Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Clean exact inversion with five forward calls

Proved
QAlgorithms.Papers.Independent.Support50.P24.cleanFiveCalls

by Goku · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

prove2quantum

Let U∈SU(2)U\in\mathrm{SU}(2)U∈SU(2) be unknown. Append one forward call to printed wire 2 of the four-call circuit of Fig. 1. This fixed circuit uses exactly five forward calls. For every input density matrix ρ\rhoρ it produces

∣ψ−⟩⟨ψ−∣12⊗(U†ρU)3⊗∣04⟩⟨04∣4⋯7,|\psi^-\rangle\langle\psi^-|_{12}\otimes(U^\dagger\rho U)_3\otimes|0^4\rangle\langle0^4|_{4\cdots7},∣ψ−⟩⟨ψ−∣12​⊗(U†ρU)3​⊗∣04⟩⟨04∣4⋯7​,

from ρ1⊗∣ψ−⟩⟨ψ−∣23⊗∣04⟩⟨04∣4⋯7\rho_1\otimes|\psi^-\rangle\langle\psi^-|_{23}\otimes|0^4\rangle\langle0^4|_{4\cdots7}ρ1​⊗∣ψ−⟩⟨ψ−∣23​⊗∣04⟩⟨04∣4⋯7​. The equality remains valid with a reference system. All final auxiliary registers are independent of UUU, which is the source's meaning of clean. The auxiliary wire layout may differ from the initial layout. This gives clean deterministic exact inversion; no thermodynamic cost estimate is asserted.

Preamble
import Definitions.Def_QAlgorithms_Papers_Independent_Support50_P24
Formal statement
noncomputable section

open QAlgorithms MeasureTheory

open scoped BigOperators Matrix ComplexConjugate ComplexOrder Matrix.Norms.Elementwise

namespace QAlgorithms.Papers.Independent.Support50.P24

attribute [local instance] Classical.decEq Classical.propDecidable

attribute [local instance] QAlgorithms.Papers.Independent.Support50.P24.groupedContinuousENorm

/-- PDF p.4: five forward calls achieve inversion with a final auxiliary state
independent of U, here singlet on wires 1,2 and four zero qubits on wires 4,...,7. -/
theorem cleanFiveCalls :
    PhysicalCalls cleanCircuit ∧ calls cleanCircuit = 5 ∧
    ∀ (U : QubitSU) (A : Matrix Bool Bool ℂ),
      conjSuperop (evaluateCalls cleanCircuit U * inputEmbedding) A =
        conjSuperop (swappedEmbedding * U.valᴴ) A := by sorry

end QAlgorithms.Papers.Independent.Support50.P24

end
Source
Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly, arXiv:2209.02907v5, PDF p. 4, Unnumbered main result: clean exact inversion with five calls
Read-back

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

Number seven qubits 0,…,60,\ldots,60,…,6, put X=(0110)X=\begin{pmatrix}0&1\\1&0\end{pmatrix}X=(01​10​) and Yα=(cos⁡(α/2)−sin⁡(α/2)sin⁡(α/2)cos⁡(α/2))Y_\alpha=\begin{pmatrix}\cos(\alpha/2)&-\sin(\alpha/2)\\ \sin(\alpha/2)&\cos(\alpha/2)\end{pmatrix}Yα​=(cos(α/2)sin(α/2)​−sin(α/2)cos(α/2)​), and let G(L;t;M)G(L;t;M)G(L;t;M) act by MMM on target ttt when all wire–value conditions in LLL hold on the input, otherwise acting as the identity, while leaving other bits unchanged. Let S(L;a,b)S(L;a,b)S(L;a,b) swap a,ba,ba,b under those conditions and otherwise leave the input unchanged. Empty control lists always hold. Lists below are chronological: [M1,…,Mr][M_1,\ldots,M_r][M1​,…,Mr​] has matrix Mr⋯M1M_r\cdots M_1Mr​⋯M1​. With ϑ=2arccos⁡2/3\vartheta=2\arccos\sqrt{2/3}ϑ=2arccos2/3​, define

