Proposition 16: the phase-halving circuit applies to both inputs and returns the catalyst
ProvedConstOverheadCompile.Main.proposition_16magic-statesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-computing
Let and let . The phase-halving circuit of Figure 1 (right) satisfies
as an exact equality of vectors, with no global phase.
The catalyst is returned unchanged, so one gate yields two applications of ; this is the conversion (13) used to replenish the bank in Algorithm 1.
Differences from the source:
- generalization: single-qubit states , → arbitrary vectors in ; reason: the circuit is linear, and states are a special case.
Preamble
import Mathlib import Definitions.Def_ConstOverheadCompile_Main_Gadgets
Formal statement
namespace ConstOverheadCompile.Main
open QAlgorithms
/-- Proposition 16, p.17 (Eq. (71)): the phase-halving circuit of Figure 1 (right) maps
`R(θ)|+⟩ ⊗ ψ ⊗ φ ⊗ |0⟩` to `R(θ)|+⟩ ⊗ R(θ)ψ ⊗ R(θ)φ ⊗ |0⟩`, exactly, for every real `θ` and
all single-qubit vectors `ψ, φ`. -/
theorem proposition_16 (θ : ℝ) (ψ φ : Bool → ℂ) :
(phaseHalving θ).unitary.mulVec (vec4 (resourceVec θ) ψ φ (basisVec false)) =
vec4 (resourceVec θ) ((rot θ).mulVec ψ) ((rot θ).mulVec φ) (basisVec false) := 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.17, Appendix B, Proposition 16, Eq. (71); circuit: p.6, Figure 1 (right)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.