Analytical Approximation of Pseudothreshold for Steane Code

Question

Is there an analytical way by which one can approximately find the pseudothreshold of the Steane code? My supervisor told me that there is a way, using the physical error rate and the number of gates used in the actual code, but I wanted to ask here and get a second (more precise) opinion.

Answer 1

Step 1: proper definition of faults and errrors.

Let's assume that a quantum gate is implemented on the $n$ physical qubits composing the quantum computer (system $S$) by the mean of a CPTP operation $\mathcal{E}$ which tries to implement the (perfect) unitary $\mathcal{U}$. I can define the noise map $\mathcal{N}$ as the map veryfing:

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

A noisy gate can then be understood as a perfect unitary followed by some noise acting "alone" on the system (if the gate was perfect we would have $\mathcal{N}=\mathbb{I}$). Now, if we consider the initial (pure) density matrix $|\psi_i\rangle \langle \psi_i|$ of the system on which the algorithm is implemented, after having applied $N$ gates to it, its final state will be a mixed density matrix $\rho_f$. It verifies:

$$\rho_f = \mathcal{N}_1 \circ \mathcal{U}_1 \circ \mathcal{N}_2 \circ \mathcal{U}_2 \circ ... \circ \mathcal{N}_N \circ \mathcal{U}_N (|\psi_i\rangle \langle \psi_i|)$$

Now, we can also consider a purification of $\rho_f$. A noisy CPTP operation acting on a system can always be seen as a a unitary entangling this system with some environment. Calling $|\Psi \rangle$ the final state of this system+environment set, it is possible to show that:

$$|\Psi \rangle=\sum_{j_1,...,j_N} E_{j_N} U_N ... E_{j_2} U_2 E_{j_1} U_1 |\psi_i\rangle |\epsilon_{j_1}...\epsilon_{j_N} \rangle \tag{1} \label{eq:psiFault}$$

Where $|\epsilon_{j_1}...\epsilon_{j_N} \rangle$ is a state for the environment and the $E_{j_i}$ are $n$-Pauli matrices. Note that the family of states $|\epsilon_{j_1}...\epsilon_{j_N} \rangle$ is not necessarily orthonormal. We could also consider that this sequence of $N$ gates is actually one "big" quantum gate $\mathcal{E}=\mathcal{E}_1 \circ ... \circ \mathcal{E}_N$. Introducing the noise map $\mathcal{N}$ for this "big" quantum gate we can also write:

$$|\Psi \rangle=\sum_{j} E_{j} |\psi_f\rangle |\epsilon_{j} \rangle \tag{2} \label{eq:psiErrors}$$

Where $E_j$ is an $n$-Pauli matrix acting on $|\psi_f\rangle$ and $|\psi_f\rangle=U_N...U_1 |\psi_i \rangle$ (it is the final quantum state we would have if the $N$ gates were the ideal unitaries).

Defining errors:

We look at one given element in the sum in \eqref{eq:psiErrors}. We say that it contains $p$ errors if the associated $E_j$ contains non trivial Pauli operators (i.e $X,Y$ or $Z$ applied on $p$ different physical qubits).

Defining faults:

We look at one given element in the sum in \eqref{eq:psiFault}. We say that the $l$'th gate had $p$ faults if the Pauli operator $E_{j_l}$ contains $p$ non trivial Pauli operators.

Step 2: where do we do error correction?

When we implement an algorithm with error correction, we do not simply want to do a quantum memory but we also wish to manipulate the logical qubits. Because of that we need to separate the logical gate we would like to do, from the detection and correction of errors. It can be done with the following concepts:

1. I call 1-Ga (for 1 Gadget) a logical gate applied on a logical qubit. In practice it will be composed of a given number of physical gates applied on the physical qubit. If without error correction we wanted to do a Hadamard, with error correction the 1-Ga will do a logical Hadamard on the logical qubit.
2. I call 1-Ec (for 1-Error correction) a component that will detect errors occuring on a logical qubit and correct them by applying the appropriate feedback operation.

The principle of fault-tolerance is to build a circuit in which each 1-Ga is being followed by a 1-Ec as represented on the image below (the full understanding of this image is given below, just look at how the 1-Ga and 1-Ec are following each other for now on). On this image the horizontal line represents a logical qubit (hence composed of a given number of physical qubits).

