Accuracy threshold theorem: what is the physical probability of failure exactly

Question

In this famous paper is derived the quantum accuracy threshold theorem for concatenated codes.

I have questions for the case errors are assumed to be local and Markovian.

In the so called level-1 simulation for concatenated codes, we basically put error correction inbetween each encoded gate.

Some usefull concepts are the notions of Rec and exRec. A 1-Rec: is an encoded gate followed by quantum error correction. And a 1-exRec is an error correction step followed by an encoded gate, followed again by quantum error correction.

It can be shown that because of quantum error correction, an algorithm will output a wrong answer if there are two fault within an exRec. A fault is defined as a physical gate that did not work as expected.

The probability of such event is upper bounded by: $p=A \epsilon^2$, where $A$ is the number of pair of fault location and $\epsilon$ is the probability that the noisiest physical gate fails.

From that it is possible after further calculation to show the accuracy threshold theorem (introducing the notion of concatenations).

My question

All the reasonning is based on the fact that it is possible to infer a probability that any given gate in the circuit fails. From a classical world I would totally understand the argument and the construction. But the quantum noise is more complicated than being purely probabilistic. And I would like to understand if it is a restricting assumption or if all Markovian quantum noise can be understood with this reasonning.

In the case of "standard" error correction, if you have an initial quantum state, that you make it go through some noise channel, because of error discretization we can make sense of the notion of error probability. Basically, we will have some probability of bit-flip or phase-flip errors due to the noise channel after the syndrome measurement.

In the fault tolerance scenario, if the error correction happened to be perfect (which is not), I could regroup all the set of gates before the error correction and define a "big" noise channel from it. In this scenario it would be like in the previous paragraph and it would make sense to define a probability of failure induced by this noise channel.

However, if I want to relate the properties of this "big" noise channel to the properties of the noise channel of each individual gates. The task might not be easy. Indeed if I define the noise channel of a CPTP $\mathcal{E}$ that tries to implement the ideal unitary $\mathcal{U}$ as the map $\mathcal{N}$ veryfing:

$$\mathcal{E}=\mathcal{N} \circ \mathcal{U}$$

If I have $N$ gates before QEC, I would have:

$$\mathcal{E}_N \circ ... \mathcal{E}_1=\mathcal{N}_N \circ \mathcal{U}_N \circ ... \circ \mathcal{N}_1 \circ \mathcal{U}_1$$

Ahd the noise channel "relevant" for QEC is defined as $ \mathcal{N}_{\text{tot}}$ which verifies:

$$ \mathcal{E}_N \circ ... \mathcal{E}_1 = \mathcal{N}_{\text{tot}} \circ \mathcal{U}_N \circ ... \circ \mathcal{U}_1 $$

Relating $\mathcal{N}_{\text{tot}}$ to the $\{\mathcal{N}_{i}\}$ is not an easy task because among other things of commutation issues.

And this is basically my issue here. In the fault tolerance construction the reasonning consists in some kind of probabilistic reasonning. If one gate "fails" with a probability $\epsilon$, then before QEC, I will have an error (which I can correct). But the quantum noise is non probabilistic, there are all the commutation issues that I just talked for instance. Thus I really don't understand the reasonning if I "think quantum" instead of with classical error probabilities. I could for instance expect some "quantum amplitudes" effects, or "crossed" contribution between all those gates which cannot be understood with classical probabilities.

Thus: how to understand why it is fine to assume that each gate fails with a given probability in FT construction ? How is this probability strictly defined ?

Answer 1

I don't know much about FTQC. The following includes my personal understanding of the AGP paper and your question. It may not be 100% correct.

$p\leq A \epsilon^2$ sounds like a loose bound since it takes all possible cases of independent faults occurring on a pair of locations in a 1-exRec as malignant (and it uses the largest size $A$ and ignores the case when faults occur on three or more locations). This doesn't require people to compute the propagated noise. So I assume the accuracy threshold theorem you refer to is the revised one in Sec. 6 of AGP (and perhaps some following sections).

In the revised accuracy threshold theorem, every possible case is taken into account. As shown in Eq. (16) of the paper, each pair / triple of locations needs to be classified to be malignant (errors will propagate) or not. So I think to estimate the accurate threshold for a specific circuit, people do need to iterate over every possible case and calculate the probabilities. This task can be $easy$ with a table of commutation rules for every input error and gate / preparation / measurement (for example, CNOT turns $XI$ into $XX$, $ZI$ into $ZI$, $IX$ into $IX$, $IZ$ into $ZZ$).

If you are worried about the definition of probabilities, The main purpose of using the definition is to make the independent noise model easy to simulate. The assumptions used in the independent noise model usually include:

1. The probability of one error occurring on every possible location is the same. So we will have parameters $p_X, p_Z$ (and sometimes $p_Y$. It looks weird to me, but some papers do include $p_Y$ as a parameter.)
2. Sometimes the probabilities of all kinds of errors (like $X,Z,Y$) are assumed to be the same. ($p=p_X=p_Z$)

Answer 2

The key idea you're missing is error digitization. Any general error mechanism can be represented as a weighted sum of Pauli products, and if the error correction procedure corrects a Pauli product then it corrects that Pauli product term appearing in the weighted sum.

For example, consider rotating every qubit in an error correcting code by 1 degree around the Z axis. Note that $R_z(1°) = I \cos(1°) + i Z \sin(1°)$. Suppose the error correcting code corrects all Pauli product errors with up to 10 non-identity Pauli terms and there are 100 qubits in the system. Then after you apply the binomial theorem to $(I \cos(1°) + i Z \sin(1°))^{\otimes 100}$, the error correction process will fix all error terms with up to 10 Zs. The remaining error terms have a weight with a prefactor $\sin(1°)^{10} \approx 2.6 \cdot 10^{-18}$. Even after accounting for the fact that there's a lot of them, they're completely negligible. So even though we applied a simultaneous error to every qubit, the deviation from the true result is tiny because the decomposition of that error into Pauli products has negligible weights on the uncorrected Pauli products.

It's also important that quantum mechanics is linear, so that errors with small weights can't become errors with big weights.