Why do error correction protocols only work when the error rates are already significantly low to begin with?

Quantum error correction is a fundamental aspect of quantum computation, without which large-scale quantum computations are practically unfeasible.

One aspect of fault-tolerant quantum computing that is often mentioned is that each error-correction protocol has associated an error rate threshold. Basically, for a given computation to be protectable against errors via a given protocol, the error rate of the gates must be below a certain threshold.

In other words, if the error rates of single gates are not low enough, then it is not possible to apply error-correction protocols to make the computation more reliable.

Why is this? Why is it not possible to reduce error rates that are not already very low to begin with?

• Well, at some point there is simply just noise. Is it that strange that there is a point where error correction is more likely to correct the right parts into noise? – Discrete lizard Mar 27 '18 at 17:11
• @Discretelizard not so much that there is one at all maybe, but the thresholds are usually very low (or high in terms of fidelity). Why is that so? – glS Mar 27 '18 at 17:12

We want to compare an output state with some ideal state, so normally, fidelity, $F\left(\left|\psi\right>, \rho\right)$ is used as this is a good way to tell how well the possible measurement outcomes of $\rho$ compare with the possible measurement outcomes of $\left|\psi\right>$, where $\left|\psi\right>$ is the ideal output state and $\rho$ is the achieved (potentially mixed) state after some noise process. As we're comparing states, this is $$F\left(\left|\psi\right>, \rho\right) = \sqrt{\left<\psi\right|\rho\left|\psi\right>}.$$

Describing both the noise and error correction processes using Kraus operators, where $\mathcal N$ is the noise channel with Kraus operators $N_i$ and $\mathcal E$ is the error correction channel with Kraus operators $E_j$, the state after noise is $$\rho' = \mathcal N\left(\left|\psi\rangle\langle\psi\right|\right) = \sum_iN_i\left|\psi\rangle\langle\psi\right|N_i^\dagger$$ and the state after both noise and error correction is $$\rho = \mathcal E\circ\mathcal N\left(\left|\psi\rangle\langle\psi\right|\right) = \sum_{i, j}E_jN_i\left|\psi\rangle\langle\psi\right|N_i^\dagger E_j^\dagger.$$

The fidelity of this is given by \begin{align}F\left(\left|\psi\right>, \rho\right) &= \sqrt{\left<\psi\right|\rho\left|\psi\right>} \\ &= \sqrt{\sum_{i, j}\left<\psi\right|E_jN_i\left|\psi\rangle\langle\psi\right|N_i^\dagger E_j^\dagger\left|\psi\right>} \\&= \sqrt{\sum_{i, j}\left<\psi\right|E_jN_i\left|\psi\rangle\langle\psi\right|E_jN_i\left|\psi\right>^*} \\ &= \sqrt{\sum_{i, j}\lvert\left<\psi\right|E_jN_i\left|\psi\right\rangle\rvert^2}.\end{align}

