QPBT definitions: Combining / PairCompletion
DefinitionQPBT_QPBT_Combining_PairCompletionqpbt
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