Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Combining / PairCompletion

Definition
QPBT_QPBT_Combining_PairCompletion

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

qpbt

This bundle completes a polynomial-pair outcome space for the combined low-degree measurement. It embeds bounded polynomial pairs, restricts and relabels extended outcomes, and records that substitution recovers and preserves the pair labels.

Principal definitions:

  • MIPStarRE.QPBT.recoverCombinedPair: recovers the two polynomial components by setting the unused block to zero and selecting the two scalar coordinate basis values.
  • MIPStarRE.QPBT.combinedPolyEmbedding: defines the bounded polynomial-pair embedding used for the combined measurement.
  • MIPStarRE.QPBT.combinedPairSubmeasurement: restricts an extended-polynomial measurement to combined polynomial-pair outcomes.
  • MIPStarRE.QPBT.completedPairLabel: relabels a combined polynomial by its unique pair and sends other outcomes to a specified fallback pair.
  • MIPStarRE.QPBT.completedPairMeasurement: defines the completed polynomial-pair measurement after relabeling all extended outcomes.
  • MIPStarRE.QPBT.recoverCombinedPair_combinePoly: states that substitution recovers both components of a combined polynomial.
  • MIPStarRE.QPBT.combinePoly_injective: states that distinct polynomial pairs label distinct combined outcomes.
  • MIPStarRE.QPBT.completedPairLabel_combinedPolyEmbedding: states that completion preserves the pair label of every combined polynomial.

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/Combining/PairCompletion.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_Preliminaries_Polynomials
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_LIDT_MIPStarRE_Quantum_Measurement
import Definitions.Def_QPBT_QPBT_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Combining_Defs
import Definitions.Def_QPBT_QPBT_Test_LowDegreeGameMeasurements
import Definitions.Def_QPBT_QPBT_Test_PauliBasisTest
import Mathlib

namespace LIDT.MIPStarRE.Quantum
end LIDT.MIPStarRE.Quantum
namespace MIPStarRE.QPBT
end MIPStarRE.QPBT
namespace MIPStarRE.QPBT.DistanceCalculus
end MIPStarRE.QPBT.DistanceCalculus

/-!
# Restricting and completing global polynomial-pair measurements

The combining map embeds pairs of bounded individual-degree polynomials into
extended polynomials. Restricting a measurement along this embedding produces a
submeasurement whose missing operator is the sum of the noncombined effects.
Relabeling those effects by one specified pair completes the measurement and
preserves projectivity.

These algebraic constructions do not establish the concentration estimate
`eq:qld-g-non-separable` or the point consistency required by
`exists_globalPairWitness`; those are separate quantitative obligations.

## References

- Blueprint `lem:qld-4-7`.
- `references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1375-1404`,
  `eq:qld-sgg-completeness` and the final completion paragraph.
-/

@[expose] public section

namespace MIPStarRE.QPBT

open scoped BigOperators MatrixOrder

noncomputable section

/-- Recover the two polynomial components by setting the unused block to zero
and the scalar coordinates to `(1,0)` or `(0,1)`. This algebraic substitution
is the left inverse implicit in the restriction to combined outcomes in
`eq:qld-sgg-completeness`, paper lines 1375--1380. Unlike evaluation as a
polynomial function on a finite field, it does not require a degree bound. -/
noncomputable def recoverCombinedPair {K : Type*} [CommSemiring K] {m : ℕ}
    (polynomial : MvPolynomial (Fin (2 * m + 2)) K) :
    MvPolynomial (Fin m) K × MvPolynomial (Fin m) K :=
  (MvPolynomial.eval₂ MvPolynomial.C (fun index =>
    match _root_.MIPStarRE.QPBT.finCombineEquiv m index with
    | .inl (.inl coordinate) => MvPolynomial.X coordinate
    | .inl (.inr _) => 0
    | .inr scalar => if scalar = 0 then 1 else 0) polynomial,
   MvPolynomial.eval₂ MvPolynomial.C (fun index =>
    match _root_.MIPStarRE.QPBT.finCombineEquiv m index with
    | .inl (.inl _) => 0
    | .inl (.inr coordinate) => MvPolynomial.X coordinate
    | .inr scalar => if scalar = 1 then 1 else 0) polynomial)

/-- Substitution recovers both components of a combined polynomial. This is
formalization support for the relabeling in `eq:qld-sgg-completeness`, paper
lines 1375--1380. -/
@[simp] theorem recoverCombinedPair_combinePoly {K : Type*} [CommSemiring K] {m : ℕ}
    (first second : MvPolynomial (Fin m) K) :
    _root_.MIPStarRE.QPBT.recoverCombinedPair (_root_.MIPStarRE.QPBT.combinePoly first second) = (first, second) := by
  simp [_root_.MIPStarRE.QPBT.recoverCombinedPair, _root_.MIPStarRE.QPBT.combinePoly, MvPolynomial.eval₂_rename,
    _root_.MIPStarRE.QPBT.embX, _root_.MIPStarRE.QPBT.embZ, _root_.MIPStarRE.QPBT.alphaVar, _root_.MIPStarRE.QPBT.betaVar, Function.comp_def, MvPolynomial.eval₂_eta]

