Computation and verification are different tasks
A quantum circuit can transform a superposition and then return a classical measurement result. Complexity theory asks for a family of such computations whose resources grow in a controlled way with the length of the input. A second question allows a prover to supply a state that helps a quantum verifier accept a yes-instance. The verifier still has to reject a no-instance against every purported state.
We discuss decision problems, represented as languages . A circuit acts on a basis encoding of the classical input. A complexity-class inclusion is a statement about all input lengths, not about one fixed-size device or an experiment that happened to succeed once.
Uniform quantum circuits and BQP
Fix a finite universal gate set with computable entries, for example one containing Hadamard, , controlled-NOT and standard reversible classical gates.
Definition 6.1.1
(Polynomial-time uniform family)
A family of circuits is polynomial-time uniform if a deterministic classical algorithm, on input , outputs a description of in time polynomial in .
Hence the circuit has polynomially many gates and wires. The circuit is fixed for the length ; the particular input is supplied on its input wires. The finite gate set avoids treating an arbitrary real rotation with unlimited precision as one free operation. Here universal means approximately universal. For standard fixed finite gate sets satisfying the usual inverse and universality hypotheses, the Solovay–Kitaev theorem gives efficient approximation with polylogarithmic dependence on inverse accuracy. Approximating polynomially many gates to sufficiently small inverse-polynomial error preserves a constant decision gap, with polynomial overhead. We cite this gate-set equivalence rather than proving it here.
Definition 6.1.2
(BQP)
A language is in BQP if a polynomial-time uniform family of polynomial-size quantum circuits, supplied with and polynomially many ancillas, has a designated output qubit such that
Acceptance means measuring the designated qubit in the computational basis and obtaining 1. The probability is determined by the circuit and measurement, not by a probability distribution assumed on inputs. Intermediate measurements can be deferred using standard circuit constructions; this definition uses a final measurement. The constants express a fixed gap and are not a requirement of exact answers.
Worked example 6.1.3
(Parity is in BQP)
A uniform reversible circuit can compute the parity of into an initially zero output bit by applying controlled-NOT from each input bit to the output. It accepts odd-parity strings and rejects even-parity strings with certainty. Thus parity is in BQP, but the example does not demonstrate a quantum speedup: this particular problem is also easily solved classically.
Common mistake
(Dropping uniformity from the definition)
Requiring only polynomial-size circuits, without uniform generation, would make some undecidable languages efficiently decidable. Let be any set and define the unary language . For each separately, a size- circuit can check whether the input is and use a hardwired bit indicating whether . If is uncomputable, these choices cannot be produced even by a computable circuit generator. Indeed, computably generated circuits over computable gates with a bounded error gap would give an algorithm deciding : generate the circuit and approximate its finite-dimensional acceptance probability sufficiently closely, even if that simulation takes exponential time. Polynomial size without uniform generation is a different, nonuniform resource model.
Quantum witnesses and QMA
Fix polynomials bounding a witness length , ancilla length and verifier circuit size. A polynomial-time uniform family receives the classical input , a -qubit witness state , and fresh zero ancillas. The witness is any density operator on its register: it may be mixed or entangled across its qubits. A mixed witness also describes the verifier’s reduced state when a prover retains an entangled external system. After the circuit, measure the designated output qubit; let be the probability of outcome 1.
Definition 6.1.4
(QMA)
A language is in QMA if such a verifier has both properties for every classical input :
- Completeness: if , there exists a witness with .
- Soundness: if , every witness satisfies .
The order of the quantifiers matters. The yes-case requires one good state; the no-case must withstand arbitrary states, including superpositions and mixed states. The verifier must be uniformly generated and run in polynomial size. The definition does not require the witness to be efficiently preparable by the verifier, nor does it supply a method to find it. More generally, a promise problem consists of disjoint sets of yes- and no-inputs; the verifier need only satisfy the two conditions on those sets and may behave arbitrarily outside the promise. For a language, the no-set is the complement of the yes-set.
For a fixed input , the acceptance probability can be written for a positive operator on the witness register. It is obtained by preparing the fixed input and ancillas, conjugating the output-acceptance projector by the verifier, and taking the corresponding matrix element on those fixed registers. By the finite-dimensional spectral theorem, the maximum over density operators is the largest eigenvalue of and is attained by a pure eigenstate. Thus allowing mixed states does not change the existential optimum, but soundness must still cover all states. This mathematical characterization does not assert that diagonalizing is efficient.
Counterexample mode
Testing basis witnesses is not soundness
Claim: if every computational-basis witness is rejected with probability at least on a no-instance, soundness holds. Let be the acceptance operator for a one-qubit witness. It can be implemented by testing for and, conditional on success, accepting on an independent fair coin. Each basis state is accepted with probability , within the QMA no-instance bound . Yet is accepted with probability , violating that bound. Even testing every computational-basis witness does not establish soundness against arbitrary quantum witnesses; the claim fails, and the repair is to bound the largest eigenvalue of , here .
Basic containments
Proposition 6.1.5
(Basic containments)
and .
Proof
(Reversible simulation, ignored witnesses and classical witnesses)
For BPP, represent the polynomial-time randomized classical algorithm by a uniform polynomial-size classical circuit , where is a polynomial-length uniform random string. Reversibly compute it while retaining , for example by recording intermediate Boolean gate values with reversible gates. Prepare each random bit with a Hadamard gate. The resulting state has orthogonal branches labeled by ; measuring the output gives exactly the classical acceptance probability. This establishes BPP BQP. A deterministic polynomial-time computation is a special case.
For BQP QMA, the verifier runs the BQP circuit and ignores a fixed-size witness register. On a yes-instance any witness works, and on a no-instance every witness gives the same rejecting bound.
For NP QMA, let a deterministic polynomial-time classical verifier have polynomial-length witnesses. The quantum verifier uses a classical reversible permutation circuit controlled by , leaving the witness register unchanged while computing into the output. If is a yes-instance, the classical accepting string encoded as is an accepted quantum witness. For fixed its acceptance operator is . Therefore, for every density operator , including a mixed or entangled witness, . If is a no-instance every is zero, so every quantum witness is rejected.
Worked example 6.1.6
(A satisfiability verifier and a coherent witness)
Take . Only the assignment satisfies it (), so . The classical witness is accepted with probability . The coherent witness is accepted with probability , since . For an unsatisfiable formula, such as , and every quantum witness is rejected. This proves membership of the satisfiability language in QMA through NP; it does not prove that a quantum computer can find such an assignment efficiently.
Common mistake
(Reading a containment as a separation)
These containments do not establish , , or . None of these comparisons follows from the arrows just proved. A query-complexity separation in an oracle model also needs its oracle qualification; it is not automatically a separation of the unrelativized classes.
Error reduction and its witness subtlety
Proposition 6.1.7
(Error reduction for BQP)
If a language has a BQP circuit family with the gap versus , then for odd running independent copies and taking the majority gives error at most on every input.
Proof
(Majority of independent runs)
Run independent copies on the same classical input using fresh registers and take their majority by a reversible classical circuit before the final output measurement. When the original success probability is at least , the probability that a majority is wrong is at most by Hoeffding's inequality. The analogous bound applies to a no-instance. Taking odd polynomial in the desired confidence parameter gives exponentially small error with polynomial overhead. The input is a classical basis state that can be copied; this is not a procedure for cloning an unknown quantum state.
Worked example 6.1.8
(Majority of three, exactly and by the bound)
With success probability per run, the majority of is correct with probability . The Hoeffding bound is larger than and therefore says nothing here: the bound is useful only once is large. To guarantee error at most one may take , which is odd with ; for this gives .
For QMA, naive repetition cannot assume a cheating prover supplies independent witnesses.
Theorem 6.1.9
(Parallel repetition for QMA)
Take witness registers, so the witness length becomes , run the verifier once on each register, and accept when a majority accept. Then on a yes-instance some witness is accepted with probability at least , and on a no-instance every witness, entangled or not, is accepted with probability at most .
Proof
(Diagonalize the one-copy acceptance operator)
For fixed , diagonalize the one-copy acceptance operator . Each one-copy test has acceptance effect and rejection effect . These effects act on separate registers, so the majority-accept operator is diagonal in a tensor-product eigenbasis of . On a no-instance soundness bounds every eigenvalue of by ; each basis tuple gives independent, not necessarily identically distributed, Bernoulli outcomes whose success probabilities are at most . Hoeffding bounds its majority acceptance by , and any entangled density operator gives a convex combination of these diagonal values. On a yes-instance the largest eigenvalue is at least ; the prover can supply the product of a corresponding good eigenvector. This is not cloning by the verifier.
Proof X-ray
How diagonalization removes the entangled prover
A cheating prover may entangle the registers, so the test outcomes need not be independent. The non-obvious move is to diagonalize before looking at the witness: the majority-accept operator is a function of the commuting one-copy operators, so in a product eigenbasis it is diagonal, and the acceptance probability of any witness is a convex combination of diagonal entries. Each diagonal entry is an ordinary probability of a majority of independent Bernoulli trials, to which Hoeffding applies. Soundness is used only through the eigenvalue bound , which is where a bound on a single tested witness would fail. Without this step one could argue only for independent witnesses.
A stronger result of Marriott and Watrous, Quantum Arthur-Merlin Games states that QMA completeness and soundness errors can be reduced exponentially with polynomial verifier overhead without increasing witness length. We cite that amplification theorem here rather than proving its construction. Its stronger feature is preserving the original witness length. More generally, efficiently specified completeness and soundness thresholds separated by at least an inverse polynomial can be amplified with polynomial overhead. Amplification does not turn a quantum witness into a classical one.
Both lie inside classical polynomial-space computation, which bounds how large they can be.
A natural next question
How do BQP and QMA compare with classical classes?
Both lie inside classical polynomial-space computation, which bounds how large they can be.
Standard results place and , where is the class of languages decided by a polynomial-time probabilistic algorithm that is correct with probability strictly greater than . These are upper bounds only: it is not known whether differs from , nor whether either quantum class equals .
Practice with solutions
Quick check
(A uniform circuit family accepts every yes-input with probability and every no-input with probability . Does it satisfy the stated BQP thresholds, assuming polynomial size and zero-initialized ancillas as needed?)
Compare with and .
Solution · Answer
Yes: and , under the stated uniformity and resource assumptions.
Quick check
(A proposed QMA verifier accepts one tested witness with probability on a no-input. Is that enough to prove soundness?)
Recall the quantifier in the soundness condition.
Solution · Answer
No. Soundness must hold for every witness, not just one; a different state might be accepted with high probability.
Quick check
(Explain how leaving the witness register unchanged makes the NP-to-QMA verifier's acceptance operator diagonal and controls acceptance of coherent witnesses.)
Write the acceptance operator in the basis of witness strings.
Solution · Answer
The reversible verifier leaves the witness unchanged and has diagonal acceptance operator . For every density operator its acceptance probability is ; on a no-instance all terms vanish.
Quick check
(A verifier's acceptance operator on one witness qubit is . Find the maximum acceptance probability over all density operators and a witness attaining it.)
Use the largest eigenvalue.
Solution · Answer
The largest eigenvalue is , achieved by . A density operator is a convex combination of pure states, and no state exceeds the largest eigenvalue.
Quick check
(Given only , can one infer that the containment is strict or that NP is contained in BQP?)
Ask what an inclusion alone says.
Solution · Answer
Neither follows from that inclusion. An inclusion alone does not prove strictness, and it says nothing by itself about an NP-to-BQP inclusion.
Quick check
(Give an odd number of BQP repetitions sufficient to make the Hoeffding error bound at most for a positive integer .)
Solve .
Solution · Answer
Choose . It is odd and , so . This is a sufficient bound, not necessarily the least possible repetition count.
Exercise 6.1.10
(Suppose on a no-instance. For three parallel verifier copies, show that accepting on at least two outcomes has probability at most even for an entangled three-register witness.)
CoreProof
Solution(3)
- 1
Diagonalize the one-copy operator
Key step
In the tensor-product eigenbasis of , the three-copy majority-accept operator is diagonal, so the acceptance probability of any witness is a convex combination of diagonal entries.
- 2
Bound one diagonal entry
A basis triple gives independent acceptance probabilities . The probability of at least two successes is coordinatewise nondecreasing in each , so it is at most its value at :
Because: Every eigenvalue of is at most .
- 3
Conclude for entangled witnesses
∎Any density operator, entangled or not, yields a convex combination of diagonal values each at most , so the acceptance probability is at most .