Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

QPBT definitions: Extraction / Defs

Definition
QPBT_QPBT_Extraction_Defs

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

qpbt

This bundle defines the register spaces and operator placements for the Pauli extraction construction. It identifies the two heterogeneous extraction blocks, the auxiliary register grouping, the six-register reassociations, and the lifts of operators from a player's original strategy space.

Principal definitions:

  • MIPStarRE.QPBT.ExtractionBlock: defines one player's register space after adjoining the two generalized-Pauli registers.
  • MIPStarRE.QPBT.ExtractionRegisters: defines the two heterogeneous extraction blocks in the order of Alice's and Bob's full blocks.
  • MIPStarRE.QPBT.ExtractionAuxRegisters: defines the auxiliary AA'BB' register space before the extracted EPR factor.
  • MIPStarRE.QPBT.sixRegExtractionEquiv: reassociates the six-register order with the two extraction blocks.
  • MIPStarRE.QPBT.extractionIdealShuffle: shuffles the auxiliary and EPR factors into the six-register order.
  • MIPStarRE.QPBT.ProjectiveSetting.placeSide: places an operator on one complete extraction block and uses identity on the other player's block.
  • MIPStarRE.QPBT.ProjectiveSetting.onPlayer: lifts an operator on a player's original strategy register to the player's full extraction block.
  • MIPStarRE.QPBT.ProjectiveSetting.placePlayer: places an operator on the selected player's original strategy register.

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/Extraction/Defs.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_Algebra_FieldBasis
import Definitions.Def_QPBT_QPBT_Algebra_LowDegreeCode
import Definitions.Def_QPBT_QPBT_Algebra_Pauli
import Definitions.Def_QPBT_QPBT_Games_Defs
import Definitions.Def_QPBT_QPBT_Observables_Defs
import Definitions.Def_QPBT_QPBT_Observables_ExpandedDefs
import Definitions.Def_QPBT_QPBT_State
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.ProjectiveSetting
end MIPStarRE.QPBT.ProjectiveSetting

/-!
# Extraction foundations

This module defines the register identifications used to pull the Pauli
measurements apart. It retains the distinct local spaces of a
heterogeneous strategy, coarse-grains the generalized Pauli projectors by a
dot product, and records the state and error expressions needed by the later
extraction witness.

The binary phases use the existing `phaseSign`; the fixed field basis remains
the basis stored in `P.model` and is not re-quantified here.

## References

The Pauli dot-product projectors formalize blueprint
`def:tau-dot-product-projector`, from
`references/qpbt-paper/14_analysis_of_the_pauli_basis_test.tex:1426-1429`.
The register and state helpers support blueprint `def:tilde-m-measurement`,
`def:v-swap-unitary`, and `lem:qld-unitary`, from paper lines 1429-1435 and
1666-1713.
-/

@[expose] public section

open scoped BigOperators Matrix

namespace MIPStarRE.QPBT

open LIDT.MIPStarRE.Quantum

noncomputable section

/-! ## Heterogeneous extraction registers -/

