Theorem 9 (corrected: ε ≤ 1): circuits over , , compile with gates
ProvedConstOverheadCompile.Main.theorem_9gate-synthesisp2o-batch-stoc27ap2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-compilationquantum-computing
There is an absolute constant with the following property. Let and be integers, , , and . Let be an adaptive circuit on wires over (with and ) that uses at most gates on every branch. Then for some number of ancillas there is an adaptive circuit over on wires such that
- every branch of uses at most
gates, and 2. the data channel of (ancillas initialized to and traced out) is within diamond distance of the channel of .
This is the core compilation result: Theorem 1 follows by decomposing into CNOT, and rotations, rounding every angle to the grid with , and choosing and so that the bound is .
Differences from the source:
- correction: all → ; reason: the printed bound is false for large : with , , , the quantity in (30) is , so no circuit meets it for any positive big-O constant; for the bound is nonnegative, and the paper uses throughout.
- generalization: a circuit of gates from → an adaptive circuit (computational-basis measurements, classical feed-forward) with at most gates on every branch; reason: Remark 5 (p.8) and the paragraph after Theorem 1; a measurement-free circuit is the special case, whose channel is .
- reading: " powers of two" with (30) undefined at → for every ; at the second term is (Lean's ); reason: is a power of two and ; the case is not excluded by the source.
- encoding: → one real constant quantified before ; natural logarithms; reason: the meaning of the bound; the base of the logarithm only changes .
- encoding: "diamond distance" → the full-trace-norm diamond distance in universal form over all reference dimensions; reason: it is at least the half-normalized one, so the bound implies the source's under either convention.
Preamble
import Mathlib import Definitions.Def_ConstOverheadCompile_Main_GateSets import Definitions.Def_ConstOverheadCompile_Main_AdaptiveCircuit
Formal statement
namespace ConstOverheadCompile.Main
open QAlgorithms
/-- Theorem 9, p.10, with `ε ≤ 1` (the printed bound (30) is negative for large `ε`): there is
an absolute constant `C₀` such that for all `r ≥ 2`, `B = 2^b`, `D = B^r`, `ε ∈ (0, 1]` and every
adaptive circuit on `n` wires over `𝒢 ∪ 𝒮_D` with at most `G` gates on every branch, some
adaptive circuit over `𝒢` on `n + a` wires (ancillas in `|0⟩`, traced out) uses at most
`C₀ (rG + rB log B · log(ε⁻¹ B r log B))` gates on every branch and is within diamond distance
`ε` of it. -/
theorem theorem_9 :
∃ C₀ : ℝ, ∀ r b : ℕ, 2 ≤ r → ∀ ε : ℝ, 0 < ε → ε ≤ 1 →
∀ (n G : ℕ) (A : AdaptiveCircuit (CliffordT ∪ gridGates ((2 ^ b) ^ r)) n),
A.maxGates ≤ G →
∃ (a : ℕ) (A' : AdaptiveCircuit CliffordT (n + a)),
(A'.maxGates : ℝ) ≤ C₀ * ((r : ℝ) * G + (r : ℝ) * (2 : ℝ) ^ b * Real.log ((2 : ℝ) ^ b) *
Real.log (ε⁻¹ * (2 : ℝ) ^ b * (r : ℝ) * Real.log ((2 : ℝ) ^ b))) ∧
DiamondClose A'.dataChannelRef A.channelRef ε := 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.10, §4, Theorem 9, Eq. (30); 𝒮_D: p.8 Eq. (18); adaptive input: p.8 Remark 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.