# How is it not a contradiction that it is possible to build fault tolerant circuits with strictly contractive (e.g.: depolarizing noise) channels?

This paper discusses strictly contractive channels, i.e. channels that strictly decrease the trace distance between any two input quantum states.

It is shown that if a quantum circuit is composed of rounds of gates followed by strictly contractive channels then the trace distance between any two input states would decay exponentially with circuit depth, which means we would not be able to distinguish outputs corresponding to any two different inputs.

In light of this, how is it even possible to build any kind of fault-tolerant circuit which is capable of "arbitrarily long" computations, given that the standard noise model, the depolarizing channel, is strictly contractive?

• Because measurements with post-selection can be non-contractive (they aren't even CP maps since they are nonlinear). – keisuke.akira Aug 9 '20 at 21:30
• But aren't there fault tolerant schemes that do not even use post-selection? – Dina Abdelhadi Aug 10 '20 at 7:51
• @keisuke.akira There is no post-selection in error correction. – Norbert Schuch Aug 10 '20 at 18:10

This is a very interesting question. Indeed, CP maps - and this includes the operations used in the error correction (measurement and subsequent unitaries) - will always decrease the trace norm.

The answer is that if you take a (strictly) contractive map on, say, a qubit, and consider how it acts if you apply it to many qubits, there will always be some subspace where the map is much less contractive - still contractive, but supressed exponentially. The art of (quantum) error correction is to encode the information in those subspaces, and to "re-focus" it into those subspaces (which is the actual error correction procedure).

Let me give a (slightly oversimplified) example.

Consider a noise which flips a bit with probability $$\epsilon=0.01$$ (per unit time, if you wish).

Now encode a (classical) bit in $$N$$ zeros or $$N$$ ones, $$0\cdots 0$$ and $$1\cdots 1$$. Then, these states (seen as quantum states, if you wish, or as probability distributions) will keep a trace distance on the order of at most $$\epsilon^{-N/2}$$ -- after all, you have to flip half the bits in either to get any overlap between them (and if they are orthogonal, the trace distance stays 1).

So what happened? Before, the noise was $$\epsilon=0.01$$. Now, the noise is $$\epsilon=0.01^{-N/2}$$. So for $$N=10$$, you might be able to go about $$10^{10}$$ time steps, rather than $$100$$.

Of course, this will break down if you let more time pass -- so what you have to do after a short interval of time is to "re-focus" your information, that is, move it back to that subspace which is best protected (like all zeros and all ones). This is what error correction does. This is a CP map and does not increase distinguishability, but it will allow you to stay with the best error rate of $$1$$ error in $$10^{10}$$.

(Note: Clearly, this is not a way to safely encode quantum information - this is not what this example is supposed to illustrate.)

• In the example, if we consider N=2 then the |00><00| state will be mapped to $(1-\epsilon)^2 |00><00| + \epsilon(1-\epsilon) |01><01| + \epsilon(1-\epsilon) |10><10|+\epsilon^2|11><11|$, similarly for |11><11|. summing up the terms, we get that after the channel, the trace distance is (1-2epsilon), Note that the N=1 case is contracted after the channel by (1- 2 epsilon). Thus, adding one more qubit did not exponentially suppress the contraction, it seems. – Dina Abdelhadi Aug 10 '20 at 19:31
• I believe in the same paper, it is shown that if one depolarizing channel contracts the trace distance by (1-p), having two parallel depolarizing channels will still contract it by (1-p). Isn't it true that the strictly contractive channel should contract all subspaces (like if we assume it is acting on a set of basis for one subspace)? – Dina Abdelhadi Aug 10 '20 at 19:32
• @Dina My argument is meant in the large N limit. Also, note that the exponent is N/2, so N=2 will indeed not help. And no, that's exactly the point: There are states which stay more orthogonal than others if you apply the same channel to every qubit. More formally, if you have a channel $$E(\rho) = (1-p)\rho + p\,I/2\ ,$$ then $E\otimes E$ is not of the form $(1-q)\rho + q\,I/4$. Why don't you do the example for, say 4 or 6 qubits? (Note that this example is entirely classical and works for probability distributions.) – Norbert Schuch Aug 10 '20 at 20:33
• @Dina Can you point out where this is said in said paper? – Norbert Schuch Aug 10 '20 at 20:34
• It is on equation (27) and the paragraph following it. I guess trying out the 4 qubit case, the overall contraction coefficient may be a bit larger than 1-2epsilon. I don't know whether this is sufficient, since trace distance will still decay exponentially with depth, just with slower decay. – Dina Abdelhadi Aug 11 '20 at 8:34

So that's where quantum error correction comes in. By measuring the stabilizers, the code is projected back into a pure state. I'll give an example using a Bell state:

Imagine the state $$\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle),$$

which is stabilized by XX and ZZ (meaning we can catch errors by verifying that these two operators have eigenvalue +1 on our state). Now imagine that the state undergoes a stochastic X channel on the second qubit, described by:

$$E(\rho) = (1-p)I\rho I + p X_2\rho X_2.$$

The overall state will now become a mixed state described by: $$\rho = \frac{1}{2}[(1-p)(|00\rangle + |11\rangle)(\langle 00| + \langle 11|) + p(|01\rangle + |10\rangle)(\langle 01| + \langle 10|)].$$ This state is a mixed state with trace less than 1, since the error channel is non-unitary.

When we measure the stabilizers XX and ZZ, we either get [+1, +1] with probability $$1+p$$, meaning that we have projected ourselves back into the state $$\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$$, or with probability $$p$$ we get [+1, -1], meaning the state is $$\frac{1}{\sqrt{2}}(|01\rangle + |10\rangle)$$. Both of these new states are again pure states, and the goal of error correction is to be able to figure out what errors we have projected onto the state, so we can undo it and recover our state. The key point is that by measuring stabilizers, error correction naturally relies on a non-unitary process in order to deal with these trace reduction concerns.

• But isn't trace distance non-increasing under the action of any quantum channel (whether it is unitary or not)? – Dina Abdelhadi Aug 10 '20 at 7:50
• The trace gets renormalized, or at least that's how I think about it. Lets say you are given a mixed state $\rho = 0.5 |0\rangle\langle 0| + 0.5 |1\rangle\langle 1|$, this state is mixed, but if you measure it and get a 0, your state is now $\rho' = |0\rangle\langle 0|$. By measuring and applying classical corrections, we can project and then get back to a cleaner state. – Dripto Debroy Aug 10 '20 at 19:39
• But you will only get the cleaner state |0><0| with probability 1/2, so really the projective measurement maps the state to 1/2 |0><0|+1/2|1><1|. I think what you describe is probably true, however if we describe all operations by quantum channels, which cannot increase the trace distance, a more subtle argument is needed to explain why QEC works. – Dina Abdelhadi Aug 10 '20 at 19:45
• I think the issue is this claim about being unable to increase trace distance. If you look in these notes (inst.eecs.berkeley.edu/~cs191/fa14/lectures/lecture89.pdf), and look at the postmeasurement state, you'll notice the normalization factor. This factor is the part that allows measurements to "increase" the trace distance, and they renormalize the state when a measurement occurs. – Dripto Debroy Aug 10 '20 at 22:14
• @DriptoDebroy Without postselection, you cannot increase trace distance. If you measure and then do a conditional operation (and then forget the measurement result, if you want), this is a CPTP map. – Norbert Schuch Aug 11 '20 at 12:28