Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Objective-preserving Haar symmetry reduction

Open
QAlgorithms.Papers.Independent.Support50.P24.symmetryReduction

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

prove2quantum

Let d≥1d\ge1d≥1, n≥0n\ge0n≥0, and let CCC be the Choi matrix of a deterministic sequential nnn-slot comb, or of a parallel strategy for U⊗nU^{\otimes n}U⊗n. Choi matrices use the unnormalized, input-first convention. Group the wires as (I1,…,In,F)(I_1,\ldots,I_n,F)(I1​,…,In​,F) and (P,O1,…,On)(P,O_1,\ldots,O_n)(P,O1​,…,On​). Let Ω\OmegaΩ be the actual inversion performance operator in (S77), with normalized Haar measure and the factor 1/d21/d^21/d2. Define R(V,W)=V⊗(n+1)⊗W⊗(n+1)R(V,W)=V^{\otimes(n+1)}\otimes W^{\otimes(n+1)}R(V,W)=V⊗(n+1)⊗W⊗(n+1) and

C‾=∫R(V,W)CR(V,W)† dV dW.\overline C=\int R(V,W)C R(V,W)^\dagger\,dV\,dW.C=∫R(V,W)CR(V,W)†dVdW.

The defining matrix integrals and scalar objective integrand are integrable. The matrix C‾\overline CC satisfies the same class of comb constraints, both Ω\OmegaΩ and C‾\overline CC commute with every R(V,W)R(V,W)R(V,W), and

Tr⁡(C‾Ω)=Tr⁡(CΩ)∈R.\operatorname{Tr}(\overline C\Omega)=\operatorname{Tr}(C\Omega)\in\mathbb R.Tr(CΩ)=Tr(CΩ)∈R.

Thus imposing the symmetry preserves every attainable objective and every optimum.

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.3,21-22,24: the concrete Haar average is feasible, invariant and
objective preserving for either sequential or parallel combs. All integrability is concluded. -/
theorem symmetryReduction (d n : ℕ) (hd : 0 < d) (parallel : Bool)
    (C : GroupedComb d (n+1))
    (hC : if parallel then ParallelFeasible C else SequentialFeasible d (n+1) C) :
    Integrable (@performanceKernel d n) (QAlgorithms.Papers.Independent.Next46.P24.haar d) ∧
    Integrable (fun U => (C * performanceKernel U).trace.re)
      (QAlgorithms.Papers.Independent.Next46.P24.haar d) ∧
    Integrable (averagingKernel C)
      ((QAlgorithms.Papers.Independent.Next46.P24.haar d).prod
        (QAlgorithms.Papers.Independent.Next46.P24.haar d)) ∧
    (if parallel then ParallelFeasible (averageComb C)
      else SequentialFeasible d (n+1) (averageComb C)) ∧
    (∀ V W : Matrix.specialUnitaryGroup (Fin d) ℂ,
      performanceOperator d n * groupAction V W = groupAction V W * performanceOperator d n ∧
      averageComb C * groupAction V W = groupAction V W * averageComb C) ∧
    (C * performanceOperator d n).trace.im = 0 ∧
    inversionObjective (averageComb C) = inversionObjective C := by sorry

end QAlgorithms.Papers.Independent.Support50.P24

end
Source
Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly, arXiv:2209.02907v5, PDF p. 3, Unnumbered main result, Eqs.(10)–(11): SU(d)×SU(d) symmetry reduction
Read-back

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

For every natural number d>0d>0d>0, every natural number nnn, every Boolean choice ppp, and every complex matrix CCC indexed by pairs of length-(n+1)(n+1)(n+1) tuples in {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1}, assume the feasibility condition specified below, using parallel feasibility when ppp is true and sequential feasibility otherwise. To define these conditions, write Ek={0,…,d−1}kE_k=\{0,\ldots,d-1\}^kEk​={0,…,d−1}k, write xaxaxa for appending aaa to xxx, write pspsps for prepending ppp to sss, and, for a matrix DDD indexed by Ek+1×Ek+1E_{k+1}\times E_{k+1}Ek+1​×Ek+1​, define

R(D)(x,s),(y,t)=1d∑a,b=0d−1D(xa,sb),(ya,tb).\mathcal R(D)_{(x,s),(y,t)} =\frac1d\sum_{a,b=0}^{d-1}D_{(xa,sb),(ya,tb)}.R(D)(x,s),(y,t)​=d1​a,b=0∑d−1​D(xa,sb),(ya,tb)​.

Sequential feasibility at length zero means that the matrix is the identity on the singleton index set E0×E0E_0\times E_0E0​×E0​; at length k+1k+1k+1, it means that DDD is positive semidefinite, R(D)\mathcal R(D)R(D) is sequentially feasible at length kkk, and, for every x,y∈Ekx,y\in E_kx,y∈Ek​ and s,t∈Ek+1s,t\in E_{k+1}s,t∈Ek+1​,

