Theorem 1: a circuit of one- and two-qubit gates has an adaptive implementation with gates to any diamond-distance error
ProvedConstOverheadCompile.Main.theorem_1gate-synthesisp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-compilationquantum-computing
For all real and there is a constant with the following property. Let and be integers, and let be an adaptive circuit on qubits whose gates are arbitrary one- and two-qubit unitaries, with computational-basis measurements and classical feed-forward, using at most gates on every execution branch. Then for some number of ancillas there is an adaptive circuit on qubits whose only gates are , and CNOT, such that
- every branch of uses at most gates, and
- the data channel of (ancillas initialized to , traced out at the end) is within diamond distance
of the channel of .
The constant depends only on and , not on , or . The standard gate-by-gate compilation costs gates; the theorem removes the logarithmic overhead for every inverse-polynomial target error.
Differences from the source:
- generalization: a circuit of one- and two-qubit gates → an adaptive circuit with at most one- and two-qubit unitary gates on every branch; reason: the paragraph after Theorem 1 on p.2 and Remark 5; a measurement-free circuit is the special case, whose channel is .
- encoding: "any given error" and "" → for all there is , quantified before , , , with error and gate bound ; reason: every polynomial satisfies for , so the family contains every inverse-polynomial error, and the constant may depend only on the polynomial.
- encoding: arbitrary → ; reason: the chosen error expression has a zero denominator at ; circuits with no unitary gates, possibly containing measurements and feed-forward, compile exactly by retaining their measurement tree, so the omitted case needs no approximation.
- encoding: "diamond distance" → the full-trace-norm diamond distance in universal form over all reference dimensions, on the data register with ancillas traced out; reason: it dominates the half-normalized one, so the bound implies the source's under either convention.
- encoding: "uses gates in the worst case" → the maximum over branches of the number of gates; measurements are not counted; reason: the source counts gates.
Preamble
import Mathlib import Definitions.Def_ConstOverheadCompile_Main_GateSets import Definitions.Def_ConstOverheadCompile_Main_AdaptiveCircuit
Formal statement
namespace ConstOverheadCompile.Main
open QAlgorithms
/-- Theorem 1, p.2 (with the adaptive input of p.2 and Remark 5): for every polynomial error
bound `1/(K G^c)` there is a constant `C` such that every adaptive circuit on `n` wires over
arbitrary one- and two-qubit unitary gates, with at most `G ≥ 1` gates on every branch, is
implemented within diamond distance `1/(K G^c)` by an adaptive circuit over `{H, T, CNOT}` on
`n + a` wires (ancillas in `|0⟩`, traced out) with at most `C G` gates on every branch. -/
theorem theorem_1 :
∀ K c : ℝ, 0 < K → 0 < c → ∃ C : ℝ, ∀ (n G : ℕ), 1 ≤ G →
∀ A : AdaptiveCircuit ArbGates n, A.maxGates ≤ G →
∃ (a : ℕ) (A' : AdaptiveCircuit CliffordT (n + a)),
(A'.maxGates : ℝ) ≤ C * G ∧
DiamondClose A'.dataChannelRef A.channelRef (1 / (K * (G : ℝ) ^ c)) := by sorry
end ConstOverheadCompile.Main
Source
Chenyi Zhang, Xinyu Tan, Robin Kothari, David Gosset, Craig Gidney, Quantum circuit compilation with constant overhead, STOC 2027 submission #397 (October 2026), source.pdf SHA-256 b848604016de1821f5f693c59f328e0b2a9e535bca0b37bb664e6f40dbe3681f, p.2, §1, Theorem 1, Eq. (3), and the following paragraph; p.8 Remark 5; proof: §4, pp.10–11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.