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

The process is classically strongly efficiently simulatable if a deterministic classical algorithm can compute the probability of any specified $K$-bit output string to requested additive precision $2^{-m}$ in time polynomial in $n$, the circuit description, and $m$. This is strong classical simulation of a quantum circuit, and is stronger than merely sampling its output.

For the first output qubit,A Clifford circuit maps the Pauli observable $Z_1$ under conjugation to a tensor-product Pauli operator $\pm P_1\otimes \cdots \otimes P_n$, found by propagating it backward through the circuit in polynomial time. Since the input is a product state,Each factor is efficiently computable, so both one-bit output probabilities are strongly simulatable. This is Heisenberg propagation of a Pauli observable through a Clifford circuit.

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