Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / MagicSquareTheorems / Rigidity / TwoQubitSwap

Definition
QPBT_QPBT_Test_MagicSquareTheorems_Rigidity_TwoQubitSwap

by Dengnifer · Oct 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

qpbt

This bundle constructs the one- and two-qubit controlled-swap maps used in the Magic Square rigidity argument. It proves their coordinate formulas and norm preservation for binary observables, and packages the two-qubit map as a linear isometric embedding.

Principal definitions:

  • MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap: the linear controlled-swap map whose output is indexed by two binary control labels.
  • MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapIsometry: the corresponding norm-preserving linear isometric embedding.
  • MIPStarRE.QPBT.MagicSquareRigidity.sum_pi_fin_two: rewrites a sum over two-bit labels as an iterated sum over the two coordinates.
  • MIPStarRE.QPBT.MagicSquareRigidity.sum_norm_sq_binarySwapComponent: expresses the squared norm of a one-qubit controlled-swap image as the sum of its residual component norms.
  • MIPStarRE.QPBT.MagicSquareRigidity.sum_norm_sq_binarySwapComponent_eq: binary observables make those residual norms sum to the input squared norm.
  • MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap_apply: the coordinate formula for the two-qubit controlled-swap map.
  • MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap_norm: the two-qubit map preserves norms under the four binary-observable hypotheses.
  • MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapIsometry_apply: the coordinate formula for the packaged isometry.

Formalization Credit. This Lean declaration is part of the Quantum Pauli basis test formalization by Ruixuan Deng. The source code was generated by AI agents; Ruixuan Deng is the responsible maintainer.

Mathematical Source. The mathematical source is Ji, Natarajan, Vidick, Wright, and Yuen, MIP*=RE, arXiv:2001.04383v3.

Definition code
-- Generated from QPBT/Test/MagicSquareTheorems/Rigidity/TwoQubitSwap.lean by skeleton subtraction.
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_AxisParallelLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_DiagonalLine
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LinePolynomials
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_LowDegreePolynomial
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_OpFamily
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersBase
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_ParametersFiniteAnswers
import Definitions.Def_LIDT_MIPStarRE_LDT_Basic_QuantumState
import Definitions.Def_LIDT_MIPStarRE_LDT_CommutativityPoints_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_ExpansionHypercubeGraph_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_GlobalVariance_Defs_Core
import Definitions.Def_LIDT_MIPStarRE_LDT_MakingMeasurementsProjective_Defs
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Families
import Definitions.Def_LIDT_MIPStarRE_LDT_Pasting_Defs_Interpolation
import Definitions.Def_LIDT_MIPStarRE_LDT_Tactic_AvgCongr
import Definitions.Def_LIDT_MIPStarRE_LDT_Test_StrategyCore
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_Basic
import Definitions.Def_QPBT_QPBT_Combining_Linearity_Defs
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Games_DistanceTheorems_Support
import Definitions.Def_QPBT_QPBT_Test_MagicSquareTheorems_PerfectStrategy_Observables
import Definitions.Def_QPBT_QPBT_Test_MagicSquareTheorems_Rigidity_Swap

namespace LIDT.MIPStarRE.LDT
end LIDT.MIPStarRE.LDT
namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT.MagicSquareRigidity
end MIPStarRE.QPBT.MagicSquareRigidity

/-!
# The two-qubit controlled-swap isometry

The conclusion of `thm:ms-rigidity` places each player's extracted register on
two qubits, indexed by `Fin 2 → ZMod 2`: the first carries the logical pair at
the cells `0` and `4`, the second the logical pair at the cells `1` and `3`.
`Rigidity/Swap.lean` builds the controlled-swap embedding attached to a single
anticommuting pair.  This file composes two of them.

For two pairs of binary observables `(X₁, Z₁)` and `(X₂, Z₂)` on one local
space, the map defined here sends a vector `ψ` to the family

    (e, i) ↦ (X₂^{e(1)} P^{Z₂}_{e(1)} X₁^{e(0)} P^{Z₁}_{e(0)} ψ) (i),

