It is a well-known fact that in fault-tolerant quantum computing, it is sufficient to actually correct the Pauli errors only right before the next non-Clifford gate.
My purpose is to check all the details behind such a claim.
In all the following examples, I assume I use a code able to resist against $t=2$-errors at most. In what follows, I call "one error" the application of a weight-1 physical Pauli.
Scenario I: we have less than $t$ physical errors along the computation
In the image below, at the top, we see an algorithm at the logical level where each red $T$ is a non-Clifford gate. Each white $C$ is a Clifford one. Between each logical gate, the error-correction syndromes are extracted and kept in a classical memory. I assume that I have in total two Pauli errors occurring as shown below.
The bottom of the image represents the code space the logical qubit is in. Each stabilizer measurement can return an eigenvalue $\pm 1$ and calling $n$ the number of stabilizers, there are then $2^n$ code spaces possible. $C_0$ represents the "error-free" code space, and $C_1, C_2$ code spaces corresponding to different non-trivial stabilizer measurements.
In this example, the total amount of errors doesn't exceed $t=2$. Each error will then put the logical qubit in another code space. Initially, we were in code space $C_0$, the first error put us in $C_1$ and the second one in $C_2$.
Claim I: As long as (I.i) the total number of errors is less or equal to $t$, (I.ii) I keep track of the code space I am in, (I.iii) whichever code space I am in, I can implement the logical gate I want, THEN, I never need to correct in practice: the measurements of the logical qubits at the end of the computation combined to my knowledge of the codespace will guarantee reliable outputs.
Note that "claim I" implies that we do not care whether or not a non-Clifford gate is happening. This is completely irrelevant if less than $t$ errors occur.
Scenario II: at some point in the computation, more than $t$ errors occur (but in a manner that no logical error is introduced: these errors occur at different correction cycles)
In the image below, I assume that $3>t$ errors occur. Importantly, these $3$ errors occur at different rounds of syndrome extraction so that conceptually, enough classical information is known to fix the error (if $3$ errors occured during one round of error correction, an uncorrectable logical error would have been introduced).
Finally, in the image represented I assumed the non-Clifford to be a $T \equiv \exp(-i \pi/8 Z)$-gate (this assumption is only important for Claim IV below).
Because $3>t$ errors happened, a logical Pauli drift might now affect the state of my logical qubit. More precisely, in this example I considered that after the $3$'rd error, I am back in the code space but with a logical Pauli drift that I call $P_L^0$.
As long as the following gates are Clifford, I can easily "commute" this Pauli drift until the next non-Clifford gate. The logical Pauli drift right before the next non-Clifford gate is $P_L^3 \neq P_L^0$.
Claim II: I can apply a correction "once for all" before the following non-Clifford gate to fix the drift. Such correction is easy to compute as it is the result of keeping track a logical Pauli through a logical Clifford circuit (Gottesman-Knill theorem). It is also easy to apply as we just have to apply a logical Pauli operator.
Claim III: "In general", commuting the logical Pauli drift with the following non-Clifford gate would create some "complicated" logical drift (i.e. neither Pauli or Clifford). Because of that it would be hard to keep track of what happens to this logical error classically. This is the reason why we want to correct any logical error before this non-Clifford gate happens.
Claim IV: In some cases, the following non-Clifford can have the property to convert a preceeding logical Pauli drift ($P_L^3$) to a Clifford drift ($C_L^1$). It would be the case for a logical $T$ gate. If it occurs we might delay even more the correction: the drift $C_L^1$ after the first $T$ gate gets "converted" to a drift $C_L^3$ before the second $T$-gate. Before this second $T$-gate we could then apply a logical Clifford operator $(C_L^3)^{\dagger}$ to "correct" the $C_L^3$ drift. We shouldn't wait more to correct as the logical Clifford error $C_L^3$ might otherwise be converted to a "complicated" logical operator $O_L^1$ after the second $T$-gate.
Note that Claim IV is based upon the following two assumptions: (IV.i) following the evolution of a Clifford error through a Clifford circuit happens to be easy, (IV.ii): applying a "complicated" Clifford is easy. I am not sure neither of these assumptions is valid: the Clifford set form a group but it does not necessarily imply that keeping track of a Clifford drift through a Clifford circuit is easy (after all, the unitary operators form a group but computing the product of two $n$-qubit unitary matrices is hard in general). Even if it was easy, the Clifford correction to apply could be very complicated (it could be a Clifford operation that cannot be written as a tensor product of single and two qubit gates).
My questions in summary:
- Do you fully agree with Claims I to III?
Additionally:
- Do you agree with: The reason why we need to worry about correcting before the next non-Clifford gate occurs because we are keeping track of a logical drift: any error at the physical level (i.e. simply changing the code space) does not care about the presence of non-Clifford gates.
- What do you think of Claim IV and the paragraph following it. Is it correct? Any comment on this?
