Foundations of Quantum Complexity Theory

A quantum circuit on $n$ qubits is a sequence of instructions $G_1, G_2, \dots, G_T$, where each $G_i$ is either a unitary gate drawn from a fixed finite gate set $\mathcal{G}$, applied to one or two qubits (or a bounded number of qubits — the notion generalizes), or a measurement in the computational basis. The circuit takes an input state, usually $|x\rangle \otimes |0\ranges^{\otimes m}$ where $x$ is the classical input and the extra $m$ qubits are ancillas, applies the gates in sequence, and measures some designated output qubits at the end. The circuit's size is the total gate count $T$; its depth is the number of layers needed if gates acting on disjoint qubits are run in parallel. These two numbers are the quantum analogues of the number of steps and the parallel time of a classical Boolean circuit — the resource quantities complexity theory bounds as a function of input length $n$. The circuit model only makes sense as a complexity-theoretic object once we fix $\mathcal{G}$ to be a small, hardware-plausible set — otherwise "one gate" could secretly encode an arbitrarily powerful operation, trivializing every complexity bound. A gate set is called universal if, for every target unitary $U$ on any number of qubits and every $\varepsilon > 0$, there is a circuit built from $\mathcal{G}$ (with possible ancillas) whose action approximates $U$ to within operator-norm distance $\varepsilon$. Universality is the quantum analogue of the classical fact that {AND, OR, NOT} (or even just NAND) suffices to build any Boolean function: the specific native gates barely matter, because any finite universal set can simulate any other with only a controlled overhead in circuit length. This is what makes "quantum circuit complexity" a well-posed, hardware-independent notion rather than a statement tied to one vendor's instruction set. Finally, because quantum measurement outcomes are inherently probabilistic, "solving a problem" cannot mean "always outputs the right answer with certainty" for problems whose answer is a single bit — instead we adopt bounded-error acceptance: the circuit family must output the correct answer with probability at least $2/3$ (or any constant $> 1/2$) for every valid input, and this success probability can be amplified exponentially close to $1$ by independent repetition and majority vote. This convention mirrors bounded-error randomized classical computation (the class BPP) and is the direct quantum generalization needed to state complexity classes like BQP built on top of this same circuit model, using Uniform Circuit Families indexed by input length exactly as in the classical treatment of P and NP.

Step 1 — Fix the register and the gate set. A computation on inputs of length $n$ uses a register of $n$ input qubits plus $\text{poly}(n)$ ancilla qubits initialized to $|0\rangle$. The gate set $\mathcal{G}$ is finite and fixed in advance — a canonical choice is

where $H$ is the Hadamard gate, $T$ is the $\pi/8$ phase gate, and CNOT is the two-qubit controlled-NOT. This is one of several standard universal sets (others include Toffoli+H, or the continuous set of all one- and two-qubit gates, which is universal for trivial reasons and used when exact rather than approximate universality is wanted).

Step 2 — Build the circuit as a uniform family. For each input length $n$, a classical, polynomial-time algorithm outputs a description of the circuit $C_n$ (its gate list, wiring, and measurement locations). This uniformity condition is exactly the one used for classical Uniform Circuit Families: it rules out circuit families that "cheat" by hard-coding answers into an astronomically complex, non-constructible circuit for each $n$.

Step 3 — Apply gates, then measure. The circuit evolves the initial state $|x\rangle|0\cdots0\rangle$ through the unitary

and then measures a designated output qubit in the computational basis. The measurement outcome is a random bit whose distribution depends on $x$; the circuit accepts if this bit is $1$.