/-- One player's registers after adjoining the two generalized-Pauli
registers: `AA'A''` or `BB'B''`. This identifies the register order and spaces for
paper `14_analysis_of_the_pauli_basis_test.tex:1429-1435,1687-1713` and
blueprint `def:tilde-m-measurement` and `def:v-swap-unitary`. -/
abbrev ExtractionBlock (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (ι : Type*) :=
  (ι × _root_.MIPStarRE.QPBT.PauliRegister P) × _root_.MIPStarRE.QPBT.PauliRegister P

/-- The two heterogeneous extraction blocks in the order
`AA'A'' | BB'B''`. This is the block presentation of the existing `SixReg`
space used in blueprint
`lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
abbrev ExtractionRegisters (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (ιA ιB : Type*) :=
  _root_.MIPStarRE.QPBT.ExtractionBlock P ιA × _root_.MIPStarRE.QPBT.ExtractionBlock P ιB

/-- The auxiliary registers `AA'BB'` occurring before the extracted EPR
factor in blueprint `lem:qld-unitary`,
paper `14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
abbrev ExtractionAuxRegisters (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (ιA ιB : Type*) :=
  (ιA × _root_.MIPStarRE.QPBT.PauliRegister P) × (ιB × _root_.MIPStarRE.QPBT.PauliRegister P)

/-- Reassociate the six-register order with the two extraction blocks.
This equivalence identifies the register order in paper
`14_analysis_of_the_pauli_basis_test.tex:1429-1435,1687-1713`. -/
def sixRegExtractionEquiv (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (ιA ιB : Type*) :
    _root_.MIPStarRE.QPBT.SixReg P ιA ιB ≃ _root_.MIPStarRE.QPBT.ExtractionRegisters P ιA ιB where
  toFun p := (((p.1.1, p.1.2.1), p.1.2.2),
    ((p.2.1, p.2.2.1), p.2.2.2))
  invFun p := ((p.1.1.1, (p.1.1.2, p.1.2)),
    (p.2.1.1, (p.2.1.2, p.2.2)))
  left_inv p := by cases p; rfl
  right_inv p := by cases p; rfl

/-- Shuffle `AA'BB' | A''B''` into the six-register order. This equivalence
places the ideal state in the order used in blueprint
`lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
def extractionIdealShuffle (P : _root_.MIPStarRE.QPBT.AdmissibleParams) (ιA ιB : Type*) :
    (_root_.MIPStarRE.QPBT.ExtractionAuxRegisters P ιA ιB ×
      (_root_.MIPStarRE.QPBT.PauliRegister P × _root_.MIPStarRE.QPBT.PauliRegister P)) ≃ _root_.MIPStarRE.QPBT.SixReg P ιA ιB where
  toFun p := ((p.1.1.1, (p.1.1.2, p.2.1)),
    (p.1.2.1, (p.1.2.2, p.2.2)))
  invFun p := (((p.1.1, p.1.2.1), (p.2.1, p.2.2.1)),
    (p.1.2.2, p.2.2.2))
  left_inv p := by cases p; rfl
  right_inv p := by cases p; rfl

namespace ProjectiveSetting

variable {P : _root_.MIPStarRE.QPBT.AdmissibleParams} {ε : ℝ}

/-- Place an operator on one complete extraction block, with the identity on
the other player's block, as in the side-qualified operators of paper
`14_analysis_of_the_pauli_basis_test.tex:1429-1435,1687-1713`. -/
noncomputable def placeSide (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε) (side : _root_.MIPStarRE.QPBT.PlayerSide)
    (O : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.ExtractionBlock P (S.LocalSpace side))) :
    _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB) := by
  cases side with
  | alice =>
      exact _root_.MIPStarRE.QPBT.reindexOp
        (_root_.MIPStarRE.QPBT.sixRegExtractionEquiv P S.toStrategy.ιA S.toStrategy.ιB)
        (_root_.MIPStarRE.QPBT.heteroKron O 1)
  | bob =>
      exact _root_.MIPStarRE.QPBT.reindexOp
        (_root_.MIPStarRE.QPBT.sixRegExtractionEquiv P S.toStrategy.ιA S.toStrategy.ιB)
        (_root_.MIPStarRE.QPBT.heteroKron 1 O)

/-- Lift an operator on a player's original strategy register to that player's
full extraction block. This places the Pauli and point measurements appearing
in blueprint `lem:qld-construct-the-paulis` and `lem:qld-unitary`. -/
noncomputable def onPlayer (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε) (side : _root_.MIPStarRE.QPBT.PlayerSide)
    (O : _root_.LIDT.MIPStarRE.Quantum.Op (S.LocalSpace side)) :
    _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.ExtractionBlock P (S.LocalSpace side)) :=
  _root_.MIPStarRE.QPBT.heteroKron (_root_.MIPStarRE.QPBT.heteroKron O 1) 1

/-- Place an operator on the original strategy register of the selected
player. This is the player-side placement used in blueprint
`lem:qld-unitary`. -/
noncomputable def placePlayer (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε) (side : _root_.MIPStarRE.QPBT.PlayerSide)
    (O : _root_.LIDT.MIPStarRE.Quantum.Op (S.LocalSpace side)) :
    _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB) := by
  cases side with
  | alice => exact S.place .AA' (_root_.MIPStarRE.QPBT.heteroKron O 1)
  | bob => exact S.place .BB' (_root_.MIPStarRE.QPBT.heteroKron O 1)

/-- Place an operator on the selected extracted register `A''` or `B''`.
The unused strategy register in the crossed placement is assigned the
identity. This is the placement of the ideal Pauli operators in
blueprint `lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
noncomputable def placeExtractedRegister (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε)
    (side : _root_.MIPStarRE.QPBT.PlayerSide) (O : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.PauliRegister P)) :
    _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB) := by
  cases side with
  | alice =>
      exact S.place .BA'' (_root_.MIPStarRE.QPBT.heteroKron (1 : _root_.LIDT.MIPStarRE.Quantum.Op S.toStrategy.ιB) O)
  | bob =>
      exact S.place .AB'' (_root_.MIPStarRE.QPBT.heteroKron (1 : _root_.LIDT.MIPStarRE.Quantum.Op S.toStrategy.ιA) O)

/-- Place a pair of block operators simultaneously on `AA'A''` and
`BB'B''`. This is the simultaneous placement used for the transformed state in
blueprint `lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
noncomputable def placeBoth (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε)
    (VA : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.ExtractionBlock P S.toStrategy.ιA))
    (VB : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.ExtractionBlock P S.toStrategy.ιB)) :
    _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB) :=
  _root_.MIPStarRE.QPBT.reindexOp (_root_.MIPStarRE.QPBT.sixRegExtractionEquiv P S.toStrategy.ιA S.toStrategy.ιB)
    (_root_.MIPStarRE.QPBT.heteroKron VA VB)

/-- Apply one operator to each heterogeneous extraction block. This is the
witness-independent state transformation used for `V_A tensor V_B` in
blueprint `lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
noncomputable def applyBoth (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε)
    (VA : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.ExtractionBlock P S.toStrategy.ιA))
    (VB : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.ExtractionBlock P S.toStrategy.ιB))
    (ψ : EuclideanSpace ℂ
      (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB)) :
    EuclideanSpace ℂ (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB) :=
  _root_.MIPStarRE.QPBT.applyOperatorToState (S.placeBoth VA VB) ψ