For the error correction protocol to be of any use, we want the fidelity after error correction to be larger than the fidelity after noise, but before error correction, so that the error corrected state is less distinguishable from the non-corrected state. That is, we want $$F\left(\left|\psi\right>, \rho\right) > F\left(\left|\psi\right>, \rho'\right).$$ This gives $$\sqrt{\sum_{i, j}\lvert\left<\psi\right|E_jN_i\left|\psi\right\rangle\rvert^2} > \sqrt{\sum_i\lvert\left<\psi\right|N_i\left|\psi\right\rangle\rvert^2}.$$ As fidelity is positive, this can be rewritten as $$\sum_{i, j}\lvert\left<\psi\right|E_jN_i\left|\psi\right\rangle\rvert^2 > \sum_i\lvert\left<\psi\right|N_i\left|\psi\right\rangle\rvert^2.$$

Splitting $\mathcal N$ into the correctable part,$\mathcal N_c$ , for which $\mathcal E\circ\mathcal N_c\left(\left|\psi\rangle\langle\psi\right|\right) = \left|\psi\rangle\langle\psi\right|$ and the non-correctable part, $\mathcal N_{nc}$, for which $\mathcal E\circ\mathcal N_{nc}\left(\left|\psi\rangle\langle\psi\right|\right) = \sigma$. Denoting the probability of the error being correctable as $\mathbb P_c$ and non-correctable (i.e. too many errors have occurred to reconstruct the ideal state) as $\mathbb P_{nc}$ gives $$\sum_{i, j}\lvert\left<\psi\right|E_jN_i\left|\psi\right\rangle\rvert^2 = \mathbb P_c + \mathbb P_{nc}\left<\psi\vert\sigma\vert\psi\right> \geq \mathbb P_c,$$ where equality will be assumed by assuming $\left<\psi\vert\sigma\vert\psi\right> = 0$. That is a false 'correction' will project onto an orthogonal outcome to the correct one.

For $n$ qubits, with an (equal) probability of error on each qubit as $p$ (note: this is not the same as the noise parameter, which would have to be used to calculate the probability of an error), the probability of having a correctable error (assuming that the $n$ qubits have been used to encode $k$ qubits, allowing for errors on up to $t$ qubits, determined by the Singleton bound $n-k\geq 4t$) is \begin{align} \mathbb P_c &=\sum_j^t {n\choose j}p^j\left(1-p\right)^{n-j}\\ &= \left(1-p\right)^n + np\left(1-p\right)^{n-1} + \frac 12n\left(n-1\right)p^2\left(1-p\right)^{n-2} + \mathcal O\left(p^3\right) \\ &= 1 - {n\choose{t+1}}p^{t+1} + \mathcal O\left(p^{t + 2}\right)\end{align}.

Noise channels can also be written as $N_i = \sum_j\alpha_{i, j}P_j$ for a basis $P_j$, which can be used to define a process matrix $\chi_{j, k} = \sum_i\alpha_{i, j}\alpha^*_{i, k}$. This gives $$\sum_i\lvert\left<\psi\right|N_i\left|\psi\right\rangle\rvert^2 = \sum_{j, k}\chi_{j, k}\left<\psi\right|P_j\left|\psi\right\rangle\left<\psi\right|P_k\left|\psi\right\rangle\geq\chi_{0, ,0},$$ where $\chi_{0, 0} = \left(1-p\right)^n$ is the probability of no error occurring.

This gives that the error correction has been successfully in mitigating (at least some of) the noise when $$1 - {n\choose{t+1}}p^{t+1} \gtrapprox\left(1-p\right)^n.$$ While this is only valid for $\rho \ll 1$ and as a weaker bound has been used, potentially giving inaccurate results of when the error correction has been successful, this displays that error correction is good for small error probabilities as $p$ grows faster than $p^{t+1}$ when $p$ is small.

However, as $p$ gets slightly larger, $p^{t+1}$ grows faster than $p$ and, depending on prefactors, which depends on the size of the code and number of qubits to correct, will cause the error correction to incorrectly 'correct' the errors that have occurred and it starts failing as an error correction code. In the case of $n=5$, giving $t=1$, this happens at $p\approx 0.29$, although this is very much just an estimate.

As $\mathbb P_c + \mathbb P_{nc} = 1$, this gives $$\sum_{i, j}\lvert\left<\psi\right|E_jN_i\left|\psi\right\rangle\rvert^2 = \left<\psi\vert\sigma\vert\psi\right> + \mathbb P_c\left(1-\left<\psi\vert\sigma\vert\psi\right>\right).$$

Plugging this in as above further gives $$1-\left(1-\left<\psi\vert\sigma\vert\psi\right>\right){n\choose{t+1}}p^{t+1} \gtrapprox\left(1-p\right)^n,$$ which is the same behaviour as before, only with a different constant.

This also shows that, although error correction can increase the fidelity, it can't increase the fidelity to $1$, especially as there will be errors (e.g. gate errors from not being able to perfectly implement any gate in reality) arising from implementing the error correction. As any reasonably deep circuit requires, by definition, a reasonable number of gates, the fidelity after each gate is going to be less than the fidelity of the previous gate (on average) and the error correction protocol is going to be less effective. There will then be a cut-off number of gates at which point the error correction protocol will decrease the fidelity and the errors will continually compound.

This shows, to a rough approximation, that error correction, or merely reducing the error rates, is not enough for fault tolerant computation, unless errors are extremely low, depending on the circuit depth.

• I think you're trying to explain up to which physical error rate the probability of uncorrectable errors is low? Note that fault-tolerance thresholds are smaller (orders of magnitudes for many codes) – M. Stern Mar 28 '18 at 23:44
• @M.Stern So this is a (very rough) estimate for when an error correction 'decreases the error' (i.e. increases the fidelity by some amount after noise is applied), so it's definitely not a fault tolerant threshold, no. Performing error correction may have increased the fidelity after the noise by some amount, but it hasn't reset it or anything, so fidelity will just decrease (and the error(s)) propagate even if error correction is constantly applied, showing error correction by itself isn't enough for fault tolerance – Mithrandir24601 Mar 29 '18 at 0:29
• Hm, glS will have to judge if that answers the question. In any case it's interesting and well written. So you assume that the state is orthogonal if the errors were uncorrectable, right? (That's certainly reasonable in many scenarios.) The other extreme would be when there is a 50/50 chance of a logical error in case of uncorrectable errors. – M. Stern Mar 29 '18 at 3:40
• @M.Stern Thanks! Yes, either that states are orthogonal, or taking the lower bound. As comparing one lower bound with another isn't a great idea, I went with the assumption that they're orthogonal. If there's any edits you feel would be useful to add to the end of this, work away! Hmm... I think taking a 50/50 chance of logical error would lead to the same result, only with different prefactors at the end – Mithrandir24601 Mar 29 '18 at 7:39

