Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1: deterministic exact four-call inversion

Proved
QAlgorithms.Papers.Independent.Support50.P24.deterministicExactFourCalls

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

prove2quantum

There is a fixed seven-qubit quantum circuit with exactly four forward calls to an unknown U∈SU(2)U\in\mathrm{SU}(2)U∈SU(2), using the same UUU at every call. Its inserted gates, singlet on input wires 2 and 3, and four zero ancillas are independent of UUU and the input. After discarding every output wire except wire 3, its channel is

ρ⟼U†ρU.\rho\longmapsto U^\dagger\rho U.ρ⟼U†ρU.

This equality holds on every input density matrix and after tensoring with the identity on any reference system. The auxiliary output may depend on UUU. The result establishes deterministic exact inversion without a supplied catalyst.

Formalization Note Equality is stated on all matrices; for these linear channels this is equivalent to channel equality on states, including entangled inputs.

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 pp.1-2, Theorem 1: a fixed circuit uses exactly four forward calls and
implements the inverse channel on all inputs, including reference-entangled inputs. -/
theorem deterministicExactFourCalls :
    ∃ gates : List CallGate, PhysicalCalls gates ∧ calls gates = 4 ∧ ExactInverter gates := by sorry

end QAlgorithms.Papers.Independent.Support50.P24

end
Source
Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly, arXiv:2209.02907v5, PDF p. 2, Theorem 1: deterministic exact four-call qubit-unitary inversion
Read-back

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

There exists a finite list of operations on seven Boolean-labelled qubits, each operation being either a specified complex 128×128128\times128128×128 matrix or a call labelled by one of the seven qubit positions, such that every specified matrix in the list is unitary and exactly four list entries are calls. For every determinant-one unitary matrix UUU indexed by {false,true}\{\mathrm{false},\mathrm{true}\}{false,true}, replace a call at position qqq by the matrix with entry Uxq,yqU_{x_q,y_q}Uxq​,yq​​ when xi=yix_i=y_ixi​=yi​ for all i≠qi\ne qi=q, and entry 000 otherwise; let GUG_UGU​ be the product of the resulting matrices in chronological order, with later operations multiplying on the left and the empty product equal to the identity. Define EEE, with rows indexed by seven-bit strings xxx and columns by Booleans bbb, by

Ex,b={s(x1,x2),x0=b and x3=x4=x5=x6=false,0,otherwise,s(a,b)={1/2,(a,b)=(false,true),−1/2,(a,b)=(true,false),0,otherwise.E_{x,b}= \begin{cases} s(x_1,x_2),&x_0=b\ \text{and }x_3=x_4=x_5=x_6=\mathrm{false},\\ 0,&\text{otherwise}, \end{cases} \qquad s(a,b)= \begin{cases} 1/\sqrt2,&(a,b)=(\mathrm{false},\mathrm{true}),\\ -1/\sqrt2,&(a,b)=(\mathrm{true},\mathrm{false}),\\ 0,&\text{otherwise}. \end{cases}Ex,b​={s(x1​,x2​),0,​x0​=b and x3​=x4​=x5​=x6​=false,otherwise,​s(a,b)=⎩⎨⎧​1/2​,−1/2​,0,​(a,b)=(false,true),(a,b)=(true,false),otherwise.​

Then, for every complex Boolean-indexed 2×22\times22×2 matrix AAA, including matrices that are not density matrices, setting X=GUEAE†GU†X=G_U E A E^\dagger G_U^\daggerX=GU​EAE†GU†​ gives, for every pair of Booleans a,ba,ba,b,

∑e∈{false,true}7e2=falseX e[2←a], e[2←b]=(U†AU)a,b.\sum_{\substack{e\in\{\mathrm{false},\mathrm{true}\}^{7}\\e_2=\mathrm{false}}} X_{\,e[2\leftarrow a],\,e[2\leftarrow b]} =(U^\dagger A U)_{a,b}.e∈{false,true}7e2​=false​∑​Xe[2←a],e[2←b]​=(U†AU)a,b​.

Here e[2←a]e[2\leftarrow a]e[2←a] means replacing coordinate 222 of eee by 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