Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 324 / 4 / iii

Take any bounded-error polynomial-size quantum circuit for a language in $\mathrm{BQP}$ and express it using $H,CX,S,T$. Replace each $T$ gate by the supplied $T$-gadget. Before measurements and conditional corrections, the resulting circuit uses only Clifford gates and has a product input consisting of the original input and one magic state $|A⟩$ per gadget.

Consider the branch in which all $t=\mathrm{poly}(n)$ gadget measurements return zero. No conditional $S$ corrections are then needed, so the ancilla measurements may be deferred to the end. This branch has known probability $2^{-t}$, and conditioned on it the remaining output is exactly that of the original universal circuit.

The assumed simulator applies with $K=t+1$: ask it for the joint probabilitiesUsing polynomially many bits of requested precision, computeThe usual bounded-error gap separates yes instances from no instances, so this conditional probability decides the language deterministically in polynomial time. Hence $\mathrm{BQP}\subseteq \mathrm{P}$. The reverse inclusion is immediate because a quantum computer can implement classical deterministic computation, and therefore