Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact three-call inversion with a returned catalyst

Proved
QAlgorithms.Papers.Independent.Support50.P24.catalyticThreeCalls

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 and let ∣ψ−⟩=(∣01⟩−∣10⟩)/2|\psi^-\rangle=(|01\rangle-|10\rangle)/\sqrt2∣ψ−⟩=(∣01⟩−∣10⟩)/2​. Supply the particular catalyst ∣ψU⟩=(U⊗I)∣ψ−⟩|\psi_U\rangle=(U\otimes I)|\psi^-\rangle∣ψU​⟩=(U⊗I)∣ψ−⟩ for this same UUU. The fixed circuit obtained from Fig. 1 by deleting its first oracle call uses three forward calls and satisfies

ρ1⊗∣ψU⟩⟨ψU∣23⊗∣04⟩⟨04∣4⋯7⟼∣ψU⟩⟨ψU∣12⊗(U†ρU)3⊗∣04⟩⟨04∣4⋯7.\rho_1\otimes|\psi_U\rangle\langle\psi_U|_{23}\otimes|0^4\rangle\langle0^4|_{4\cdots7} \longmapsto |\psi_U\rangle\langle\psi_U|_{12}\otimes(U^\dagger\rho U)_3\otimes|0^4\rangle\langle0^4|_{4\cdots7}.ρ1​⊗∣ψU​⟩⟨ψU​∣23​⊗∣04⟩⟨04∣4⋯7​⟼∣ψU​⟩⟨ψU​∣12​⊗(U†ρU)3​⊗∣04⟩⟨04∣4⋯7​.

The equality includes reference-entangled inputs. It returns the catalyst for reuse with the same unknown operation; it does not assert three-call inversion without advice. The density-matrix formula includes the physical wire relabelling and removes the circuit's global minus sign.

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.2, Eq.(1): three forward calls with the specified same-U catalyst return
that catalyst while inverting the input. Full output channel equality suppresses global phase. -/
theorem catalyticThreeCalls :
    PhysicalCalls catalyticCircuit ∧ calls catalyticCircuit = 3 ∧
    ∀ (U : QubitSU) (A : Matrix Bool Bool ℂ),
      conjSuperop (evaluateCalls catalyticCircuit U * catalyticInput U) A =
        conjSuperop (outputEmbedding U * 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. 2, Unnumbered main result, Eq.(1): exact catalytic inversion with three calls
Read-back

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

Let the seven qubits be numbered 0,…,60,\ldots,60,…,6, with computational basis indexed by Boolean strings of length seven. Write 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)​). Let G(L;t;M)G(L;t;M)G(L;t;M) apply the matrix MMM to target qubit ttt when the input bits satisfy every wire–value pair in the list LLL, and otherwise act as the identity; all other bits remain unchanged. Let S(L;a,b)S(L;a,b)S(L;a,b) swap bits a,ba,ba,b when those same input conditions hold, and otherwise leave the string unchanged. An empty control list imposes no conditions. In the following lists, operations act from left to right, so the matrix of a list [M1,…,Mr][M_1,\ldots,M_r][M1​,…,Mr​] is Mr⋯M1M_r\cdots M_1Mr​⋯M1​, and the empty list has matrix III. 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)],ϑ=2arccos⁡2/3.\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)], \qquad \vartheta=2\arccos\sqrt{2/3}. \end{aligned}T2​(a,b,c)=T3​(a,b,c,e)=​[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)],ϑ=2arccos2/3​.​

Here a named list inside another list denotes its matrix. Define the fixed matrices

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} 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}K1​=K2​=​[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)].​

For any 2×22\times22×2 special unitary matrix UUU, let Qj(U)=G([];j;U)Q_j(U)=G([];j;U)Qj​(U)=G([];j;U), let EUE_UEU​ be the matrix of the sequence

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

and put ∣s⟩=(∣01⟩−∣10⟩)/2|s\rangle=(|01\rangle-|10\rangle)/\sqrt2∣s⟩=(∣01⟩−∣10⟩)/2​ and ∣χU⟩=(U⊗I)∣s⟩|\chi_U\rangle=(U\otimes I)|s\rangle∣χU​⟩=(U⊗I)∣s⟩. The assertion is that the known matrices K1,K2K_1,K_2K1​,K2​ in this sequence are unitary, the sequence contains exactly three calls to UUU, and, for every such UUU and every complex 2×22\times22×2 matrix AAA,

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

The tensor factors are ordered by wire number; AAA is arbitrary and need not be a density matrix.

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