/-- The state `aux tensor EPR_q^{tensor M}` in the six-register order.
This is the ideal state in Item 1 of blueprint
`lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
noncomputable def idealExpState (S : _root_.MIPStarRE.QPBT.ProjectiveSetting P ε)
    (aux : EuclideanSpace ℂ
      (_root_.MIPStarRE.QPBT.ExtractionAuxRegisters P S.toStrategy.ιA S.toStrategy.ιB)) :
    EuclideanSpace ℂ (_root_.MIPStarRE.QPBT.SixReg P S.toStrategy.ιA S.toStrategy.ιB) := by
  classical
  exact
    _root_.MIPStarRE.QPBT.reindexState (_root_.MIPStarRE.QPBT.extractionIdealShuffle P S.toStrategy.ιA S.toStrategy.ιB)
      (_root_.MIPStarRE.QPBT.vecTensor aux (_root_.MIPStarRE.QPBT.eprState (_root_.MIPStarRE.QPBT.PauliRegister P)))

end ProjectiveSetting

/-! ## Coarse-grained Pauli projectors -/

/-- Coarse-grain a finite operator family along a map of outcomes. This is the
operator-valued sum corresponding to `Measurement.postprocess`, used by
blueprint
`def:tau-dot-product-projector`. -/
noncomputable def bracketOp {α β ι : Type*} [Fintype α] [DecidableEq β]
    (N : α → _root_.LIDT.MIPStarRE.Quantum.Op ι) (f : α → β) (b : β) : _root_.LIDT.MIPStarRE.Quantum.Op ι :=
  ∑ a ∈ Finset.univ.filter (fun a => f a = b), N a



/-- The projector obtained by measuring in basis `W` and retaining outcomes
whose dot product with `u` is `a`. This is Equation `eq:def-tauwu` in
blueprint
`def:tau-dot-product-projector`, paper
`14_analysis_of_the_pauli_basis_test.tex:1426-1429`. -/
noncomputable def tauDotProj {P : _root_.MIPStarRE.QPBT.AdmissibleParams} (W : _root_.MIPStarRE.QPBT.PauliKind)
    (u : _root_.MIPStarRE.QPBT.PauliRegister P) (a : _root_.MIPStarRE.QPBT.PauliScalar P) : _root_.LIDT.MIPStarRE.Quantum.Op (_root_.MIPStarRE.QPBT.PauliRegister P) :=
  _root_.MIPStarRE.QPBT.bracketOp (_root_.MIPStarRE.QPBT.pauliProj W) (fun h => dotProduct h u) a







/-! ## Conjugation and extraction error -/

/-- Conjugation of an operator by a square matrix, as used in the exact
conjugation equations in blueprint
`lem:v-swap-conjugation`, paper
`14_analysis_of_the_pauli_basis_test.tex:1687-1713`. -/
noncomputable def conjBy {ι : Type*} [Fintype ι]
    (V N : _root_.LIDT.MIPStarRE.Quantum.Op ι) : _root_.LIDT.MIPStarRE.Quantum.Op ι :=
  V * N * Vᴴ

/-- The common error scale for constructing the pulled-apart measurements from
a global polynomial-pair witness. Here `deltaG` is its consistency error. The
remaining terms record the point-measurement transfer
and the Schwartz--Zippel loss; when `0 ≤ epsilon ≤ 1`, `sqrt epsilon` also
dominates terms of order `epsilon`.

This makes explicit the enlargement of the error called `deltaS` in
blueprint
`lem:qld-construct-the-paulis`, paper
`14_analysis_of_the_pauli_basis_test.tex:1458-1605`. -/
noncomputable def deltaConstructPaulis (C epsilon deltaG : ℝ)
    (m d q : ℕ) : ℝ :=
  C * (deltaG + Real.sqrt epsilon +
    ((m * d : ℕ) : ℝ) / (q : ℝ))

/-- The explicit extraction scale
`C * (deltaS^(1/4) + md/q)` from blueprint
`lem:qld-unitary`, paper
`14_analysis_of_the_pauli_basis_test.tex:1666-1685`. -/
noncomputable def deltaExtract (C deltaS : ℝ) (m d q : ℕ) : ℝ :=
  C * (Real.rpow deltaS (1 / 4 : ℝ) + ((m * d : ℕ) : ℝ) / (q : ℝ))

end

end MIPStarRE.QPBT
Source
https://github.com/Dengnifer/MIPStarRE-QPBT/blob/8f4118aeea7be16912adbaee3df6dce1741a2c26/QPBT/Extraction/Defs.lean#L39-L307

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