§2, Eq. (12): the state-injection gadget applies , using only on outcome 1
ProvedConstOverheadCompile.Main.state_injectionmagic-statesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-computing
Let and let . Run the state-injection gadget of Figure 1 (left) on . The gadget has exactly two branches:
- on measurement outcome it applies only the CNOT, and the post-measurement vector is
- on measurement outcome it applies the CNOT and the correction , and the post-measurement vector is
For a state each outcome therefore occurs with probability , the data wire ends in up to a global phase on both branches, and the gate is used exactly on outcome . This is the resource conversion of Eq. (12), which drives the recursion of Algorithm 1.
Differences from the source:
- generalization: a single-qubit state → any vector ; reason: the gadget is linear, and unit vectors are a special case.
- encoding: "adaptively implements … with probability 1/2 … uses " → the two branch operators applied to , outcome 0 listed first, with coefficients and ; reason: the probabilities and the channel follow from these vectors.
Preamble
import Mathlib import Definitions.Def_ConstOverheadCompile_Main_Gadgets
Formal statement
namespace ConstOverheadCompile.Main
open QAlgorithms
/-- §2, p.6, Figure 1 (left) and Eq. (12): the state-injection gadget, run on `|ψ⟩ ⊗ R(θ)|+⟩`,
has exactly two branches. On outcome 0 (one gate, CNOT) the post-measurement vector is
`(1/√2) R(θ)|ψ⟩ ⊗ |0⟩`; on outcome 1 (CNOT and the correction `R(2θ)`) it is
`(e^{iθ}/√2) R(θ)|ψ⟩ ⊗ |1⟩`. Each branch vector has squared Euclidean norm
`(‖ψ false‖² + ‖ψ true‖²)/2`, hence probability `1/2` for a normalized input state. On both
branches the data wire carries `R(θ)|ψ⟩` up to a global phase. -/
theorem state_injection (θ : ℝ) (ψ : Bool → ℂ) :
(AdaptiveCircuit.krausList (injectionGadget θ)).map
(fun K => K.mulVec (vec2 ψ (resourceVec θ))) =
[((Real.sqrt 2 : ℝ) : ℂ)⁻¹ • vec2 ((rot θ).mulVec ψ) (basisVec false),
(Complex.exp ((θ : ℂ) * Complex.I) * ((Real.sqrt 2 : ℝ) : ℂ)⁻¹) •
vec2 ((rot θ).mulVec ψ) (basisVec true)] := 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.6, §2, Figure 1 (left) and Eq. (12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.