In the paper Universal quantum computation with ideal Clifford gates and noisy ancillas, it is claimed that a circuit composed by Clifford gates, plus a so-called "magic state", can perform any quantum computation.

This paper is based on the formalism developed for fault tolerance. However, the claim above does not have to do with fault tolerance, nor with "noise". Indeed, the section III, which discusses the universal quantum computation, does not even mention the "noise" and the magic state is simply a well-defined pure state. It looks like it is possible to build any circuit using Clifford gates and simulating the T gate by using the so-called magic state, which is simply $\alpha\left|0\right>+\beta\left|1\right>$ with well defined $\alpha$ and $\beta$ (together with a particular procedure and additional Clifford gates).

So I would like to understand what I miss, if I do not understand the discussion about the fault tolerance and noisy qubits. Looking in literature, I feel that I actually miss something. For example, here I read this sentence:

quantum computers with magic states will most likely have the vast majority of its usable qubits be used for the distillation of magic states

Thus it seems that this "distillation" is needed: is it simply the preparation of $\alpha\left|0\right>+\beta\left|1\right>$ with known $\alpha$ and $\beta$?

So I would like to have a sketch of the idea of the relation between the discussion on universal computation and fault tolerance, or a reference discussing this idea more in depth but without relying too much on the language of fault tolerance.


1 Answer 1


From Sec. V on in the Bravyi-Kitaev paper, it is all about noise - in particular magic state distillation, which is the process of distilling the magic state from many copies of some noisy state $\rho$.

Let us zoom out a bit. The magic state gadget replacing the $T$ gate looks like the following:

If we can do the Clifford gates and the measurement fault-tolerantly, which we can for a suitable stabilizer code, this circuit is fault-tolerant. However, the problem is that the preparation of the magic state $|T\rangle = \frac{1}{\sqrt{2}}(|0\rangle + e^{i\pi/4}|1\rangle)$ might not be.

So how would you prepare such a state?

  1. First, one can observe that $|T\rangle$ is the +1 eigenstate of a suitable Clifford unitary $U$. Hence, by preparing e.g. a logical $|0\rangle$ state and then measuring in its eigenbasis (applying $U^\dagger$ to $|0\rangle$, then measuring in the computational basis), we get either the +1 or -1 eigenstate as post-measurement state. Post-selecting on the +1 outcome results in $|T\rangle$. This is actually fault-tolerant, but the physical error rate can be quite high, so you would have to repeat very often (see e.g. the discussion on p. 3 in "Roads towards fault-tolerant universal quantum computation" by Campbell, Terhal, and Vuillot).

  2. You prepare a noisy approximation $\rho$ to $|T\rangle$, somehow. Then you use a magic state distillation protocol to distill a better approximation to $|T\rangle$ from $\rho^{\otimes n}$. In fact, it is enough to use stabilizer protocols only, i.e. protocols which only use stabilizer circuits. This is also interesting from a foundational perspective: Which states can you actually distill and which not? This is discussed in the Bravyi-Kitaev paper. Unfortunately, magic state distillation is also very costly.

I think the discussion of fault-tolerance in Nielsen & Chuang is not such a bad reference to begin with. In particular, Chapter 10.6 and the section "Fault-tolerant $\pi/8$ gate" on page 485. Unfortunately, magic state distillation is not discussed there.

  • $\begingroup$ Let us forget about the fault tolerance for a moment and imagine that we can prepare any initial state, with suitable ancillary qubits, exactly. Then it seems that we can perform any quantum computation with Clifford gates. This can be done efficiently with classical computation. Where is the error in this reasoning? (I know, there must be an error!) $\endgroup$ Jan 26 at 9:57
  • 2
    $\begingroup$ @DorianoBrogioli Efficient clifford simulation requires you to start in the computational basis state. It's not impossible to adjust it to work with magic states, but when you do you find that the costs are exponential in the number of magic states you use. For example, the cost might scale like 1.2^n where n is the number of T states. So it doesn't scale to full sized computations, which use billions of T gates. $\endgroup$ Jan 26 at 11:13
  • $\begingroup$ Do you have a paper to suggest, to read about this exponentially slow method? $\endgroup$ Jan 26 at 12:55
  • 1
  • $\begingroup$ @DorianoBrogioli there's a weak simulation algorithm in "Simulation of quantum circuits by low-rank stabilizer decompositions" (for pure states only) and "Quantifying Quantum Speedups: Improved Classical Simulation From Tighter Magic Monotones" (mixed states) $\endgroup$ Jan 26 at 15:49

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.