Past exam of the mathematics course of the University of Cambridge / 2014 / iii / Paper 63 / 2

BQP consists of promise problems decided by a uniform family of polynomial-size quantum circuits. On input $x$, with polynomially many zero-initialized ancilla qubits, a designated output measurement accepts with probability at least $2/3$ on YES inputs and at most $1/3$ on NO inputs. Uniformity means a classical polynomial-time procedure produces the quantum circuit description from the input length, or equivalently produces the verifier quantum circuit with $x$ supplied as input.

For BQP error reduction, run independent copies with freshly initialized registers. If the completeness and soundness thresholds are any constants $a>b$, accept when the fraction of accepting trials exceeds $(a+b)/2$. A Hoeffding inequality bounds either error by $\exp [-r(a-b{)}^2/2]$, with $r$ repetitions. The threshold need not be a simple majority when both $a$ and $b$ lie on the same side of $1/2$.

Choosing $r$ sufficiently large gives the usual $2/3,1/3$ thresholds, or any other fixed separated thresholds. Even an inverse-polynomial gap can be amplified using polynomially many repetitions. Classical threshold evaluation can be incorporated into the uniform computation. Thus fixed separated acceptance probabilities define the same BQP class. This argument concerns unrestricted BQP quantum circuits and does not assume such amplification is available for restricted stoquastic circuits.

The class $C$ uses polynomial-register real-arithmetic computation: its storage restriction counts real registers, without limiting their precision or the running time. Use the usual decision-model interpretation that computed real values may be compared with fixed thresholds, and that the fixed universal gate set's real constants are available. Without a way to test values, arithmetic instructions alone would not specify the intended decision model.

Let a BQP quantum circuit use $q=\mathrm{poly}(n)$ qubits and $T=\mathrm{poly}(n)$ gates. A matrix element can be evaluated by depth-first quantum circuit path summation:Enumerate the intermediate $q$-bit strings recursively. Store the current strings and loop positions, a partial product, and the partial sum at each depth. There are at most $T$ active levels, using $O(qT)$ registers or bits of loop information, not an exponentially long state vector. Each fixed-locality gate matrix element is computed from its few affected bits. Represent a complex number by two real registers; complex multiplication and addition require only real addition, subtraction and multiplication.

Recompute this amplitude separately for every final string $z$ whose output bit is one, accumulating the Born rule probabilityThe outer enumeration needs only another $O(q)$ bits and a real accumulator. Arbitrarily large running time is allowed, so repeated recomputation is harmless. Compare $p_1$ with $1/2$ to distinguish the promised BQP cases. This proves $\mathrm{BQP}\subseteq C$ using polynomial storage.

The printed probability hint omits the squares of the amplitude moduli. Summing their absolute values alone is not the Born rule and can exceed one. The corrected sum above is necessary for the containment proof. The argument is about the stated real-register model, rather than a claim that exponential-precision numbers are free in an ordinary bit-cost model.

QMA is the class of promise problems for which a uniform polynomial-size quantum circuit checks a polynomial-size quantum witness. A YES instance has some quantum witness accepted with probability at least $2/3$; on a NO instance every quantum witness is accepted with probability at most $1/3$. The verifier initializes its own ancilla qubits to zero. Mixed quantum witnesses do not improve the maximum because acceptance is linear in their density operator.

For a verifier $U_x$ and quantum witness embedding $J|w⟩=|w⟩|0\cdots 0⟩$, define the witness acceptance operatorThe Rayleigh quotient gives ${\max }_{\Vert w\Vert =1}⟨w|F|w⟩={\lambda }_{\max }(F)$. Every entry of $F$ can be recomputed by the polynomial-storage path summation of part (b); no full quantum witness matrix needs to be stored.

Let the quantum witness have $m$ qubits, so its dimension is $D=2^m$. For this positive operator, trace-power witness optimization usesThis is the useful exponentiated form of the supplied logarithmic inequality. Positivity is required; such a logarithmic statement is not true for an arbitrary operator. No logarithms or roots need to be calculated.

Choose $d=2m+2$. On a NO instance,since $2^m(2/3{)}^{2m+2}=(4/9)(8/9{)}^m<1$. On a YES instance, $\mathrm{Tr}(F^d)\ge (2/3{)}^d>(1/2{)}^d$. Thus comparison of $2^d\mathrm{Tr}(F^d)$ with one distinguishes the cases using only multiplication and a final comparison.

Evaluate the trace byThere are $d=O(m)$ active quantum witness indices, each requiring $m$ bits. Accumulate one product at a time and recompute its matrix entries as required. Together with the verifier path workspace, this uses polynomially many real registers. The potentially enormous time and the numerical precision are unrestricted in $C$. Therefore $\mathrm{QMA}\subseteq C$, without solving an exponentially large eigenvalue problem by storing its matrix.