There is a good mathematical answer already, so I'll try and provide an easy-to-understand one.

Quantum error correction (QEC) is a (group of) rather complex algorithm(s), that requires a lot of actions (gates) on and between qubits. In QEC, you pretty much connect two qubits to a third helper-qubit (ancilla) and transfer the information if the other two are equal (in some specific regard) into that third qubit. Then you read that information out of the ancialla. If it tells you, that they are not equal, you act on that information (apply a correction). So how can that go wrong if our qubits and gates are not perfect?

QEC can make the information stored in your qubits decay. Each of these gates can decay the information stored in them, if they are not executed perfectly. So if just executing the QEC destroys more information than it recovers on average, it's useless.

You think you found an error, but you didn't. If the comparison (execution of gates) or the readout of the information (ancilla) is imperfect, you might obtain wrong information and thus apply "wrong corrections" (read: introduce errors). Also if the information in the ancillas decays (or is changed by noise) before you can read it out, you will also get wrong readout.

The goal of every QEC is obviously to introduce less errors than it corrects for, so you need to minimize the aforementioned effects. If you do all the math, you find pretty strict requirements on your qubits, gates and readouts (depending on the exact QEC algorithm you chose).

Classical Version

Think about a simple strategy of classical error correction. You've got a single bit that you want to encode, $$0\mapsto 00000\qquad 1\mapsto 11111$$ I've chosen to encode it into 5 bits, but any odd number would do (the more the better). Now, let's assume some bit-flip errors have occurred, so what we have is $$01010.$$ Was this originally the encoded 0 or 1? If we assume that the probability of error per bit, $p$, is less than a half, then we expect that fewer than half the bits have errors. So, we look at the number of 0s and the number of 1s. Whichever there's more of is the one that we assume is the one we started with. This is called a majority vote. There's some probability that we're wrong, but the more bits we encoded into, the smaller this probability.

