Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Test / Soundness / NaimarkReduction

Definition
QPBT_QPBT_Test_Soundness_NaimarkReduction

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

qpbt

This bundle defines the Naimark dilation and compression data used to reduce soundness to projective strategies. It embeds the original Alice and Bob spaces into ground slices, constructs the dilated strategy and setting, transports witnesses, proves projectivity, and preserves the game value exactly.

Principal definitions:

  • MIPStarRE.QPBT.pauliNaimarkEmbeddingA: the question-independent Alice ground-slice embedding.
  • MIPStarRE.QPBT.pauliNaimarkEmbeddingB: the corresponding Bob embedding.
  • MIPStarRE.QPBT.pauliNaimarkStrategy: the completed questionwise Naimark strategy.
  • MIPStarRE.QPBT.pauliNaimarkSetting: the projective setting supplied by a winning strategy.
  • MIPStarRE.QPBT.pauliNaimarkWitness: transports a witness through the ground embeddings.
  • MIPStarRE.QPBT.pauliNaimarkStrategy_isProjective: proves projectivity of both dilated local families.
  • MIPStarRE.QPBT.pauliNaimarkStrategy_value: proves exact preservation of the game value.

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/Soundness/NaimarkReduction.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_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_LowDegreeCode
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Games_StrategyClasses
import Definitions.Def_QPBT_QPBT_Observables_Defs
import Definitions.Def_QPBT_QPBT_Test_MagicSquareTheorems_Rigidity_Dilation
import Definitions.Def_QPBT_QPBT_Test_PauliBasisTest
import Definitions.Def_QPBT_QPBT_Test_SoundnessDefs
import Mathlib

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

/-!
# Naimark reduction for Pauli-test strategies

An arbitrary Pauli-test strategy is dilated questionwise to a projective
strategy on two separately enlarged local spaces. The ground-slice embeddings
are fixed across questions. Compression recovers both original POVM families,
including the complete Pauli-answer postprocessing. Composing any isometry
witness on the dilation with the embeddings returns its state comparison to
the original spaces. Operator-family distance transfer is not asserted here.

## References

Paper `references/qpbt-paper/08_classical_and_quantum_low_degree_tests.tex:1426-1447`
(`thm:pauli`) and
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:160-190,1862-1876`.
Blueprint `thm:pauli-naimark-reduction-support`.
-/

@[expose] public section

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.Quantum MagicSquareRigidity

noncomputable section

/-- The question-independent embedding of Alice's original space in the
ground slice of the completed Naimark dilation. -/
def pauliNaimarkEmbeddingA (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P)) :
    EuclideanSpace ℂ S.ιA →ₗᵢ[ℂ]
      EuclideanSpace ℂ (S.ιA × Option (_root_.MIPStarRE.QPBT.PauliAnswer P)) :=
  _root_.MIPStarRE.QPBT.MagicSquareRigidity.naimarkEmbedding S.ιA (_root_.MIPStarRE.QPBT.PauliAnswer P)

/-- The corresponding question-independent embedding of Bob's space. -/
def pauliNaimarkEmbeddingB (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P)) :
    EuclideanSpace ℂ S.ιB →ₗᵢ[ℂ]
      EuclideanSpace ℂ (S.ιB × Option (_root_.MIPStarRE.QPBT.PauliAnswer P)) :=
  _root_.MIPStarRE.QPBT.MagicSquareRigidity.naimarkEmbedding S.ιB (_root_.MIPStarRE.QPBT.PauliAnswer P)

/-- Complete the Naimark dilation separately for every question and both
players, padding the original bipartite state at the ground coordinates. -/
@[reducible] def pauliNaimarkStrategy (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P)) : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P) :=
  _root_.MIPStarRE.QPBT.paddedStrategy S (none : Option (_root_.MIPStarRE.QPBT.PauliAnswer P)) (none : Option (_root_.MIPStarRE.QPBT.PauliAnswer P))
    (fun question => _root_.MIPStarRE.QPBT.dilatedMeasurement (default : _root_.MIPStarRE.QPBT.PauliAnswer P) (S.A question))
    (fun question => _root_.MIPStarRE.QPBT.dilatedMeasurement (default : _root_.MIPStarRE.QPBT.PauliAnswer P) (S.B question))

/-- Both local families of the dilated strategy are projective measurements. -/
theorem pauliNaimarkStrategy_isProjective (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P)) : (_root_.MIPStarRE.QPBT.pauliNaimarkStrategy P S).IsProjective :=
  _root_.MIPStarRE.QPBT.paddedStrategy_isProjective S none none _ _
    (fun question => _root_.MIPStarRE.QPBT.dilatedMeasurement_isProjective
      (default : _root_.MIPStarRE.QPBT.PauliAnswer P) (S.A question))
    (fun question => _root_.MIPStarRE.QPBT.dilatedMeasurement_isProjective
      (default : _root_.MIPStarRE.QPBT.PauliAnswer P) (S.B question))

/-- The two ground-slice compressions preserve the value of the game exactly. -/
theorem pauliNaimarkStrategy_value (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P)) : (_root_.MIPStarRE.QPBT.pauliNaimarkStrategy P S).value = S.value :=
  _root_.MIPStarRE.QPBT.paddedStrategy_value S none none _ _
    (fun question answer => _root_.MIPStarRE.QPBT.dilatedMeasurement_compression
      (default : _root_.MIPStarRE.QPBT.PauliAnswer P) answer (S.A question))
    (fun question answer => _root_.MIPStarRE.QPBT.dilatedMeasurement_compression
      (default : _root_.MIPStarRE.QPBT.PauliAnswer P) answer (S.B question))



/-- A winning strategy supplies a projective setting after dilation, with no
extra premise beyond the original winning inequality. -/
def pauliNaimarkSetting (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (epsilon : ℝ)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P)) (hwin : 1 - epsilon ≤ S.value) :
    _root_.MIPStarRE.QPBT.ProjectiveSetting P epsilon where
  toStrategy := _root_.MIPStarRE.QPBT.pauliNaimarkStrategy P S
  isProjective := _root_.MIPStarRE.QPBT.pauliNaimarkStrategy_isProjective P S
  win := by rw [_root_.MIPStarRE.QPBT.pauliNaimarkStrategy_value]; exact hwin









/-- Compose a witness on the dilated strategy with the ground embeddings,
keeping both auxiliary carrier spaces and the same normalized auxiliary state. -/
@[reducible] def pauliNaimarkWitness (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (S : _root_.MIPStarRE.QPBT.Strategy (_root_.MIPStarRE.QPBT.pauliBasisTest P))
    (w : _root_.MIPStarRE.QPBT.PauliSoundnessWitness P (_root_.MIPStarRE.QPBT.pauliNaimarkStrategy P S)) :
    _root_.MIPStarRE.QPBT.PauliSoundnessWitness P S where
  ιA' := w.ιA'
  ιB' := w.ιB'
  ιAFintype := w.ιAFintype
  ιBFintype := w.ιBFintype
  ιADecidableEq := w.ιADecidableEq
  ιBDecidableEq := w.ιBDecidableEq
  φA := w.φA.comp (_root_.MIPStarRE.QPBT.pauliNaimarkEmbeddingA P S)
  φB := w.φB.comp (_root_.MIPStarRE.QPBT.pauliNaimarkEmbeddingB P S)
  aux := w.aux
  aux_norm := w.aux_norm





end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Test/Soundness/NaimarkReduction.lean#L34-L147

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