Quantum complexity theory

Quantum complexity theory studies resources needed by quantum circuits and quantum algorithms, including time, workspace, and quantum query complexity. Its models specify which input oracles and gate implementations are available; counting oracle calls is different from counting all elementary gates.

BQP is the class of promise problems decided by uniform polynomial-size quantum circuits with bounded error. Completeness $2/3$ and soundness $1/3$ are conventional; BQP error reduction shows that other fixed separated thresholds give the same class.

Independent runs of a BQP algorithm with fresh ancilla qubits can be combined by a classical threshold rule. If completeness exceeds soundness by $\gamma$, a Hoeffding inequality bounds the error after $r$ runs by $e^{-r{\gamma }^2/2}$. Polynomial repetition handles inverse-polynomial gaps. This does not automatically preserve the restricted gate and measurement rules of a stoquastic circuit.

A quantum witness is a polynomial-size quantum state supplied to a verifier as evidence for a YES instance. The verifier fixes its own ancilla qubits independently. Pure quantum witnesses suffice when maximizing a linear acceptance functional on density operators. Quantum witnesses are not generally restricted to basis vectors or product states.

StoqMA is a restricted quantum-verifier class using stoquastic circuits and polynomial-size quantum witnesses. A YES instance has a quantum witness accepted with probability at least $a$; on a NO instance every quantum witness has acceptance at most $b$, with an inverse-polynomial gap $a-b$. An optimal quantum witness can be chosen with nonnegative amplitudes, since the witness acceptance operator is entrywise nonnegative. The quantum witness is generally a superposition, rather than a computational basis vector. The stoquastic acceptance floor explains the lower limit $b\ge 1/2$ for a nontrivial soundness promise.

QMA is the class of promise problems with a polynomial-size quantum witness checked by a uniform polynomial-size quantum circuit. YES instances have an accepting witness with probability at least $2/3$; NO instances have acceptance at most $1/3$ for every witness, including mixed states. The verifier's acceptance is linear in the witness density operator. Inverse-polynomial or exponentially small error can be obtained through QMA error reduction.

For quantum witness embedding $J$, verifier unitary $U$ and accepting projector $\Pi$, the witness acceptance operator is the positive contraction $F=J^{†}{U}^{†}\Pi UJ$. The maximum acceptance over normalized quantum witnesses is ${\lambda }_{\max }(F)$ by the Rayleigh quotient. Restricting to basis quantum witnesses only tests its diagonal entries and need not find that maximum.

For a positive witness acceptance operator on dimension $D$, large trace powers approximate its largest eigenvalue. With an $m$-qubit QMA quantum witness and $d=2m+2$, the usual NO instances give $\mathrm{Tr}(F^d)<2^{-d}$ and YES instances give a value above $2^{-d}$. A closed product-index expansion computes the trace by recomputation with polynomial storage, avoiding logarithms and roots in a real-arithmetic implementation.

Starting from completeness $2/3$ and soundness $1/3$, run an odd number $r$ of parallel copies and take majority. The QMA parallel repetition with entangled witnesses argument proves soundness for arbitrary repeated witnesses. Exponential Markov's inequality gives majority error at most $(2\sqrt{2}/3{)}^r$. Hence $O(\log (1/ϵ))$ copies suffice for error $ϵ$, with polynomial overhead when the target error is inverse-polynomial or exponentially small in input length.

Independent verifier circuits on $r$ witness registers induce a threshold acceptance effect built from tensor products of $M$ and $I-M$, where $M$ is the quantum verifier acceptance operator. In a product eigenbasis of $M$, the effect's eigenvalues are threshold probabilities for independent Bernoulli random variables with parameters given by the selected eigenvalues of $M$. Bounding every parameter on a NO instance bounds the effect's operator norm, even if the actual submitted witness is entangled. Independence is used only for the spectral calculation, not assumed for the witness.

A verifier with clean ancillas and a designated output measurement induces an effect $0\le M\le I$ on the witness register. Its acceptance probability is $\mathrm{Tr}(M\rho )$, and the largest possible acceptance is $\Vert M\Vert$. Spectral bounds on $M$ make the soundness quantifier over all witnesses, including entangled repeated witnesses, explicit.

