QUEST: systematically approximating Quantum circuits for higher output fidelity

On today's noisy quantum computers every two-qubit gate costs 1–3% error, so the exact circuit often gives worse answers than a deliberately approximate one — QUEST partitions circuits, synthesizes shorter stand-ins with provably bounded drift, and runs several deliberately dissimilar ones so their individual biases average away.

Why this problem is worth solving

The site’s quantum explainers so far cover compilation (Paulihedral) and error correction (LILLIPUT). QUEST lives in the era before error correction:

The arithmetic of despair is simple. A CNOT — the two-qubit gate that creates entanglement, and into which all quantum algorithms decompose (together with single-qubit rotations) — fails at 1–3% per application. A circuit with a hundred CNOTs is thus mostly noise. The paper opens with the demonstration: the TFIM and Heisenberg Hamiltonian-simulation algorithms — real materials science, computing magnetization over time for four-spin systems — run on IBM’s relatively good Manila device with all Qiskit optimizations enabled, and produce outputs that track neither the amplitude nor even the shape of the ground truth.

The overlooked lever is exactness itself. Conventional compilers must emit a circuit computing precisely the same

What people did before, and where it broke

Exact optimization. Gate collapsing, commutativity-based cancellation, layout- and noise-aware mapping (Qiskit’s optimization passes bundle the state of the art). Measured here: negligible CNOT reductions for most benchmarks, over 30% for Heisenberg’s favorable structure, and small increases for HLF and Multiply. Exact rewriting can only harvest redundancy the circuit happens to contain.

Exact synthesis. Numerical synthesis tools (QSearch, LEAP — from the same Berkeley Lab group’s BQSKit ecosystem) rebuild a circuit from its unitary, layer by layer: place a CNOT plus rotations, optimize the angles to minimize

The two open problems. Loosening ε yields short circuits — but (1) for a large circuit, you cannot even compute the process distance to verify quality, and (2) process distance does not map monotonically onto output distance: of two approximations at equal ε, one may produce nearly correct measurement statistics and the other badly skewed ones, and telling them apart analytically would require knowing the answer you’re computing. Prior approximation ideas stalled on exactly these rocks.

The idea

Fewer gates beats exact gates — if drift is controlled. The design’s first principle is an error budget with two currencies: approximation error (chosen, bounded, known) versus noise error (imposed, compounding, roughly proportional to CNOT count). QUEST spends a little of the first to save a lot of the second.

Partition, then prove the pieces compose. Synthesis scales exponentially, so QUEST synthesizes blocks. The dangerous unknown is composition: block errors might compound badly, forcing paranoidly tight per-block thresholds — and tight thresholds mean more layers, more CNOTs, defeating the purpose. The paper’s theorem dissolves the fear: extending a block unitary to the full register (Kronecker product with identity) preserves its process-distance bound, and composing blocks accumulates bounds predictably. Block budgets therefore imply a full-circuit guarantee that is never directly computed — the result that makes partitioned approximation sound rather than hopeful.

Don’t pick the best approximation — pick a committee that disagrees. Here is the paper’s most distinctive move. The fewest-CNOT approximation may happen to have low output error or high — unknowable without ground truth. But many approximations scattered around the original in Hilbert space have biases in different directions, and their average converges toward the true output. The selection criterion makes “different directions” precise: two approximations are similar if their mutual process distance is at most the larger of their distances to the original (same region of the ε-ball), dissimilar if their mutual distance exceeds it (opposite sides — biases that cancel). A dual-annealing search over block-instance combinations minimizes an objective weighing the fraction of similar pairs and normalized CNOT count equally: a committee of cheap, mutually contradicting circuits.

The cost model is honest. Running M circuits costs M× the shots — but each circuit is dramatically shorter, and on NISQ hardware shots are cheap while gates are ruinous. The trade is explicit and tunable.

CNOT error: 1–3% per gate, compounding
Qiskit reduction on most benchmarks: negligible

Why it works

• Noise error scales with gate count while approximation error is a chosen budget → below the crossover, approximating is strictly better than exactness → the exact circuit is not the most faithful circuit on noisy hardware.
• Blocks are synthesizable and the composition bound is proven → full-circuit quality is guaranteed from block budgets without computing the intractable full unitary → partitioned approximation becomes sound and scalable (to 32 qubits here).
• Output bias of any single approximation is unknowable without ground truth → but geometry is knowable: mutual process distances identify approximations on opposite sides of the ε-ball → an ensemble chosen for disagreement self-cancels its biases in the average.
• Synthesis trees naturally emit candidates at every depth → harvesting the whole menu (rather than one winner) supplies the diversity the committee needs at no extra search cost.
• Shots are cheap, gates are expensive on NISQ devices → running M short circuits beats running one long one → the ensemble’s cost lands on the abundant resource.

What it costs

• M× the executions. The committee multiplies shot counts; acceptable when shots are cheap, relevant for cloud-metered access.
• Offline synthesis time. Per-block tree search with numerical optimization at every layer; partitioning keeps it tractable but it is hours, not seconds, for larger circuits.
• An approximation, still. Applications needing exact amplitudes (not sampled output statistics) fall outside the trade; the bound controls process distance, and the ensemble argument is geometric and empirical, not a worst-case output guarantee.
• Small real-device validation. Hardware runs reach 5 qubits (Manila) and noisy simulation 16 qubits; the 32-qubit results are ideal-simulator only.
• Block structure sensitivity. Partitioning choices shape the reachable approximation space; the paper uses established partitioners but the interaction is not exhaustively explored.

The evaluation

Fifteen benchmark instances across eight algorithm families — arithmetic (Adder, Multiply), variational (QAOA, VQE), transforms (QFT, HLF), and Hamiltonian simulation (TFIM, Heisenberg, XY) — from 4 to 32 qubits. Comparisons: the original circuit, Qiskit’s full optimization stack, QUEST alone, and QUEST + Qiskit. Fidelity is measured by total variation distance and Jensen-Shannon divergence of output distributions, plus algorithm-specific quantities (magnetization curves).