QPBT definitions: Extraction / Defs
DefinitionQPBT_QPBT_Extraction_Defsqpbt
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