where `P^{Z}_b` is the spectral effect `reflectionEffect Z b`.  It is the
composition of the controlled swap of the first pair with the controlled swap
of the second pair applied to the residual copy of the local space, so it is an
*exact* isometry with no commutation assumption on the two pairs; approximate
commutation of the two pairs enters only when the second pair's observables are
transported through the first swap, which is not part of this file.

The first pair is applied innermost and is indexed by the register coordinate
`0`, matching `idealMagicBitProj`, whose marginal is taken over the coordinate
`0` of the label.

## References

blueprint `thm:ms-rigidity`,
paper `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:612-652`;
the cited robust self-test is Coladangelo--Stark, arXiv:1709.09267v2,
Theorem 6.9, `references/cs-paper/self-testing.tex:660-730`.  The one-qubit
construction is `binarySwapIsometry` in `Rigidity/Swap.lean`.
-/

@[expose] public section

open scoped BigOperators Matrix MatrixOrder ComplexOrder

namespace MIPStarRE.QPBT.MagicSquareRigidity

open LIDT.MIPStarRE.LDT LIDT.MIPStarRE.Quantum

noncomputable section

/-! ## Sums over a two-qubit label -/

/-- Formalization-only: a sum over two-qubit labels is a double sum over the two
coordinates. -/
theorem sum_pi_fin_two {M : Type*} [AddCommMonoid M] (f : ZMod 2 → ZMod 2 → M) :
    (∑ e : Fin 2 → ZMod 2, f (e 0) (e 1)) = ∑ b : ZMod 2, ∑ c : ZMod 2, f b c :=
  calc (∑ e : Fin 2 → ZMod 2, f (e 0) (e 1))
      = ∑ p : ZMod 2 × ZMod 2, f p.1 p.2 :=
        Fintype.sum_equiv (piFinTwoEquiv fun _ => ZMod 2) _ _ fun _ => rfl
    _ = ∑ b : ZMod 2, ∑ c : ZMod 2, f b c := Fintype.sum_prod_type _

/-- Formalization-only: the squared norm of the one-qubit controlled-swap image
is the sum of the squared norms of its two residual components. -/
theorem sum_norm_sq_binarySwapComponent {ι : Type} [Fintype ι] [DecidableEq ι]
    (X Z : _root_.LIDT.MIPStarRE.Quantum.Op ι) (v : EuclideanSpace ℂ ι) :
    (∑ b : ZMod 2,
        ‖_root_.MIPStarRE.QPBT.applyOperatorToState (X ^ b.val * _root_.MIPStarRE.QPBT.reflectionEffect Z b) v‖ ^ 2) =
      ‖_root_.MIPStarRE.QPBT.MagicSquareRigidity.binarySwapMap X Z v‖ ^ 2 := by
  rw [EuclideanSpace.norm_sq_eq, Fintype.sum_prod_type]
  exact Finset.sum_congr rfl fun b _ => EuclideanSpace.norm_sq_eq _

/-- The two residual components of a controlled swap carry the whole squared
norm of the input.  This is `binarySwapMap_norm` in the form in which the
two-qubit construction iterates it. -/
theorem sum_norm_sq_binarySwapComponent_eq {ι : Type} [Fintype ι] [DecidableEq ι]
    (X Z : _root_.LIDT.MIPStarRE.Quantum.Op ι) (hX : _root_.MIPStarRE.QPBT.IsBinaryObservable X) (hZ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z)
    (v : EuclideanSpace ℂ ι) :
    (∑ b : ZMod 2,
        ‖_root_.MIPStarRE.QPBT.applyOperatorToState (X ^ b.val * _root_.MIPStarRE.QPBT.reflectionEffect Z b) v‖ ^ 2) = ‖v‖ ^ 2 := by
  rw [_root_.MIPStarRE.QPBT.MagicSquareRigidity.sum_norm_sq_binarySwapComponent, _root_.MIPStarRE.QPBT.MagicSquareRigidity.binarySwapMap_norm X Z hX hZ]

/-! ## The two-qubit controlled-swap map -/

