Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1: a circuit of GGG one- and two-qubit gates has an adaptive {H,T,CNOT}\{H,T,\mathrm{CNOT}\}{H,T,CNOT} implementation with O(G)O(G)O(G) gates to any 1/poly(G)1/\mathrm{poly}(G)1/poly(G) diamond-distance error

Proved
ConstOverheadCompile.Main.theorem_1

by mikedeng1 · Nov 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

gate-synthesisp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-compilationquantum-computing

For all real K>0K>0K>0 and c>0c>0c>0 there is a constant CCC with the following property. Let n≥0n\ge0n≥0 and G≥1G\ge1G≥1 be integers, and let AAA be an adaptive circuit on nnn qubits whose gates are arbitrary one- and two-qubit unitaries, with computational-basis measurements and classical feed-forward, using at most GGG gates on every execution branch. Then for some number aaa of ancillas there is an adaptive circuit A′A'A′ on n+an+an+a qubits whose only gates are HHH, TTT and CNOT, such that

  1. every branch of A′A'A′ uses at most C GC\,GCG gates, and
  2. the data channel of A′A'A′ (ancillas initialized to ∣0⟩|0\rangle∣0⟩, traced out at the end) is within diamond distance
1K Gc\frac{1}{K\,G^{c}}KGc1​

of the channel of AAA.

The constant CCC depends only on KKK and ccc, not on nnn, GGG or AAA. The standard gate-by-gate compilation costs O(Glog⁡(G/ε))O(G\log(G/\varepsilon))O(Glog(G/ε)) gates; the theorem removes the logarithmic overhead for every inverse-polynomial target error.

Differences from the source:

  • generalization: a circuit of GGG one- and two-qubit gates → an adaptive circuit with at most GGG 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 ρ↦UρU†\rho\mapsto U\rho U^\daggerρ↦UρU†.
  • encoding: "any given 1/poly(G)1/\mathrm{poly}(G)1/poly(G) error" and "O(G)O(G)O(G)" → for all K,c>0K,c>0K,c>0 there is CCC, quantified before nnn, GGG, AAA, with error 1/(KGc)1/(KG^c)1/(KGc) and gate bound CGCGCG; reason: every polynomial ppp satisfies p(G)≤KGcp(G)\le KG^cp(G)≤KGc for G≥1G\ge1G≥1, so the family 1/(KGc)1/(KG^c)1/(KGc) contains every inverse-polynomial error, and the constant may depend only on the polynomial.
  • encoding: GGG arbitrary → G≥1G\ge1G≥1; reason: the chosen error expression 1/(KGc)1/(KG^c)1/(KGc) has a zero denominator at G=0G=0G=0; 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 ∣0⟩|0\rangle∣0⟩ ancillas traced out; reason: it dominates the half-normalized one, so the bound implies the source's under either convention.
  • encoding: "uses O(G)O(G)O(G) 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
  • Endorsed by Shuze Chen · Nov 11, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 11, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me