Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§2, Eq. (12): the state-injection gadget applies R(θ)R(\theta)R(θ), using R(2θ)R(2\theta)R(2θ) only on outcome 1

Proved
ConstOverheadCompile.Main.state_injection

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

magic-statesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-computing

Let θ∈R\theta\in\mathbb Rθ∈R and let ψ∈C2\psi\in\mathbb C^2ψ∈C2. Run the state-injection gadget of Figure 1 (left) on ∣ψ⟩⊗R(θ)∣+⟩|\psi\rangle\otimes R(\theta)|+\rangle∣ψ⟩⊗R(θ)∣+⟩. The gadget has exactly two branches:

  1. on measurement outcome 000 it applies only the CNOT, and the post-measurement vector is
12 R(θ)∣ψ⟩⊗∣0⟩;\tfrac{1}{\sqrt2}\,R(\theta)|\psi\rangle\otimes|0\rangle ;2​1​R(θ)∣ψ⟩⊗∣0⟩;
  1. on measurement outcome 111 it applies the CNOT and the correction R(2θ)R(2\theta)R(2θ), and the post-measurement vector is
eiθ2 R(θ)∣ψ⟩⊗∣1⟩.\tfrac{e^{i\theta}}{\sqrt2}\,R(\theta)|\psi\rangle\otimes|1\rangle .2​eiθ​R(θ)∣ψ⟩⊗∣1⟩.

For a state ∣ψ⟩|\psi\rangle∣ψ⟩ each outcome therefore occurs with probability 1/21/21/2, the data wire ends in R(θ)∣ψ⟩R(\theta)|\psi\rangleR(θ)∣ψ⟩ up to a global phase on both branches, and the gate R(2θ)R(2\theta)R(2θ) is used exactly on outcome 111. This is the resource conversion R(θ)∣+⟩+12R(2θ)⇒R(θ)R(\theta)|+\rangle+\tfrac12R(2\theta)\Rightarrow R(\theta)R(θ)∣+⟩+21​R(2θ)⇒R(θ) of Eq. (12), which drives the recursion of Algorithm 1.

Differences from the source:

  • generalization: a single-qubit state ∣ψ⟩|\psi\rangle∣ψ⟩ → any vector ψ∈C2\psi\in\mathbb C^2ψ∈C2; reason: the gadget is linear, and unit vectors are a special case.
  • encoding: "adaptively implements R(θ)R(\theta)R(θ) … with probability 1/2 … uses R(2θ)R(2\theta)R(2θ)" → the two branch operators applied to ∣ψ⟩⊗R(θ)∣+⟩|\psi\rangle\otimes R(\theta)|+\rangle∣ψ⟩⊗R(θ)∣+⟩, outcome 0 listed first, with coefficients 1/21/\sqrt21/2​ and eiθ/2e^{i\theta}/\sqrt2eiθ/2​; 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
  • 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