Step 3: Axioms behind 1-Ec, and 1-Ga

We need to assume some "good behaviors" of the 1-Ga and 1-Ec. Here are the axioms we are asking them to verify.

1. (Axiom 1-Ga, behavior of errors) I assume that for 1-Ga, if its input logical qubit has only one error (which means that the quantum state describing it is associated to a non trivial pauli operator applied on one qubit only given my definition of errors provided above) and that there is no fault inside it, its output state will contain a maximum of one error (we ask the 1-Ga to be nicely designed so that they do not propagate errors from one physical qubit composing the logical qubit on many physical qubits composing this same logical qubit).
2. (Axiom 1-Ga, behavior of faults) I also assume that if a 1-Ga had no errors at its input but contained one fault, then its output state will contain one error maximum (intuitively it means that if a fault is occurring in the 1-Ga it is not "too bad" and will only cause one error on the output logical qubit)
3. (Axiom 1-Ec, behavior of errors) I assume for the 1-Ec, that if its input contains a maximum of one error, (but the 1-Ec contains no fault), then its output will contain no errors (it means that in the case there were an error, the error correction "does the job", and if no error was there it will not add an error).
4. (Axiom 1-Ec, behavior of faults) I assume that for 1-Ec, if its input has no errors but one fault is occuring inside, its output will contain one error maximum (we assume that if something goes wrong in the 1-Ec, it is not "too bad").

Step 4: understanding the (pseudo)-threshold

Finally, I define the 1-exRec (for extended rectangle) the group of components contained in the "chain" 1-Ec, 1-Ga, 1-Ec. Two consecutive 1-exRec are overlapping.

And I assume that I will have a maximum of one fault per 1-exRec. I also assume that the input logical qubit had no errors.

You are ready to understand the image.

I assumed that no error was on the logical qubit at the very left. Then, a fault occured in the 1-Ec. From "Axiom 1-Ec, behavior of faults" we deduce that only one error will be at its output. Now as we also assumed a maximum of one fault per 1-exRec, the following 1-Ga and 1-Ec cannot have fault. After the 1-Ga we still have only one error from "Axiom 1-Ga, behavior of errors". This error will be corrected by the following 1-Ec "Axiom 1-Ec, behavior of errors". And we move on. I assumed that the next fault is occuring on the 1-Ga of the following 1-exRec. From "Axiom 1-Ga, behavior of faults" it induces one error maximum. This error is corrected by the following 1-Ec that cannot be faulty from my assumption of 1 fault maximum per 1-exRec. And so on.

From this we can estimate a pseudo-threshold. If we assume that all the physical gates have a probability to have a fault that is $\eta$, if we call $A$ the total number of physical gates inside a 1-exRec, the probability that a 1-exRec does not behave "nicely" (i.e that it contains two faults) is given by $\binom{A}{2} \eta^2$.

Now, the 1-exRec is the good set of components on which you should reason to define a logical gate. The logical gate (physically represented by the 1-exRec) will improve the situation over the case no error correction was done if it verifies:

$$\binom{A}{2} \eta^2<\eta \Leftrightarrow \eta< \eta_{\text{thr}} \equiv \frac{1}{\binom{A}{2}}$$

The quantity $\eta_{\text{thr}} \equiv \frac{1}{\binom{A}{2}}$ is the pseudo-threshold. It is equal to $9.3 \times 10^{-5}$ for a depolarizing noise channel (see this paper).

Extra information

I simplified slightly the story. For instance, here I reasoned with a unique logical qubit and I neglected "boundaries effect". Typically I considered that the qubit at the very left has no errors (to clarify what happens with boundaries we would need to describe preparations and measurements). But this is really the main intuition to get from this (and it is not far from the very full picture).

I did not explain the principle of concatenations here, but we are almost there. It consists in replacing "again" of all the physical gates that are inside the 1-EC, and 1-Ga by "new" 1-Ga and 1-Ec. This is also the reason behind the notations "1"-Ec and "1"-Ga: what I explained corresponds to the first level of concatenation.

For further information this paper is one of the main references on this topic.