The quantum query complexity of a task counts uses of an input oracle by a quantum circuit, for a specified success probability. Known gates and workspace operations are not counted as oracle queries, although they contribute to the circuit's full runtime. An efficient query bound therefore need not, by itself, be an efficient gate bound.

A quantum oracle supplies coherent access to a function through a specified unitary operator. For a function with binary string output, the standard construction retains the input and adds the output into an answer quantum register by bitwise exclusive or. This operation is its own inverse, even when the function is not injective. A Boolean quantum oracle is the single-output-bit case; Simon's algorithm uses several answer qubits. Other encodings, such as a modular-addition quantum oracle or a phase gate encoding, require their own explicit query conventions.

A phase oracle encodes a Boolean function in the signs of computational basis states. Its diagonal entries have modulus one, so it is a unitary operator. The usual convention $O_f$ changes the sign when $f(x)=1$. A complemented convention $U_f|x⟩=(-1{)}^{f(x)\oplus 1}|x⟩$ instead changes the sign when $f(x)=0$, with $U_f=-O_f$; $\oplus$ denotes exclusive or. The two conventions differ by a global phase when used without coherent control, but the global phase of a controlled quantum gate makes that difference observable when the quantum oracle is controlled.

An unrestricted Boolean function on $M>2$ inputs cannot be classified as constant or nonconstant with certainty using a single phase oracle query, even with quantum ancillas. Write a purified query input as $|\Psi ⟩={\sum }_x|x⟩|a_x⟩$ with $p_x=\Vert a_x{\Vert }^2$ and ${\sum }_x{p}_x=1$. The zero constant function leaves it unchanged; the function supported only at $j$ produces a vector with inner product $1-2p_j$ with it. Perfect discrimination of pure states requires orthogonality, forcing $p_j=1/2$ for all $j$ and thus $M=2$, a contradiction. This is an exact quantum query complexity obstruction for all nonconstant inputs, rather than the restricted promise used by the Deutsch-Jozsa algorithm.

After $T$ input-bit queries, every probability amplitude is a polynomial of degree at most $T$, because the bit-query matrix entries are affine in the input bits. An acceptance probability is a sum of squared absolute amplitudes and has polynomial degree at most $2T$. Multilinear reduction on the Boolean cube does not increase degree. Exact acceptance therefore implies $Q_E(f)\ge \lceil \mathrm{deg}(f)/2\rceil$. For bounded error the acceptance polynomial only approximates the Boolean function; its exact representing degree is not the relevant bound.

The least worst-case number of input-oracle calls made by a quantum circuit that computes a Boolean function with zero error on every input. Known unitary gates and classical processing do not count toward this quantity; their runtime is a separate cost.

One exact parity query determines whether the first two bits agree. If they agree, a second query reads one of them; otherwise it reads the third bit. Those values respectively determine the three-bit majority function. The matching lower bound follows from its degree-three multilinear polynomial.

Given a function $f$ with an $m$-bit output, accessed through the unitary operator $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$, quantum collision finding asks for distinct inputs with equal outputs. Here $\oplus$ is bitwise exclusive or on the $m$-bit answer quantum register. The distinctness requirement excludes the uninformative pair $(x,x)$. For a two-to-one function on $N$ inputs, Grover search algorithm methods yield a cube-root quantum query complexity, despite a square-root cost for finding a partner of just one preselected input.

Query a known set of $m$ inputs and store its output table. If no function collision occurs there, each of its $m$ distinct outputs has exactly one partner in the complement, for a two-to-one function. A compute-phase-uncompute construction marks those partners using two function queries and reversible table comparison. Known-subset Grover search then uses $O(\sqrt{(N-m)/m})$ such phase queries. Including table preparation and a final verification query givesChoosing $m\asymp N^{1/3}$ balances both terms and gives $T(m)=O(N^{1/3})$. The Grover rotation angle rounding bound gives success tending to one. This is a query bound; it does not make reversible table lookup free in a gate or physical-memory cost model.