My understanding of the code threshold for an $ [[n,1,3]] $ code is something roughly like the setup given in

How to compute the error threshold for the $9$-qubit Shor code?

where the error channel is a depolarizing channel in which no error occurs with probability $ 1-p $ and each of the weight $ 1 $ Pauli errors $ X, Y, Z $ occurs with probability $ p/3 $.

Then you compute, as a function of $ p $, the probability $ p_L(p) $ of an error happening to the one logical qubit. $ p_L(p) $ as a function of $ p $ will have the property that for small values of $ p $ it is the case that $ p_L(p)< p $ and for the large values of $ p $ it is the case that $ p_L(p) >p $. The threshold of the code $ p_T $ is the value of $ p $ for which $ p_L(p_T)=p_T $. For $ p< p_T $ the error-corrected logical qubit is more reliable than any one of the physical qubits. For $ p>p_T $ the error-corrected logical qubit is less reliable than any one of the physical qubits, so you might as well just forget about your stupid error correcting code and just encode your logical qubit into a raw physical qubit instead.

My intuition is that for sufficiently noisy physical qubits (large values of $ p $) it will eventually be the case that using multiple physical qubits to encode your logical data will actually introduce more errors that it is able to correct. In other words, my intuition is that we must always have $ p_T<1 $.

I know there are different kinds of code thresholds so this intro is just an example, I am interested in any upper bound on any type of code threshold.

Does anyone know an argument making this rigorous?

In other words, my question is:

Is there any no-go theorem that the threshold of a code is never $ p_T=1 $?

And if such arguments/ general information theoretic principles exist I would love to know what the smallest known universal upper bound on the threshold of a quantum code is. Is it $ p_T<100\text{%} $? Is it $ p_T < 50\text{%} $?


2 Answers 2


TL;DR: The threshold is not just a property of a quantum error correcting code. The existence and value of the threshold depends on the noise model (and also on the chosen decoding procedure). To demonstrate this, I exhibit a noise channel under which the no-cloning theorem implies that $p_T<\frac12$ for every code and every decoder. This rules out the existence of a code with $p_T=1$ for every noise model.

Digression: break-even vs threshold

Before describing the noise process that yields $p_T<\frac12$, let me point out that the condition $p=p_L$ does not define the threshold. Instead, that condition defines the break-even point, which is not necessarily the same.

In the simplest terms, the threshold is whatever number appears in the relevant instance of the threshold theorem. More helpfully, the threshold is the largest real number $p_T\in[0,1]$ such that a quantum computer whose physical gate operations fail with probability $p<p_T$ can achieve arbitrarily low probability $\epsilon$ of failure in executing any quantum program with $K$ operations at the expense of overhead that is $\mathcal{O}\left(\mathrm{polylog}^c\left(\frac{K}{\epsilon}\right)\right)$ per operation.

Note the asymptotic character of the threshold theorem. It means that in practice looking for the threshold involves a (more or less explicit) computation of the limit of a series. In more practical terms, suppose you draw the $p_L$ vs $p$ curves for a family of quantum error correcting codes with increasing code distance. Each of the curves will typically intersect the line $p_L=p$ at some point. This is the break-even point for that particular code distance. The lines will also intersect each other and these intersection points may converge. If they do, then typically they converge from the right. The $p$ coordinate of the limit point is the threshold, because for any $p$ that is less than that value we can guarantee that a modestly larger quantum computer will have a substantially lower logical error rate than a smaller quantum computer. There are codes for which the limit point lies at $p=0$. We say that those codes don't have a threshold. Nevertheless, these codes may have a positive break-even point at every code distance.

I now return to the main point of constructing an error model under which no code can achieve $p_T \geqslant\frac12$.

Intuitive idea

The key idea is that noise, which we usually think of as undesired deviations of quantum dynamics from theoretical ideal due to system imperfections, can in fact be due to the environment secretly "spying" on our encoded quantum information. If we were successful in our attempts to preserve a quantum state in the code subspace and if the environment were simultaneously successful in its attempts to spy on our quantum state, then jointly we and the environment would have copied the state!

Probabilistic $\text{SWAP}$ noise

Consider a two-qutrit quantum channel $\mathcal{E}$ which extends the action of $$ \mathcal{E}(\rho\otimes|2\rangle\langle 2|)=\frac{\rho\otimes|2\rangle\langle 2|}{2}+\frac{|2\rangle\langle 2|\otimes\rho}{2}.\tag1 $$ We can easily realize this channel by swapping the qutrits when a symmetric coin comes up heads and doing nothing if it comes up tails. Suppose we use the $|0\rangle$ and $|1\rangle$ states of each qutrit to encode a qubit. Then the error channel $\mathcal{E}$ inflicts an erasure error on the first qubit with probability $p=\frac12$.

