Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6: one-call controlled U when U fixes zero

Open
QAlgorithms.Papers.Independent.Intakethird100.P03.controlled_partial_unitary

by Gohan · Nov 1, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

For every nnn, a fixed sequence over QQQ and one plain partial-unitary oracle call implements controlled UUU whenever U:N→MU:N\to MU:N→M contains and fixes the computational zero state. It uses clean work and satisfies

length⁡=4n+1,#U=1.\operatorname{length}=4n+1,\qquad\#U=1.length=4n+1,#U=1.

On the valid controlled domain ∣0⟩N⊕∣1⟩N|0\rangle N\oplus|1\rangle N∣0⟩N⊕∣1⟩N, it maps ∣0⟩ξ|0\rangle\xi∣0⟩ξ to itself and ∣1⟩ξ|1\rangle\xi∣1⟩ξ to ∣1⟩Uξ|1\rangle U\xi∣1⟩Uξ, returning work exactly to zero on every superposition. Its range is ∣0⟩N⊕∣1⟩M|0\rangle N\oplus|1\rangle M∣0⟩N⊕∣1⟩M. Every partial oracle call is defined on its incoming vector.

The sequence is chosen before the oracle, with no free controlled or inverse call.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Intakethird100_P03
Formal statement
noncomputable section

open scoped Matrix ComplexConjugate Kronecker

namespace QAlgorithms.Papers.Independent.Intakethird100.P03

open QAlgorithms.Papers.Independent.Renew46.P01 (cleanVector)

attribute [local instance] Classical.propDecidable

/-- PDF p.13, Lemma 6: one plain U call and four controlled-XOR sweeps (4n Toffolis).
U fixes zero exactly; all work is clean on the whole valid controlled subspace. The gate
list is chosen before the oracle, and every partial call is checked on its actual input. -/
theorem controlled_partial_unitary (n : ℕ) :
    ∃ (w : ℕ) (c : List (PartialOracleStep n ((n + 1) + w))),
      c.length = 4 * n + 1 ∧ partialOracleCount c = 1 ∧
      ∀ (U : PartialUnitary (Qubits n)) (hzero : zeroKet n ∈ U.domain),
        (U.iso ⟨zeroKet n, hzero⟩ : EuclideanSpace ℂ (Qubits n)) = zeroKet n →
        ∀ v : EuclideanSpace ℂ (Qubits (n + 1)), ControlledDomain U v →
          ValidPartialExecution c U (cleanVector w v) ∧
          act (partialOracleMatrix c U) (cleanVector w v) =
            cleanVector w (act (controlledQubits U.matrix) v) := by sorry

end QAlgorithms.Papers.Independent.Intakethird100.P03

end
Source
Quantum measurements and the Abelian Stabilizer Problem, arXiv:quant-ph/9511026v1, PDF p. 13, Lemma 6: one-call controlled U when U fixes zero
Read-back

What the Lean code literally says, in plain math · gpt-6.1-sol

For every natural number nnn, there exist a natural number www and a list ccc of steps on n+1+wn+1+wn+1+w wires, chosen independently of the partial unitary and input vector, such that ccc has exactly 4n+14n+14n+1 entries and exactly one oracle-call entry. Known entries are injectively placed arbitrary one-wire unitaries, controlled NOT gates, or three-wire gates (a,b,d)↦(a,b,dxor(a∧b))(a,b,d)\mapsto(a,b,d\mathbin{\mathrm{xor}}(a\land b))(a,b,d)↦(a,b,dxor(a∧b)); a call entry injectively places the nnn oracle wires. For every partial unitary UUU, consisting of a complex linear isometry u:D→Ru:D\to Ru:D→R between subspaces of C{0,1}n\mathbb C^{\{0,1\}^n}C{0,1}n, every proof that the all-zero coordinate basis vector e0e_0e0​ belongs to DDD, and the hypothesis u(e0)=e0u(e_0)=e_0u(e0​)=e0​, the following holds for every vector v∈C{0,1}n+1v\in\mathbb C^{\{0,1\}^{n+1}}v∈C{0,1}n+1 whose two slices x↦v(b,x)x\mapsto v(b,x)x↦v(b,x), for both Boolean values bbb, belong to DDD. Let MMM be the matrix of uPDuP_DuPD​, where PDP_DPD​ is orthogonal projection onto DDD, and extend vvv by www zero ancillas to the vector v~(x,a)=v(x)\widetilde v(x,a)=v(x)v(x,a)=v(x) when every bit of aaa is false, and 000 otherwise. Executing ccc on v~\widetilde vv preserves the norm at every oracle call, and its final vector is

Bc(U)v~=CMv~,(CMv)(b,x)={v(false,x),b=false,∑yMx,yv(true,y),b=true.B_c(U)\widetilde v=\widetilde{C_Mv}, \qquad (C_Mv)(b,x)= \begin{cases} v(\mathrm{false},x),&b=\mathrm{false},\\ \displaystyle\sum_y M_{x,y}v(\mathrm{true},y),&b=\mathrm{true}. \end{cases}Bc​(U)v=CM​v​,(CM​v)(b,x)=⎩⎨⎧​v(false,x),y∑​Mx,y​v(true,y),​b=false,b=true.​

Here Bc(U)B_c(U)Bc​(U) is the reverse-ordered product of the step matrices, so the list acts in its written order; embedding a local matrix along a wire injection uses its entry on the selected bits when input and output agree on every unselected wire, and uses 000 otherwise. Norm preservation at a call means that its embedded matrix preserves the norm of the vector obtained from all preceding steps. No normalization of vvv is assumed. The claim includes n=0n=0n=0, when the list has length 111 and that sole entry is an oracle call; it also permits w=0w=0w=0.

Human review
  • Endorsed by Shuze Chen · Nov 1, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Gohan · Nov 1, 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