2
$\begingroup$

Suppose I have a single block $n$-qubit stabilizer code that can correct a weight 1 error (so the distance is $d=3$). If I apply a $1$-transversal gate of the form $U = U_1 \otimes U_2 \otimes \cdots \otimes U_n$, then if there was 1 error before I applied the gate, there will still only be 1 error after I apply the gate. So $U$ is called fault tolerant because error correction works before and after applying $U$.

On the other hand, consider a $2$-transversal gate of the form $V = V_1 \otimes V_2 \otimes \cdots \otimes V_N$ where each $V_i$ acts on either 1 or 2 qubits, for example $\mathrm{CNOT} \otimes X \otimes Y$. Then if there is 1 error before we apply $V$, there could be 2 errors on the output. This means $V$ is not fault-tolerant (as usually defined) because we could correct the error before we applied $V$ but we could not after we applied $V$.

However, if I simply choose a code with a larger distance, say $d=5$ (which can correct 2 errors or less) then it seems like $V$ should be considered "fault-tolerant". Because if a weight 1 error happens and we apply $V$ then the output will have a maximum of 2 errors. And because the code can correct 2 errors we can still undo this correctly. However, the "fault-tolerant distance" of the code has changed - we can only tolerate a single error (if 2 errors happen then after we apply $V$ there could be 4 errors). So even though the code has $d=5$, the "fault-tolerant distance" is $d_{FT}=3$.

Is my understanding correct? I really have never seen this mentioned anywhere but it seems fairly obvious (unless I am missing something)? Reference?

$\endgroup$

2 Answers 2

1
$\begingroup$

I think there is no common agreement on what $U$ being fault tolerant exactly means. It was initially defined as "the quantum [system] can function successfully even if errors occur during the error correction".

To some people it will mean "$U$ does not spread errors within one code block" (see this answer for example quoting this paper).

A more or less equivalent formulation could be "A correctable amount of errors before is the operation is always mapped to a correctable amount of errors after the operation". The slight difference being that error spreadings can happen if they always cancel out (e.g. thanks to stabilizers). As an example, I would argue that stabilizer measurements can spread errors towards the code. Consequently, they are considered fault tolerant only if the measurement schedule is chosen to avoid the so-called hook errors.

An even broader definition could be "A correctable set of errors before the operation is mapped to a correctable set of errors after the operation". Indeed, error spreading induces correlation which could be used by a decoder to correct errors despite some of them having spread.

As the answer I quoted points out, fault tolerance is a property of an operation (usually defined over a class of codes with arbitrary large distance). I do not think the fault tolerant property of your $V$ would depend on whether it is applied on a $d=3$ or $d\geq 5$ code.

Your notion of "fault tolerant distance" want to grasp how badly an operation impact the code performance. I believe it is close to the minimal-weight error mechanism that induces a logical error in a circuit experiment i.e. the minimal-weight error in the circuit space-time decoding graph.

You can probably say that a 2-transversal operation is fault-tolerant if you show that you are able to decode any circuit using it without hindering (or at least without hindering too much) the overall distance of the computation.

$\endgroup$
1
$\begingroup$

I think you are right that such a 2-local gate would be fault tolerant with "fault-tolerant distance 3" as you say.

I think the reason that you don't see this idea around is that it is more complicated than 1-local transversal gates without much gain. One might hope, for example, that you could get a 2-local gate of the form $ V_{1,2} \otimes V_{3,4} \otimes V_{5,6} \otimes V_7 $ on the Steane code that implements logical $ T $ gate. This would be very interesting because such a gate would have $ d_{FT}=2 $ that is, if you start with a $ 1 $ qubit error (which detectable) and then apply any of the 1-local transversal Clifford gates then you still only have 1 error, which is still detectable (indeed even correctable) and even if you apply the 2-local gate implementing logical $ T $ it would still only spread the 1 qubit error to at most 2 qubits so it would still be detectable. This would be very interesting because it would be an effectively error detecting code with a universal fault tolerant gate set.

Unfortunately, this possibility is ruled out by Eastin-Knill. Applying this $ V_{1,2} \otimes V_{3,4} \otimes V_{5,6} \otimes V_7 $ is essentially applying a 1-local transversal gate on a code that encodes one qubit into 3 physical 4-dits and 1 physical qubit. One can run through the proof of Eastin-Knill and see that it still forbids universality in this case. If one goes to $ 3 $-local qubit gates however then $ d_{FT}=1 $ for $ 3 $-local gates (in other words if some of the qudits are size $ 8 $ then the code is no longer error detecting on all physical qudits) so Eastin-Knill no longer applies and there exist $ 3 $-local qubit gates implementing logical $ T $ on the Steane code, for example the gate $ \mathrm{CNOT}_{12} \mathrm{CNOT}_{27} \mathrm{T}_7 \mathrm{CNOT}_{27} \mathrm{CNOT}_{12} $ acting on physical qubits 1,2,7 described in the code-swtiching paper https://arxiv.org/abs/1309.3310

Something similar occurs with, say, the $ [[23,1,7]] $ Golay code, which is close to being universal in that $ b $ blocks is a $ [[23b,b,7]] $ code which implements the $ b $ qubit Clifford group transversally. One might hope that there is some 2-local or 3-local way to implement a universal gate set but again we run up against Eastin-Kill. If there were, say, some 3-local physical gate on the $ [[23,1,7]] $ Golay code that implemented logical $ T $ then we would essentially have a $ d_{FT}=3 $ code that implements a universal transversal gate set, but the transversal partition is into qudits all of size $ 2,4 $ or $ 8 $. So we can apply Eastin-Knill to conclude that no 3-local gate can implement a logical $ T $ gate on the $ [[23,1,7]] $ Golay code, indeed a gate must be at least $ d $ local (in this case $ 7 $-local) to implement a logical $ T $ gate and thus combine with the $ 1 $-local gates to make a universal logical gate set.

$\endgroup$
2
  • $\begingroup$ I suspected as much. But what if we had a 2-local gate $U_1$ that implemented say $T$ and another 2-local gate $U_2$ that implemented say $H$ but the partition support of each gate was different. For example, say $U_1$ acted locally on subsystems $\{1,2\}$, $\{3,4\}$, $\{5,6\}$, $\{7\}$ but $U_2$ acted locally on subsystems $\{ 1,3\}$, $\{2,4\}$, $\{5,7\}$, $\{6\}$. Then Eastin-Knill wouldn't rule out this scenario correct? $\endgroup$ Commented May 5 at 21:23
  • $\begingroup$ @EricKubischta I'm not totally sure but I was also sort of wondering if that might be true. It certainly wouldn't work for something like the Steane code where adding any logical gate outside the Clifford group will give you universality, but yes for something like $ [[11,1,5]] $ code that has fairly small group of logical gates implementable by 1-local physical gates (i.e. has a small what we would normally think of as a transversal gate group) then perhaps with respect to two different 2-local partitions you could get complementary gates like $ H $ and $ T $. I'm just not sure $\endgroup$ Commented May 5 at 22:15

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.