I'm having trouble understanding the so-called "digitization of errors" argument in QEC.

Suppose I have to encode my logical qubit into $n$ physical qubits to do error correction. I will use some encoder - let's call it $E$ - and note that the encoder cannot depend on the input state. After encoding, we then have the physical qubits in some state $E(\vert\psi\rangle)$.

Suppose the physical qubits are subjected to some noise such that the new state they have is $E(\vert\psi'\rangle)$ where $\vert\psi' \rangle \approx_\delta \vert\psi\rangle$ (this represents closeness in trace distance) for small $\delta$.

A decoder cannot distinguish between these two states, since they can be arbitrarily close in trace distance as $\delta\rightarrow 0$. So the decoder will output $\vert\psi\rangle$ in two cases

  1. The input state was $\vert\psi'\rangle$ and there was no noise.
  2. The input state was $\vert\psi\rangle$ and there was some noise.

I suspect the answer has to do with quantum computing never using states that are too close to each other. Indeed, if the final state after a computation was $\vert\psi\rangle$ or $\vert\psi'\rangle$ and these are close in trace distance, then the measurement statistics would also be very similar.

Can someone elucidate exactly what assumptions are made about the state during a quantum computation, how distinguishable they need to be and how that allows us to use error correction techniques?


2 Answers 2


When you encode in an error correcting code, you select a subspace that your encoded qubit sits in. You can identify this with some projector $P$. For instance, if you know your logical 0 and logical 1, $$ P=|0_L\rangle\langle 0_L|+|1_L\rangle\langle 1_L|. $$ Now, in quantum, we usually describe measurements by projective measurements, meaning a set of projectors that sum to the identity. At a very crude level, you could think of error correction as a measurement which, at least in part conveys the information "in the original space" or "not in the original space". These are projects $P$ and $I-P$. (There's then some further structure inside $I-P$ corresponding to multiple different measurement results that help you identify how it's not in the original space.)

So, if we started with an encoded state $|\psi\rangle$ with no error, we always get the measurement result "in the original space". On the other hand, for $|\psi'\rangle$, however close it is to the original state, it can always be decomposed as $$ P|\psi'\rangle+(I-P)|\psi'\rangle. $$ So, you do the measurement, and you get two different possible measurement results. With probability $\langle\psi'|P|\psi'\rangle$ you get "in the original space". This probability is about $1-\delta^2$. The other option is that you collapse (with small probability) into a state that is orthogonal to the original space. With the extra information gained in the measurement structure, you should be able to work out how to push it back into the space, and that's the correction part.

Note that nowhere in this does the decoder have to distinguish between $|\psi\rangle$ and $|\psi'\rangle$ which, as you say, would be impossible. All it has to do is distinguish "in original space" from "not in original space" and for states that are a bit of both, it doesn't care about preserving that superposition because we can fix that later.

  • 2
    $\begingroup$ Thanks for answering! I didn't follow the argument for why measuring $\vert\psi'\rangle$ with $\{P, I-P\}$ gives us those outcomes. What happens if an error takes $\vert\psi\rangle = \vert 0\rangle_L\rightarrow \vert\psi'\rangle = \sqrt{1-\delta}\vert 0\rangle_L + \sqrt{\delta} \vert 1\rangle_L$ for arbitrarily small but nonzero $\delta$? The projective measurement gives us the $P$ outcome with probability 1 and the error went undetected. Moreover, as we do more operations, this can result in such errors accumulating till we have a full logical error. $\endgroup$
    – Joan
    Commented Apr 5 at 19:04
  • 2
    $\begingroup$ Yes, that sort of error is always a risk that you cannot mitigate against fully. However, your choice of error correcting code should be such that there's a significant distance (i.e. requires multiple errors to flip from $|0_L\rangle$ to $|1_L\rangle$) so that that is extremely low probability. The higher the code distance, the more unlikely it is (it goes exponentially with the distance), until you get it down to some tolerable level of error. $\endgroup$
    – DaftWullie
    Commented Apr 6 at 4:29

The trick is to rewrite your continuous rotations as a perturbative sum. For example, consider applying $R_Z(\theta)$ to all data qubits of an $n$-qubit code. You can rewrite:

$$R_Z(\theta) = I \cos \theta + i Z \sin \theta$$

$${n \choose k}_Z = \text{sum of n-qubit Pauli strings with $k$ iZ terms and $n-k$ I terms}$$

$$R_Z(\theta)^{\otimes n} = \sum_{k=0}^n {n \choose k}_Z \left(\cos^{n-k} \theta \right)\left(\sin^k \theta\right)$$

In a distance $d$ code, error correction will correct up to $d/2$ errors. It transforms ${n \choose k}_Z$ into ${n \choose k}I^{\otimes n}$ if $k < d/2$. Supposing $d=5$ then, after error correction (C), we will have:

$$\text{C} \cdot R_Z(\theta)^{\otimes n} = I^{\otimes n} \left(\sum_{k=0}^2 \left(\cos^{n-k} \theta \right)\left(\sin^k \theta\right)\right) + \text{C} \cdot \left(\sum_{k=3}^n {n \choose k}_Z \left(\cos^{n-k} \theta \right)\left(\sin^k \theta\right) \right)$$

Using small angle approximations $\cos \theta \approx 1$ and $\sin \theta \approx \theta$, we get:

$$\text{C} \cdot R_Z(\theta)^{\otimes 2} \approx I^{\otimes n} + \text{C} \cdot {n \choose 3}_Z \theta^3 + \text{C} \cdot {n \choose 4}_Z \theta^4 + \dots$$

Assuming w.l.o.g. that $\theta > 0$ we can then pessimistically assume all the bad states constructively interfere, coherently combining into a single state $|\text{BAD}\rangle$. We then get:

$$R_Z(\theta)^{\otimes n} \approx I^{\otimes n} + O(\theta^3) \cdot |\text{BAD}\rangle$$

By increasing the code distance, we can suppress $O(\theta^3)$ to $O(\theta^4)$ to $O(\theta^5)$ and etc. This exponentially suppresses the bad states resulting from this particular kind of continuous rotation. That's where the fault tolerance comes from.

Other combinations of rotations can be analyzed in the same way.

I will use some encoder - let's call it E - and note that the encoder cannot depend on the input state.

This is potentially one place where you're confused. Fault tolerant codes don't use this kind of encoder. They instead use different strategies for different states.

For example, in the surface code:

  • $\begingroup$ Thank you for the answer! I accepted the other but both answers complement each other and helped clear up my understanding :) $\endgroup$
    – Joan
    Commented Apr 7 at 17:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.