= Solution
<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. \b[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>.
Back to article page