/-- Formalization-only linear controlled-swap map on a two-qubit register
supporting `thm:ms-rigidity`.  The component at the label `e` is obtained by
applying the residual component of the first pair at `e 0` and then that of the
second pair at `e 1`. -/
def twoBinarySwapMap {ι : Type} [Fintype ι] [DecidableEq ι]
    (X₁ Z₁ X₂ Z₂ : _root_.LIDT.MIPStarRE.Quantum.Op ι) :
    EuclideanSpace ℂ ι →ₗ[ℂ] EuclideanSpace ℂ ((Fin 2 → ZMod 2) × ι) where
  toFun ψ := (EuclideanSpace.equiv ((Fin 2 → ZMod 2) × ι) ℂ).symm
    (fun p => _root_.MIPStarRE.QPBT.applyOperatorToState
      (X₂ ^ (p.1 1).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ (p.1 1) *
        (X₁ ^ (p.1 0).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ (p.1 0))) ψ p.2)
  map_add' ψ ξ := by
    apply (EuclideanSpace.equiv ((Fin 2 → ZMod 2) × ι) ℂ).injective
    funext p
    simp only [ContinuousLinearEquiv.apply_symm_apply]
    unfold _root_.MIPStarRE.QPBT.applyOperatorToState
    rw [map_add]
    rfl
  map_smul' c ψ := by
    apply (EuclideanSpace.equiv ((Fin 2 → ZMod 2) × ι) ℂ).injective
    funext p
    simp only [ContinuousLinearEquiv.apply_symm_apply, RingHom.id_apply]
    unfold _root_.MIPStarRE.QPBT.applyOperatorToState
    rw [map_smul]
    rfl

/-- Formalization-only coordinate formula for the two-qubit controlled-swap
map. -/
@[simp]
theorem twoBinarySwapMap_apply {ι : Type} [Fintype ι] [DecidableEq ι]
    (X₁ Z₁ X₂ Z₂ : _root_.LIDT.MIPStarRE.Quantum.Op ι) (ψ : EuclideanSpace ℂ ι) (e : Fin 2 → ZMod 2) (i : ι) :
    _root_.MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap X₁ Z₁ X₂ Z₂ ψ (e, i) =
      _root_.MIPStarRE.QPBT.applyOperatorToState
        (X₂ ^ (e 1).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ (e 1) *
          (X₁ ^ (e 0).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ (e 0))) ψ i := rfl

/-- The two-qubit controlled-swap map preserves norms whenever the four
controlling operators are binary observables.  No commutation assumption between
the two pairs is needed: the map is the composition of the controlled swap of
the first pair with the controlled swap of the second pair applied to the
residual space. -/
theorem twoBinarySwapMap_norm {ι : Type} [Fintype ι] [DecidableEq ι]
    (X₁ Z₁ X₂ Z₂ : _root_.LIDT.MIPStarRE.Quantum.Op ι)
    (hX₁ : _root_.MIPStarRE.QPBT.IsBinaryObservable X₁) (hZ₁ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z₁)
    (hX₂ : _root_.MIPStarRE.QPBT.IsBinaryObservable X₂) (hZ₂ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z₂)
    (ψ : EuclideanSpace ℂ ι) :
    ‖_root_.MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap X₁ Z₁ X₂ Z₂ ψ‖ = ‖ψ‖ := by
  apply (sq_eq_sq₀ (norm_nonneg _) (norm_nonneg _)).mp
  rw [EuclideanSpace.norm_sq_eq, Fintype.sum_prod_type]
  have hcomp : ∀ (e : Fin 2 → ZMod 2),
      (∑ i : ι, ‖_root_.MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap X₁ Z₁ X₂ Z₂ ψ (e, i)‖ ^ 2) =
        ‖_root_.MIPStarRE.QPBT.applyOperatorToState (X₂ ^ (e 1).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ (e 1))
          (_root_.MIPStarRE.QPBT.applyOperatorToState
            (X₁ ^ (e 0).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ (e 0)) ψ)‖ ^ 2 := by
    intro e
    rw [← _root_.MIPStarRE.QPBT.DistanceCalculus.applyOperatorToState_mul]
    exact (EuclideanSpace.norm_sq_eq (_root_.MIPStarRE.QPBT.applyOperatorToState
      (X₂ ^ (e 1).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ (e 1) *
        (X₁ ^ (e 0).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ (e 0))) ψ)).symm
  rw [Finset.sum_congr rfl
    fun e (_ : e ∈ (Finset.univ : Finset (Fin 2 → ZMod 2))) => hcomp e]
  rw [_root_.MIPStarRE.QPBT.MagicSquareRigidity.sum_pi_fin_two (fun b c =>
    ‖_root_.MIPStarRE.QPBT.applyOperatorToState (X₂ ^ c.val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ c)
      (_root_.MIPStarRE.QPBT.applyOperatorToState (X₁ ^ b.val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ b) ψ)‖ ^ 2)]
  have hinner : ∀ b : ZMod 2,
      (∑ c : ZMod 2, ‖_root_.MIPStarRE.QPBT.applyOperatorToState (X₂ ^ c.val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ c)
          (_root_.MIPStarRE.QPBT.applyOperatorToState (X₁ ^ b.val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ b) ψ)‖ ^ 2) =
        ‖_root_.MIPStarRE.QPBT.applyOperatorToState (X₁ ^ b.val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ b) ψ‖ ^ 2 :=
    fun b => _root_.MIPStarRE.QPBT.MagicSquareRigidity.sum_norm_sq_binarySwapComponent_eq X₂ Z₂ hX₂ hZ₂ _
  rw [Finset.sum_congr rfl
    fun b (_ : b ∈ (Finset.univ : Finset (ZMod 2))) => hinner b]
  exact _root_.MIPStarRE.QPBT.MagicSquareRigidity.sum_norm_sq_binarySwapComponent_eq X₁ Z₁ hX₁ hZ₁ ψ