∑a=0d−1D(xa,s),(ya,t)=R(D)(x,s−),(y,t−) 1sk=tk,\sum_{a=0}^{d-1}D_{(xa,s),(ya,t)} =\mathcal R(D)_{(x,s^-),(y,t^-)}\,\mathbf1_{s_k=t_k},a=0∑d−1​D(xa,s),(ya,t)​=R(D)(x,s−),(y,t−)​1sk​=tk​​,

where s−,t−s^-,t^-s−,t− are the first kkk coordinates. Parallel feasibility of CCC means that CCC is positive semidefinite and there exists a positive semidefinite matrix BBB, indexed by En×{0,…,d−1}E_n\times\{0,\ldots,d-1\}En​×{0,…,d−1}, satisfying, for every x,y,s,t∈Enx,y,s,t\in E_nx,y,s,t∈En​ and every a,b∈{0,…,d−1}a,b\in\{0,\ldots,d-1\}a,b∈{0,…,d−1},

∑r=0d−1C(xr,as),(yr,bt)=B(x,a),(y,b)1s=t,∑x∈EnB(x,a),(x,b)=1a=b.\sum_{r=0}^{d-1}C_{(xr,as),(yr,bt)} =B_{(x,a),(y,b)}\mathbf1_{s=t}, \qquad \sum_{x\in E_n}B_{(x,a),(x,b)}=\mathbf1_{a=b}.r=0∑d−1​C(xr,as),(yr,bt)​=B(x,a),(y,b)​1s=t​,x∈En​∑​B(x,a),(x,b)​=1a=b​.

Let μd\mu_dμd​ be normalized Haar measure on SU(d)\mathrm{SU}(d)SU(d). For U,V,W∈SU(d)U,V,W\in\mathrm{SU}(d)U,V,W∈SU(d), define

vU(x,s)=Us0,xn∏i=0n−1Usi+1,xi,KU(x,s;y,t)=vU(x,s)vU(y,t)‾d2,P=∫KU dμd(U),TV,W(x,s;y,t)=(∏i=0nVxi,yi)(∏i=0nWsi,ti),C‾=∬TV,WCTV,W† dμd(V) dμd(W).\begin{aligned} v_U(x,s)&=U_{s_0,x_n}\prod_{i=0}^{n-1}U_{s_{i+1},x_i},& K_U(x,s;y,t)&=\frac{v_U(x,s)\overline{v_U(y,t)}}{d^2},\\ P&=\int K_U\,d\mu_d(U),& T_{V,W}(x,s;y,t)&= \left(\prod_{i=0}^{n}V_{x_i,y_i}\right) \left(\prod_{i=0}^{n}W_{s_i,t_i}\right),\\ \overline C&=\iint T_{V,W}CT_{V,W}^\dagger\, d\mu_d(V)\,d\mu_d(W). \end{aligned}vU​(x,s)PC​=Us0​,xn​​i=0∏n−1​Usi+1​,xi​​,=∫KU​dμd​(U),=∬TV,W​CTV,W†​dμd​(V)dμd​(W).​KU​(x,s;y,t)TV,W​(x,s;y,t)​=d2vU​(x,s)vU​(y,t)​​,=(i=0∏n​Vxi​,yi​​)(i=0∏n​Wsi​,ti​​),​

Then U↦KUU\mapsto K_UU↦KU​ is integrable, U↦Re⁡Tr⁡(CKU)U\mapsto\operatorname{Re}\operatorname{Tr}(CK_U)U↦ReTr(CKU​) is integrable, and (V,W)↦TV,WCTV,W†(V,W)\mapsto T_{V,W}CT_{V,W}^\dagger(V,W)↦TV,W​CTV,W†​ is integrable, each with respect to the displayed Haar measure or product measure; C‾\overline CC satisfies the same selected feasibility condition as CCC; for every V,W∈SU(d)V,W\in\mathrm{SU}(d)V,W∈SU(d), both PPP and C‾\overline CC commute with TV,WT_{V,W}TV,W​; and

Im⁡Tr⁡(CP)=0,Re⁡Tr⁡(C‾P)=Re⁡Tr⁡(CP).\operatorname{Im}\operatorname{Tr}(CP)=0, \qquad \operatorname{Re}\operatorname{Tr}(\overline C P) =\operatorname{Re}\operatorname{Tr}(CP).ImTr(CP)=0,ReTr(CP)=ReTr(CP).

The quantification includes n=0n=0n=0, with empty tuples and empty products interpreted as the unique empty tuple and 111, respectively.

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