2
$\begingroup$

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.

enter image description here

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).

enter image description here

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:

  1. Do you fully agree with Claims I to III?

Additionally:

  1. 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.
  2. What do you think of Claim IV and the paragraph following it. Is it correct? Any comment on this?
$\endgroup$

1 Answer 1

1
$\begingroup$

A loophole in this reasoning is that you can set up delayed choice gates to correct the error. By using ancilla qubits, you can guarantee all corrections correspond to X-vs-Z basis measurement and classically controlled Paulis, even if those gates are only performed much later.

The measurement basis choice doesn't get in the way of any intervening computations, and the classically controlled Paulis can be backdated through any intervening computations. So you don't have to wait for the correction to complete before continuing the computation. This gives an enormously improved ability to trade between a computation using more space or more time. See https://arxiv.org/abs/1210.4626 and https://arxiv.org/abs/1905.08916 .

enter image description here

$\endgroup$
14
  • $\begingroup$ Thanks for your answer. Your answer is perhaps a bit too technical for my current knowledge. Hence I have a first basic question: Would you agree with (A): if the errors only occur at the physical level (i.e. less than $t$ physical errors occur), we simply perform the computation in another Pauli frame and we don't care of which sequence of gates are happening at the logical level (i.e. we don't care correcting quickly). The trouble might only occur when more than $t$ physical error occur. $\endgroup$ Apr 8, 2023 at 18:00
  • $\begingroup$ If (A) is correct, I call (B) the situation where more than $t$ physical error occurs. In such a case we might have a logical error occuring. What you seem to say here is that even if there is a non-Clifford gate at the logical level we might not care correcting quickly because we can set up "delayed choices". I am not fully understanding why but is it at least what you suggest here? $\endgroup$ Apr 8, 2023 at 18:02
  • $\begingroup$ @MarcoFellous-Asiani In practice, it's impossible to actually know which Pauli errors are present as you actually execute the non-Clifford gate, because those Pauli errors could occur at the very moment before you start it. Even worse, the decoding process that is figuring out which errors occurred can be lagging behind what the quantum computer is actually doing by several rounds of measurements. So there's actually lots of time for Pauli errors to sneak into the non-Cliffords. It doesn't matter whether there's more or less than t, the same issues apply. $\endgroup$ Apr 8, 2023 at 18:33
  • $\begingroup$ I understand what you say apart from the last sentence. Assuming less than $t$ (weight-1) errors damaged my qubit, we might not know "in time" which physical error happened (for the same reasons as your examples), but we wouldn't care as well as it just means the computation is occurring in another code space. We would just have to re-interpret the measurement at the end (after the final measurements, we wait a bit for the classical processing to keep up, then we interpret the measurements). If the error was a logical one (hence more than $t$ errors), things are less clear to me[...] $\endgroup$ Apr 8, 2023 at 18:44
  • 1
    $\begingroup$ @MarcoFellous-Asiani That is not a logical error. That is just drift in the tracked Pauli frame. And yes, enough drift can exchange the on-quantum-computer representations of logical |0> and logical |1>. But it's a mistake to assume that there's only a problem if there's a lot of drift; even a little bit of drift has to be accounted for or else you will get catastrophic error amplification. For example, transversal Cliffords spread drift between qubits. There's no hard boundary where the drift goes from "not logical error" to "logical error". $\endgroup$ Apr 8, 2023 at 19:06

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.