/-- Formalization-only local two-qubit controlled-swap embedding for
`thm:ms-rigidity`, bundled as a linear isometric embedding.  Its codomain is the
two-qubit register of the conclusion, `(Fin 2 → ZMod 2) × ι`. -/
noncomputable def twoBinarySwapIsometry {ι : Type} [Fintype ι] [DecidableEq ι]
    (X₁ Z₁ X₂ Z₂ : _root_.LIDT.MIPStarRE.Quantum.Op ι)
    (hX₁ : _root_.MIPStarRE.QPBT.IsBinaryObservable X₁) (hZ₁ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z₁)
    (hX₂ : _root_.MIPStarRE.QPBT.IsBinaryObservable X₂) (hZ₂ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z₂) :
    EuclideanSpace ℂ ι →ₗᵢ[ℂ] EuclideanSpace ℂ ((Fin 2 → ZMod 2) × ι) where
  toLinearMap := _root_.MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap X₁ Z₁ X₂ Z₂
  norm_map' := _root_.MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapMap_norm X₁ Z₁ X₂ Z₂ hX₁ hZ₁ hX₂ hZ₂

/-- Formalization-only coordinate formula for the two-qubit controlled-swap
isometry. -/
@[simp]
theorem twoBinarySwapIsometry_apply {ι : Type} [Fintype ι] [DecidableEq ι]
    (X₁ Z₁ X₂ Z₂ : _root_.LIDT.MIPStarRE.Quantum.Op ι)
    (hX₁ : _root_.MIPStarRE.QPBT.IsBinaryObservable X₁) (hZ₁ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z₁)
    (hX₂ : _root_.MIPStarRE.QPBT.IsBinaryObservable X₂) (hZ₂ : _root_.MIPStarRE.QPBT.IsBinaryObservable Z₂)
    (ψ : EuclideanSpace ℂ ι) (e : Fin 2 → ZMod 2) (i : ι) :
    _root_.MIPStarRE.QPBT.MagicSquareRigidity.twoBinarySwapIsometry X₁ Z₁ X₂ Z₂ hX₁ hZ₁ hX₂ hZ₂ ψ (e, i) =
      _root_.MIPStarRE.QPBT.applyOperatorToState
        (X₂ ^ (e 1).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₂ (e 1) *
          (X₁ ^ (e 0).val * _root_.MIPStarRE.QPBT.reflectionEffect Z₁ (e 0))) ψ i := rfl

/-! ## Magic Square specialization -/















end

end MIPStarRE.QPBT.MagicSquareRigidity
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/MagicSquareTheorems/Rigidity/TwoQubitSwap.lean#L51-L177

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