We can also consider a virtual qubit that begins on the left side at the input of $\mathcal{E}$ and migrates to the right at the output of $\mathcal{E}$. The channel $\mathcal{E}$ inflicts an erasure error on this virtual qubit with probability $p=\frac12$, too.

Arbitrarily reliable universal copier from encoding and recovery

Suppose we have two blocks of $n$ qubits where each qubit resides in the $\mathrm{span}(|0\rangle, |1\rangle)$ subspace of a qutrit. Suppose further that we use a quantum error correcting code $\mathcal{C}$ to encode one logical qubit into each block. Let $\mathcal{R}$ denote the code's recovery operation. Suppose that the joint effect of noise on each of the $n$ corresponding pairs of physical qutrits in the two logical code blocks is described by $\mathcal{E}$. Finally, assume that $\mathcal{R}$ achieves threshold $p_T\geqslant\frac12$ under the noise described by $\mathcal{E}$.

Let's initialize the two code blocks in $\rho\otimes|2\rangle\langle 2|^{\otimes n}$ for some logical state $\rho$. We will attempt recovery for two logical qubits: the one encoded in the left code block and the virtual one encoded in the $n$ virtual qubits that begin on the left at the input to $\mathcal{E}$ and exit on the right at its output.

Note that the left logical qubit and the virtual logical qubit are both seeing physical erasure errors occurring with probability $p=\frac12$, so noise and recovery yield $$ \left[(\mathcal{R}\otimes\mathcal{R})\circ\mathcal{E}^{\otimes n}\right](\rho\otimes|2\rangle\langle 2|^{\otimes n})=(1-2p_L+p_L^2)\rho\otimes\rho+(2p_L-p_L^2)\sigma\tag2 $$ where the first term corresponds to successful decoding of both logical qubits and $\sigma$ is an error term. Note that the logical error probability $p_L\lt p=\frac12\leqslant p_T$. Since this is below the threshold for each of the logical qubits, we can use concatenation $\mathcal{C}$ (or simply a larger code family member if $\mathcal{C}$ is a topological code) to construct a channel $$ \left[(\mathcal{R}^{(k)}\otimes\mathcal{R}^{(k)})\circ\mathcal{E}\right](\rho\otimes|2\rangle\langle 2|^{\otimes n})=(1-\epsilon)\rho\otimes\rho+\epsilon\sigma\tag3 $$ where $\mathcal{R}^{(k)}$ denotes the recovery operation of $k$ levels of concatenation of the code $\mathcal{C}$, which has arbitrarily low error rate $\epsilon$. Clearly, this channel copies an arbitrary quantum state with arbitrarily high reliability and is therefore impossible. Therefore, the assumption that $p_T\geqslant\frac12$ is false.


For communication under depolarizing noise, the threshold is exactly $50\%$. We have constructions that achieve this, and we can prove you can't do better.

The key idea is that any protocol where you send complicated codes through a channel is isomorphic to one where you use the channel to share Bell pairs $|00\rangle + |11\rangle$, do entanglement purification on the Bell pairs, and then use the purified Bell pairs to teleport across the channel. So if purification can't work, the original protocol couldn't work either.

For any amount of depolarization less than 50%, you can alternate between purifying with the [2,1,2] X basis rep code and the [2,1,2] Z basis rep code (like what's done in my paper "Tetrationally Compact Entanglement Purification). This will pull the fidelity up from 50%, until it's as close to 100% as you'd like. You can then consume the arbitrarily-purified entanglement to communicate a qubit with arbitrarily-good fidelity.

If the communicated fidelity is less than 50%, then you can show the density matrix describing the Bell pair's state can be produced using local operations and classical communication. Therefore the Bell pair isn't entangled anymore. But if you can't get entanglement across the channel, the later teleportation is going to fail. Therefore it's not possible to make such a channel fault tolerant.

Therefore the depolarization strength threshold for communication is $t=50\%$. Beware that this assumes only the channel itself is noisy. It assumes the encoding and decoding computers are perfect. For computation under depolarizing noise, the situation is much more complicated. The threshold will presumably be worse; certainly it won't be better.

Here is the state you get from 50% depolarizing a Bell pair (the bottom three qubits are really bits being used to generate the error):

enter image description here

Here is the same state, but made under LOCC conditions. Alice and Bob start with two $|0\rangle$ qubits. They roll a die. If the die roll is odd, they each apply X to their qubits. Also, if it's 1 or 4, they each apply $\sqrt{Y}$ to their qubits. Also, if it's 2 or 5, Alice applies $\sqrt{X}$ to her qubit while Bob applies $\sqrt{X}^\dagger$. The density matrix of the resulting state, after tracing out the die, is identical to the depolarized Bell pair. But since no two qubit gate has occurred, we know the qubits cannot be entangled:

enter image description here


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.