/-- Distinct polynomial pairs label distinct combined outcomes. This justifies
restricting a measurement on extended polynomials to pairs without duplicating
an effect in `eq:qld-sgg-completeness`, paper lines 1375--1380. -/
theorem combinePoly_injective {K : Type*} [CommSemiring K] {m : ℕ} :
    Function.Injective (fun pair : MvPolynomial (Fin m) K × MvPolynomial (Fin m) K =>
      _root_.MIPStarRE.QPBT.combinePoly pair.1 pair.2) := by
  exact (show Function.LeftInverse _root_.MIPStarRE.QPBT.recoverCombinedPair
    (fun pair : MvPolynomial (Fin m) K × MvPolynomial (Fin m) K =>
      _root_.MIPStarRE.QPBT.combinePoly pair.1 pair.2) from fun pair =>
        _root_.MIPStarRE.QPBT.recoverCombinedPair_combinePoly pair.1 pair.2).injective

/-- The bounded polynomial-pair embedding used to restrict the global
measurement in `eq:qld-sgg-completeness`, paper lines 1375--1380. The degree
bound is inherited from `def:combine-map`; the two scalar coordinates have
degree one, allowed by admissibility. -/
noncomputable def combinedPolyEmbedding (P : _root_.MIPStarRE.QPBT.AdmissibleParams) :
    _root_.MIPStarRE.QPBT.PolyPair P ↪ _root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc (2 * P.m + 2) (_root_.MIPStarRE.QPBT.PauliScalar P) P.d where
  toFun pair := ⟨_root_.MIPStarRE.QPBT.combinePoly pair.1.1 pair.2.1,
    _root_.MIPStarRE.QPBT.combinePoly_mem_polyFunc P.hd pair.1.2 pair.2.2⟩
  inj' := by
    intro first second heq
    have hpoly : _root_.MIPStarRE.QPBT.combinePoly first.1.1 first.2.1 = _root_.MIPStarRE.QPBT.combinePoly second.1.1 second.2.1 :=
      congrArg Subtype.val heq
    have hpair : (first.1.1, first.2.1) = (second.1.1, second.2.1) :=
      _root_.MIPStarRE.QPBT.combinePoly_injective hpoly
    exact Prod.ext (Subtype.ext (congrArg Prod.fst hpair))
      (Subtype.ext (congrArg Prod.snd hpair))



/-- Restrict an extended-polynomial measurement to combined outcomes, as in
`eq:qld-sgg-completeness`, paper lines 1375--1380. Injectivity of the combining
map ensures that the retained effects sum to at most the identity. This
construction does not assert the source's quantitative completeness bound. -/
noncomputable def combinedPairSubmeasurement (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    {carrier : Type*} [Fintype carrier] [DecidableEq carrier]
    (measurement : _root_.LIDT.MIPStarRE.Quantum.Measurement
      (_root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc (2 * P.m + 2) (_root_.MIPStarRE.QPBT.PauliScalar P) P.d) carrier) :
    _root_.LIDT.MIPStarRE.Quantum.Submeasurement (_root_.MIPStarRE.QPBT.PolyPair P) carrier where
  effect pair := measurement.effect (_root_.MIPStarRE.QPBT.combinedPolyEmbedding P pair)
  pos pair := measurement.pos _
  sum_le_one := by
    classical
    rw [← Finset.sum_image (fun first _ second _ heq =>
      (_root_.MIPStarRE.QPBT.combinedPolyEmbedding P).injective heq)]
    exact (Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)
      (fun outcome _ _ => measurement.pos outcome)).trans measurement.sum_le_one





/-- Relabel a combined polynomial by its unique pair and send every other
polynomial to a specified pair. This implements the completion at an arbitrary
outcome in the last paragraph of `lem:qld-4-7`, paper lines 1402--1404. The
noncombined outcomes are retained at the completion outcome, not discarded. -/
noncomputable def completedPairLabel (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (completionPair : _root_.MIPStarRE.QPBT.PolyPair P) :
    _root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc (2 * P.m + 2) (_root_.MIPStarRE.QPBT.PauliScalar P) P.d → _root_.MIPStarRE.QPBT.PolyPair P :=
  Function.extend (_root_.MIPStarRE.QPBT.combinedPolyEmbedding P) id (fun _ => completionPair)

/-- Completion preserves every combined polynomial's pair label. -/
@[simp] theorem completedPairLabel_combinedPolyEmbedding (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    (completionPair pair : _root_.MIPStarRE.QPBT.PolyPair P) :
    _root_.MIPStarRE.QPBT.completedPairLabel P completionPair (_root_.MIPStarRE.QPBT.combinedPolyEmbedding P pair) = pair := by
  exact (_root_.MIPStarRE.QPBT.combinedPolyEmbedding P).injective.extend_apply _ _ _



/-- The completed polynomial-pair measurement of the final paragraph of
`lem:qld-4-7`, paper lines 1402--1404, obtained by relabeling all extended
polynomial outcomes. No assertion about consistency is built into this
construction. -/
noncomputable def completedPairMeasurement (P : _root_.MIPStarRE.QPBT.AdmissibleParams)
    {carrier : Type*} [Fintype carrier] [DecidableEq carrier]
    (measurement : _root_.LIDT.MIPStarRE.Quantum.Measurement
      (_root_.LIDT.MIPStarRE.LDT.Preliminaries.polyFunc (2 * P.m + 2) (_root_.MIPStarRE.QPBT.PauliScalar P) P.d) carrier)
    (completionPair : _root_.MIPStarRE.QPBT.PolyPair P) : _root_.LIDT.MIPStarRE.Quantum.Measurement (_root_.MIPStarRE.QPBT.PolyPair P) carrier :=
  measurement.postprocess (_root_.MIPStarRE.QPBT.completedPairLabel P completionPair)





open LIDT.MIPStarRE.Quantum DistanceCalculus





end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Combining/PairCompletion.lean#L34-L195

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