On the other hand, if we know that $p>\frac12$, we can still do the correction. You'd just be implementing a minority vote! The point, however, is that you have to do completely the opposite operation. There's a sharp threshold here that shows, at the very least, that you need to know which regime you're working in.

For fault-tolerance, things get messier: the $01010$ string that you got might not be what the state actually is. It might be something different, still with some errors that you have to correct, but the measurements you've made in reading the bits are also slightly faulty. Crudely, you might imagine this turns the sharp transition into an ambiguous region where you don't really know what to do. Still, if error probabilities are low enough, or high enough, you can correct, you just need to know which is the case.

Quantum Version

In general, things get worse in the quantum regime because you have to deal with two types of errors: bit flip errors ($X$) and phase flip errors ($Z$), and that tends to make the ambiguous region bigger. I won't go further into details here. However, there's a cute argument in the quantum regime that may be illuminating.

Imagine you have the state of a single logical qubit stored in a quantum error correcting code $|\psi\rangle$ across $N$ physical qubits. It doesn't matter what that code is, this is a completely general argument. Now imagine there's so much noise that it destroys the quantum state on $\lceil N/2\rceil$ qubits ("so much noise" actually means that errors happen with 50:50 probability, not close to 100% which, as we've already said, can be corrected). It is impossible to correct for that error. How do I know that? Imagine I had a completely noiseless version, and I keep $\lfloor N/2\rfloor$ qubits and give the remaining qubits to you. We each introduce enough blank qubits so that we've got $N$ qubits in total, and we run error correction on them. If it were possible to perform that error correction, the outcome would be that both of us would have the original state $|\psi\rangle$. We would have cloned the logical qubit! But cloning is impossible, so the error correction must have been impossible.

To me there seem to be two parts of this question (one more related to the title, one more related to the question itself):

1) To which amount of noise are error correction codes effective?
2) With which amount of imperfection in gates can we implement fault-tolerant quantum computations?

Let me firs stress the difference: quantum error correction codes can be used in many different scenarios, for example to correct for losses in transmissions. Here the amount of noise mostly depends on the length of the optical fibre and not on the imperfection of the gates. However if we want to implement fault-tolerant quantum computation, the gates are the main source of noise.

On 1)

Error correction works for large error rates (smaller than $1/2$). Take for example the simple 3 qubit repetition code. The logical error rate is just the probability for the majority vote to be wrong (the orange line is $f(p)=p$ for comparison): So whenever the physical error rate $p$ is below $1/2$, the logical error rate is smaller than $p$. Note however, that is particularly effective for small $p$, because the code changes the rate from $\mathcal{O}(p)$ to a $\mathcal{O}(p^2)$ behaviour.

On 2)

We want to perfrom arbitrarily long quantum computations with a quantum computer. However, the quantum gates are not perfect. In order to cope with the errors introduced by the gates, we use quantum error correction codes. This means that one logical qubit is encoded into many physical qubits. This redundancy allows to correct for a certain amount of errors on the physical qubits, such that the information stored in the logical qubit remains intact. Bigger codes allow for longer calculations to still be accurate. However, larger codes involve more gates (for example more syndrome measurements) and these gates introduce noise. You see there is some trade-off here, and which code is optimal is not obvious.
If the noise introduced by each gate is below some threshold (the fault-tolerance or accuracy threshold), then it is possible to increase the code size to allow for arbitrarily long calculations. This threshold depends on the code we started with (usually it is iteratively concatenated with itself). There are several ways to estimate this value. Often it is done by numerical simulation: Introduce random errors and check whether the calculation still worked. This method typically gives threshold values which are too high. There are also some analytical proofs in the literature, for example this one by Aliferis and Cross.

