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

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.