T2(a,b,c)=[G([(a,1),(b,1)];c;X),G([(b,1)];a;X),G([(c,0)];b;Yπ/2),G([(a,0),(c,0)];b;Yπ/2),G([(b,0)];a;X),S([];a,b),S([];b,c)],T3(a,b,c,e)=[G([(a,0)];c;X),G([(c,1),(e,1)];b;X),G([(e,1)];c;X),G([(b,1)];c;X),G([(b,0)];e;Yπ),G([(a,1),(b,0),(c,1)];e;Y−ϑ),G([(a,1),(b,1),(c,1)];e;Yϑ),G([(e,1)];a;X),G([];a;X),S([];b,c),G([];b;X),G([(a,1)];b;X),S([(a,1)];b,c),G([(a,1),(b,1)];c;X)],K1=[S([];2,5),T2(0,1,2),G([(0,1)];6;X),T3(3,4,5,6)†,S([];3,6),S([];1,3)],K2=[S([];1,3),T3(0,1,2,3),S([];4,6),G([(4,1)];3;X),S([];5,6),T2(4,5,6)†,S([];2,4),S([];1,5),S([];0,4)].\begin{aligned} T_2(a,b,c)={}&[ G([(a,1),(b,1)];c;X),G([(b,1)];a;X), G([(c,0)];b;Y_{\pi/2}),\\ & G([(a,0),(c,0)];b;Y_{\pi/2}), G([(b,0)];a;X),S([];a,b),S([];b,c)],\\ T_3(a,b,c,e)={}&[ G([(a,0)];c;X),G([(c,1),(e,1)];b;X), G([(e,1)];c;X),G([(b,1)];c;X),\\ & G([(b,0)];e;Y_\pi), G([(a,1),(b,0),(c,1)];e;Y_{-\vartheta}), G([(a,1),(b,1),(c,1)];e;Y_\vartheta),\\ & G([(e,1)];a;X),G([];a;X),S([];b,c),G([];b;X), G([(a,1)];b;X),S([(a,1)];b,c), G([(a,1),(b,1)];c;X)],\\ K_1={}&[S([];2,5),T_2(0,1,2),G([(0,1)];6;X), T_3(3,4,5,6)^\dagger,S([];3,6),S([];1,3)],\\ K_2={}&[S([];1,3),T_3(0,1,2,3),S([];4,6), G([(4,1)];3;X),S([];5,6),T_2(4,5,6)^\dagger, S([];2,4),S([];1,5),S([];0,4)]. \end{aligned}T2​(a,b,c)=T3​(a,b,c,e)=K1​=K2​=​[G([(a,1),(b,1)];c;X),G([(b,1)];a;X),G([(c,0)];b;Yπ/2​),G([(a,0),(c,0)];b;Yπ/2​),G([(b,0)];a;X),S([];a,b),S([];b,c)],[G([(a,0)];c;X),G([(c,1),(e,1)];b;X),G([(e,1)];c;X),G([(b,1)];c;X),G([(b,0)];e;Yπ​),G([(a,1),(b,0),(c,1)];e;Y−ϑ​),G([(a,1),(b,1),(c,1)];e;Yϑ​),G([(e,1)];a;X),G([];a;X),S([];b,c),G([];b;X),G([(a,1)];b;X),S([(a,1)];b,c),G([(a,1),(b,1)];c;X)],[S([];2,5),T2​(0,1,2),G([(0,1)];6;X),T3​(3,4,5,6)†,S([];3,6),S([];1,3)],[S([];1,3),T3​(0,1,2,3),S([];4,6),G([(4,1)];3;X),S([];5,6),T2​(4,5,6)†,S([];2,4),S([];1,5),S([];0,4)].​

A named list within a list denotes its matrix. For U∈SU(2)U\in\mathrm{SU}(2)U∈SU(2), indexed by the two Boolean values, let Qj(U)=G([];j;U)Q_j(U)=G([];j;U)Qj​(U)=G([];j;U) and let EUE_UEU​ be the matrix of

[Q1(U),K1,Q1(U),K2,Q1(U),K1,Q1(U),K2,Q1(U)].[Q_1(U),K_1,Q_1(U),K_2,Q_1(U),K_1,Q_1(U),K_2,Q_1(U)].[Q1​(U),K1​,Q1​(U),K2​,Q1​(U),K1​,Q1​(U),K2​,Q1​(U)].

The assertion is that its known matrices K1,K2K_1,K_2K1​,K2​ are unitary, it contains exactly five calls to UUU, and, writing ∣s⟩=(∣01⟩−∣10⟩)/2|s\rangle=(|01\rangle-|10\rangle)/\sqrt2∣s⟩=(∣01⟩−∣10⟩)/2​, for every such UUU and every complex 2×22\times22×2 matrix AAA,

EU(A⊗∣s⟩⟨s∣⊗∣0000⟩⟨0000∣)EU†=∣s⟩⟨s∣⊗(U†AU)⊗∣0000⟩⟨0000∣.E_U\bigl(A\otimes|s\rangle\langle s| \otimes|0000\rangle\langle0000|\bigr)E_U^\dagger = |s\rangle\langle s|\otimes(U^\dagger A U) \otimes|0000\rangle\langle0000|.EU​(A⊗∣s⟩⟨s∣⊗∣0000⟩⟨0000∣)EU†​=∣s⟩⟨s∣⊗(U†AU)⊗∣0000⟩⟨0000∣.

Tensor factors are ordered by wire number. No density-matrix assumption is imposed on AAA.

Human review
  • Endorsed by Shuze Chen · Oct 24, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 24, 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