Step 4 — Approximate any needed unitary using universality. If an algorithm designer wants to apply some unitary $V$ not directly in $\mathcal{G}$ (e.g., a controlled rotation by an irrational angle appearing in Shor's algorithm), universality guarantees a circuit of gates from $\mathcal{G}$ approximating $V$ to error $\varepsilon$ using

gates (Solovay–Kitaev), for a small constant $c$ (known bounds give $c \approx 3.97$, improved variants push it lower). This lets algorithm designers reason at the level of "apply unitary $V$" and only pay a polylogarithmic overhead when compiling down to the fixed native gate set.

Step 5 — Amplify bounded error. If a single run of $C_n$ gives the correct answer with probability $\ge 2/3$, run $C_n$ independently $k$ times and take the majority vote. By a Chernoff bound the error probability drops to $2^{-\Omega(k)}$, so $k = O(\log(1/\delta))$ repetitions suffice for any target failure probability $\delta$, at only a polynomial blow-up in total circuit size. ``` // Pseudocode: constructing and running a quantum circuit // for a decision problem, with universality-based compilation // and error amplification. function BUILD_CIRCUIT(n): // classical poly-time "compiler": outputs a gate list register R = n input qubits + poly(n) ancilla qubits, all |0> gate_list = [] for each abstract step V_i in the algorithm's high-level description: if V_i in native_gate_set G: gate_list.append(V_i) else: // Solovay-Kitaev style compilation approx_circuit = APPROXIMATE(V_i, epsilon, G) gate_list.append(approx_circuit) // O(log^c(1/eps)) gates designate output_qubit return (register, gate_list, output_qubit) function RUN_ONCE(x, register, gate_list, output_qubit): state = encode(x) tensor |0...0>_ancilla for G in gate_list: state = apply(G, state) // unitary evolution bit = measure(output_qubit, state) // probabilistic return bit function DECIDE(x, k): // amplification: k independent repetitions, majority vote votes = [] for i in 1..k: (register, gate_list, output_qubit) = BUILD_CIRCUIT(len(x)) votes.append(RUN_ONCE(x, register, gate_list, output_qubit)) return MAJORITY(votes) // error <= 2^{-Omega(k)} ``` The single :::svg figure below lays out the whole pipeline: classical description of $x$, register initialization, layered gate application (showing depth vs. size), a Solovay–Kitaev compilation zoom-in, and final measurement feeding a majority-vote amplifier.

Size and depth as complexity measures. For an algorithm on inputs of length $n$, we track two functions: $\text{size}(n)$, the total gate count of $C_n$, and $\text{depth}(n)$, the number of layers when gates on disjoint qubits run in parallel. A problem is solved efficiently in the circuit model if there is a uniform family $\{C_n\}$ with $\text{size}(n) = \text{poly}(n)$ — this is the direct quantum analogue of polynomial-time classical computation, and it is exactly the resource bound used to define BQP. Depth matters separately for questions about parallel quantum speedups but does not, by itself, define the basic efficient class.

Why universality doesn't blow up complexity: Solovay–Kitaev. The correctness of "any universal gate set gives the same complexity class up to polynomial factors" rests on the Solovay–Kitaev theorem: given a universal, closed-under-inverse gate set $\mathcal{G}$, any single-qubit unitary $U$ can be approximated to accuracy $\varepsilon$ by a word of length

gates from $\mathcal{G}$, for a constant $c$ (originally $c \approx 4$; refinements reduce this). The proof sketch proceeds by induction on a sequence of nets $\mathcal{G}_0 \subset \mathcal{G}_1 \subset \cdots$ that get $\varepsilon$-dense in $SU(2)$ exponentially fast: 1. Base case: net $\mathcal{G}_0$ approximates every unitary to some fixed constant accuracy $\varepsilon_0 < 1$ (this follows because $\mathcal G$ densely generates $SU(2)$ — a consequence of universality — and $SU(2)$ is compact). 2. Inductive step: given a net $\mathcal{G}_j$ accurate to $\varepsilon_j$, express the residual error $\Delta = U (\text{approx}_j)^{-1}$ as a group commutator $\Delta = V W V^{-1} W^{-1}$ where $V, W$ are close to identity (this is always possible for $U(2)$/$SU(2)$ elements near identity, via the Balanced Commutator Lemma). Approximate $V$ and $W$ using the previous net $\mathcal{G}_j$; because the commutator map is a contraction near the identity, the resulting approximation to $\Delta$ — and hence to $U$ — has error

3. Iterating, error shrinks doubly exponentially in the recursion depth $j$, while circuit length grows only exponentially in $j$. Solving $\varepsilon_j \sim \varepsilon$ for the required $j$ and comparing to gate-count growth gives the polylogarithmic bound above. This theorem is the precise justification for "the choice of universal gate set doesn't matter (up to polylog overhead)" — it converts an existence statement (universal sets can approximate anything) into an efficiency statement (they can do so cheaply), which is exactly what a complexity theorist needs before declaring the circuit model well-defined independent of hardware.

Why bounded-error amplification is correct. Suppose a single circuit run outputs the correct bit with probability $p \ge 2/3$ on every fixed input $x$ (this asymmetry, "correct with probability $\ge 2/3$" rather than "$= 1$", is unavoidable because measurement is genuinely stochastic). Run $k$ independent copies and output the majority bit. Let $X_i$ be the indicator that run $i$ is correct, so $X_i$ are i.i.d. Bernoulli($p$) with $p \geq 2/3$. The majority is wrong only if fewer than $k/2$ of the $X_i$ are $1$. By a Chernoff–Hoeffding bound,

So $k = O(\log(1/\delta))$ repetitions push the error below any target $\delta$, and the total circuit size only grows by the same $O(\log(1/\delta))$ multiplicative factor — a polynomial (indeed polylogarithmic) overhead, not an exponential one. This is precisely the argument that makes "bounded error with probability $\ge 2/3$" and "bounded error with probability $\ge 1 - 2^{-n}$" define the same complexity class: amplification is free up to polynomial factors, so the exact constant $2/3$ in the definition of bounded-error acceptance is a convention, not a real degree of freedom.

Honesty about the tradeoffs. The circuit model idealizes gates as exact unitaries and ignores decoherence, gate infidelity, and connectivity constraints of real hardware — all of which real quantum devices must fight using Quantum Error Correction. The Solovay–Kitaev overhead, while polylogarithmic, is not free in practice: compiling a single arbitrary rotation to $10^{-10}$ precision can cost dozens of native gates, which matters enormously when every gate carries a nonzero physical error rate. And circuit depth, not just size, often dominates real device feasibility (coherence time), a distinction the size-only definition of efficient quantum computation does not capture — it captures asymptotic classification, not near-term engineering cost.

Trace the compilation and amplification pipeline concretely for a toy problem: decide whether a hidden bit $s \in \{0,1\}$ satisfies $s = 1$, using a circuit that (by design) outputs the correct answer with probability exactly $p = 0.7$ per run — a stand-in for a real bounded-error quantum subroutine.

Part A — universality/compilation cost. Suppose the algorithm needs to apply a single-qubit rotation $R_\theta$ by an irrational angle $\theta$ (this arises, e.g., in phase-estimation subroutines) to accuracy $\varepsilon = 10^{-3}$, using only $\{H, T\}$-type gates. Applying the Solovay–Kitaev bound with a typical constant $c \approx 4$:

(In practice, tuned SK implementations and modern number-theoretic compilers achieve far fewer gates than this loose asymptotic bound suggests — the exercise is to see the shape of the tradeoff, not to take the constant literally.)

Part B — error amplification. Now trace the majority-vote amplifier with $p = 0.7$, wanting final error $\delta = 0.01$.

Concretely with $k = 41$: run the circuit 41 times, each independently correct with probability 0.7. The number of correct runs $X \sim \text{Binomial}(41, 0.7)$ has mean $28.7$; the majority threshold is $21$. Computing the exact binomial tail $\Pr[X < 21]$ gives a value comfortably under $1\%$, confirming (and beating) the Chernoff estimate — repetitions bought certainty at only a $41\times$ multiplicative blow-up in circuit count, i.e. still polynomial in $\log(1/\delta)$, exactly as the amplification argument predicts.

Putting both parts together: the total circuit used to decide $s=1$ with $99\%$ confidence, using an internal rotation gate compiled to $10^{-3}$ precision, has size roughly

still a polynomial function of the problem parameters — illustrating exactly why both universality overhead and error-amplification overhead are absorbed into the "polynomial" in the definition of efficient bounded-error quantum computation, without changing which problems are solvable efficiently.

The circuit model and gate universality did not appear fully formed; they crystallized from independent lines of work in quantum information and theoretical computer science through the 1980s and 1990s.

The circuit model with a fixed universal gate set is exactly the abstraction quantum hardware compilers target: IBM's Qiskit, Google's Cirq, and other toolchains all compile high-level algorithm descriptions down to a small native gate set (typically single-qubit rotations plus a two-qubit entangling gate), invoking Solovay–Kitaev-style or number-theoretically optimized compilation to hit target precision with minimal gate count. Bounded-error acceptance and amplification underlie every practical claim that a noisy intermediate-scale quantum (NISQ) device "solved" an instance, since no physical run of a quantum circuit is ever certain — every reported quantum algorithm result is implicitly a bounded-error claim, repeated and aggregated over many shots. The universality question also governs quantum error correction: fault-tolerant schemes must implement a universal and fault-tolerant gate set (e.g. Clifford+T with magic-state distillation), directly inheriting the size/precision tradeoffs analyzed via Solovay–Kitaev-type bounds. Finally, this entire circuit-and-error framework is the machine model referenced whenever a paper claims a quantum algorithm achieves a speedup over the best known classical algorithm — that claim is only meaningful once "efficient quantum computation" has been pinned down as precisely as "efficient classical computation" is pinned down by Uniform Circuit Families and classical Time Complexity classes like P.

Ask the tutor: How does BQP formally relate to classical complexity classes like P, BPP, and NP?