• The second paragraph is touching the right points, but it is still very qualitative. You are saying that you need the gates introduced by the error correction protocol to reduce the error rate more than they increase it. However, how does one go from this intuitive idea to an actual quantitative estimate over the threshold? Also, does this imply an universal lower threshold that no error correcting protocol can beat? – glS Mar 27 '18 at 18:49
• @glS I suspect that there is such a "universal lower threshold", i.e. an error value above which there exist no fault tolerant correction protocols. However, the value should depend on both your gate set and your error model. People tend to be more interested in positive results here (showing the existence of a good fault tolerant protocol). It may be interesting to find upper bounds in order to see "how much room we have left" in making our fault tolerant schemes better. I'd guess there isn't much room left. – Jalex Stark Mar 27 '18 at 20:11
• @glS You're right, some actual quantitative calculation would improve this answer. I think these calculations are typically done numerically? But I also want to know about this – M. Stern Mar 28 '18 at 0:46
• @JalexStark What makes you think there is not much room left? For example the surface code doesn't seem to be optimized w.r.t. this threshold. It uses only nearest neighbor interactions on a lattice and you could do a lot more in general. – M. Stern Mar 28 '18 at 0:49
• @M.Stern I don't have any theorem-based evidence, and I'm not an expert in the area. I was just guessing based on the amount of work done and on how large the best thresholds are. – Jalex Stark Mar 28 '18 at 1:16

You need a surprisingly large number of quantum gates to implement a quantum error correcting code in a fault-tolerant manner. One part of the reason is that there are many errors to detect since a code that can correct all single qubit errors already requires 5 qubits and each error can be of three kinds (corresponding to unintentional X, Y, Z gates). Hence to even just correct any single qubit error, you already need logic to distinguish between these 15 errors plus the no-error situation: $XIIII$, $YIIII$, $ZIIII$, $IXIII$, $IYIII$, $IZIII$, $IIXII$, $IIYII$, $IIZII$, $IIIXI$, $IIIYI$, $IIIZI$, $IIIIX$, $IIIIY$, $IIIIZ$, $IIIII$ where $X$, $Y$, $Z$ are the possible single qubit errors and $I$ (identity) denotes the no-error-for-this-qubit situation.

The main part of the reason is, however, that you cannot use straight-forward error detection circuitry: Every CNOT (or every other nontrivial 2 or more qubit gate) forwards errors in one qubit to another qubit which would be disastrous for the most trivial case of a single qubit error correcting code and still very bad for more sophisticated codes. Hence a fault-tolerant (useful) implementation of needs even more effort than one might naively think.

With many gates per error correcting step, you can only permit a very low error rate per step. Here yet another problem arises: Since you may have coherent errors, you must be ready for the worst case that an error $\epsilon$ propagates not as $N \epsilon$ after N single qubit gates but as $N^2 \epsilon$. This value must remain sufficiently low such that you overall gain after correcting some (but not all) errors, for example single qubit errors only.

An example for a coherent error is an implementation of a gate $G$ that does, to first order, not simply $G$ but $G + \sqrt{\epsilon} X$ which you might call an error of $\epsilon$ because that is the probability corresponding to the probability amplitude $\sqrt{\epsilon}$ and hence the probability that a measurement directly after the gate reveals that it acted as the error $X$. After $N$ applications of this gate, again to first order, you have actually applied $G^N + N \sqrt{\epsilon} G^N X$ (if G and X commute, otherwise a more complicated construct that has $N$ distinct terms proportional to $\sqrt{\epsilon}$). Hence you would, if measuring then, find an error probability of $N^2 \epsilon$.

Incoherent errors are more benign. Yet if one must give a single value as an error threshold, then one cannot choose to only assume benign errors!

• thanks for the answer, but I would appreciate if you could expand the answer to say more about some of the points here. In particular, 1) what do you mean exactly by saying that you need many gates in the error correcting code because there are "many errors to detect"? 2) What do you mean with "straight-forward logical construct"? 3) Why do "coherent errors" imply an error propagation scaling like $N^2 \epsilon$ instead of $N\epsilon$? – glS Mar 28 '18 at 21:33
• @glS I have substantially expanded the answer to address all your questions. Did I manage to do that? – pyramids Mar 29 '18 at 9:17