Theorem 10 — clean fixed-gate simulation of QAC circuits
OpenDepthOptQC.Synth.Supplement.theorem_10p2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-circuitsquantum-compilationquantum-information
There are uniform constants and such that every size-, depth- QAC circuit on qubits and every admit a circuit over , and generalized Toffoli gates, with fresh clean ancillas, for which one phase satisfies
for every -qubit vector . Moreover, its depth is at most , while its size and are at most .
This is a full-unitary clean compiler, stronger than merely preserving a decision probability.
Differences from the source:
- reading: and → uniform witnesses and chosen before the circuit and precision; reason: makes the printed asymptotics explicit without choosing a special exponent
- encoding: the paper writes → Lean stores the data wires before the appended zero ancillas; reason: a fixed wire relabelling changes neither depth, size nor Euclidean error
- encoding: the paper quantifies normalized inputs → Lean quantifies every vector with error ; reason: homogeneity of the two linear maps makes this exactly equivalent, including the zero vector
Preamble
import Definitions.Def_DepthOptQC_Synth_Supplement_CircuitModel set_option autoImplicit false
Formal statement
namespace DepthOptQC.Synth.Supplement
open QAlgorithms DepthOptQC.Synth
/-- **Theorem 10 (Fixed-Gate Simulation of QAC Circuits)** — Vasconcelos,
arXiv:2609.34659, p.43, Eq. (203). Every size-`s`, depth-`d` QAC circuit has a clean simulation
over `H`, `T` and generalized Toffoli gates, with constant-factor depth and polynomial gate and
clean-workspace costs.
**Formalization Note.** The witnesses `K,k` make both `O(d)` and `poly(s,1/ε)` uniform. The clean
error is on the complete output for every quantum input, with one phase selected before the input. -/
theorem theorem_10 :
∃ K : ℝ, 0 < K ∧ ∃ k : ℕ,
∀ (w s d : ℕ) (C : LayeredCircuit qacGateSet w),
1 ≤ s → C.size = s → C.depth = d →
∀ ε : ℝ, 0 < ε → ε < 1 →
∃ A : ℕ, ∃ Ctilde : LayeredCircuit quacGateSet (w + A),
CleanlyApproximatesCircuit Ctilde.unitary C.unitary ε ∧
(Ctilde.depth : ℝ) ≤ K * d ∧
(Ctilde.size : ℝ) ≤ K * ((s : ℝ) + 1 / ε) ^ k ∧
(A : ℝ) ≤ K * ((s : ℝ) + 1 / ε) ^ k := by sorry
end DepthOptQC.Synth.Supplement
Source
Vasconcelos, Depth-Optimal Quantum Compilation, arXiv:2609.34659, Theorem 10, p.43 (PDF p.45), Eq. (203)