When reading this question and quickly reading some of the linked papers, I wondered why was the number of $T$ gates specified along the number of controlled-$X$ gates.

I've often read that implementing a controlled-$X$ gate was more costly than implementing single-qubit gates, though I never got the explanation as to why this is true. Assuming this however, I can understand why this number is of importance.

Concerning the number of $T$ gates however, what's the motive behind it? My intuition is that it gives an idea of how deep the circuit is, since $T$ is required to precisely approximate the desired gates, but if it is the case, why bother with the number of $T$ gates rather than with the circuit depth directly?


If you are trying to implement a fault-tolerant quantum computation, you need to implement unitary gates that act on logical qubits. You typically have a finite set of these gates available, and what you really care about is making your operations in such a way as to keep the fault-tolerant threshold as small as possible.

If you calculate a fault-tolerant threshold for a concatenated scheme, you can roughly think of this as taking each gate in your gate set, specifying how each of them is made on the physical qubits (including a round of error correction before & after), and (roughly speaking) evaluating the size (=depth$\times$width, think of it like the number of places where an error could occur) of that circuit. The fault tolerant threshold is determined by the gate in the set that has the largest size.

Now, a two-qubit gate has much larger width than a single-qubit gate, so it might be the critical case. However, many error correcting codes have most of their unitaries implemented using transversal operations. This makes for particularly small circuit depths. However, the Eastin-Knill theorem says that not all unitaries in a universal set can be implemented transversally. So there will be (at least) one gate in the set with a much higher depth, and that may be your critical case. In many implementations, the non-transversal gate is chosen to be the T gate.

So, in a typical implementation, you know that either the c-NOT or the T will be the dominant contributer to the fault-tolerant threshold. Simplifying these implementations, or reducing the number of applications of these gates, potentially has a huge impact on how efficiently your quantum computer runs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.