Barnum–Knill: the pretty good measurement succeeds with probability at least 1 − Σ_{i≠j} √(p_i p_j) F_BU(ρ̂_i, ρ̂_j)
ProvedQAlgorithms.Papers.BarnumKnill02.pgm_success_ge_one_sub_sum_buresLet be an ensemble of density matrices on a finite-dimensional Hilbert space, indexed by a finite label set , with probabilities , . Write and , and let be the generalized inverse square root (non-zero eigenvalues inverted, zero eigenvalues kept). The pretty good measurement (PGM) has effects . For density matrices let be the Bures–Uhlmann fidelity.
Then the success probability of the PGM, and therefore the optimal success probability over all measurements (POVMs with one outcome per label), satisfy
the sums running over ordered pairs of distinct labels.
This bound expresses the error of state discrimination through pairwise overlaps only; it is the tool behind the polynomial query complexity of the hidden subgroup problem (Childs, Theorem 10.1).
Formalization Note The paper writes the left side of (39) as and opens (38) with , which is reversed relative to its own Corollary 4 and false in general (two equiprobable pure states with overlap 0.9). Its proof establishes the bound for the PGM success probability and then for the optimal ; that is what is stated. The reversal map of Eq. (35)–(36) is not formalized: for of form (35), classical fidelities of reversal are exactly measurement success probabilities on the ensemble.
import Definitions.Def_QAlgorithms_Defs_QuantumInformation set_option autoImplicit false
namespace QAlgorithms.Papers.BarnumKnill02
/-- Barnum–Knill, Theorem 5 (p.11, Eq. (39), with Eq. (38) and the proof on pp.12–13).
For an ensemble `{p_j, ρ̂_j}` of density matrices with probabilities `p_j` (finitely many labels,
finite dimension), the success probability of the pretty good measurement,
`Σ_j tr(ρ_out^{-1/2} ρ_j ρ_out^{-1/2} ρ_j)` (`mixedPgmSuccess`), and hence the optimal success
probability over all measurements with outcome set the labels (`mixedOptSuccess`), are at least
`1 − Σ_{i ≠ j} √(p_i p_j) F_BU(ρ̂_i, ρ̂_j)`, where `F_BU(σ₁, σ₂) = tr √(σ₁^{1/2} σ₂ σ₁^{1/2})`
(`rootFidelity`).
The paper writes the left side of (39) as `F_cl^2`; its own proof bounds `F_cl(ρ, R_{A,ρ}A)` (the
PGM success probability) and then the optimal `F_cl ≥ F_cl(ρ, R_{A,ρ}A)`, which is what is stated
here (the squared form contradicts Corollary 4 and is false in general). -/
theorem pgm_success_ge_one_sub_sum_bures {O ι : Type*} [Fintype O] [DecidableEq O] [Fintype ι]
[DecidableEq ι] (p : O → ℝ) (hp0 : ∀ j, 0 ≤ p j) (hp1 : ∑ j, p j = 1)
(ρh : O → Matrix ι ι ℂ) (hρ : ∀ j, IsDensityMatrix (ρh j)) :
1 - ∑ i, ∑ j ∈ Finset.univ.erase i, Real.sqrt (p i * p j) * rootFidelity (ρh i) (ρh j) ≤
mixedPgmSuccess p ρh ∧
1 - ∑ i, ∑ j ∈ Finset.univ.erase i, Real.sqrt (p i * p j) * rootFidelity (ρh i) (ρh j) ≤
mixedOptSuccess p ρh := by
sorry
end QAlgorithms.Papers.BarnumKnill02
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Setting. Let be a finite index set of hypotheses (labels), with decidable equality. Let be a finite index set for a Hilbert space , also with decidable equality. The statement takes the following data:
- Prior weights. Real numbers with for every and . Since the weights must sum to , cannot be empty.
- States. Complex matrices , each a density matrix: is positive semidefinite and . Since is nonempty, this forces to be nonempty.
No other hypotheses are imposed. In particular, the need not be distinct, commuting, or of full rank.
Root fidelity. For matrices the code uses
Each "" is the real square root applied to the eigenvalues via the continuous functional calculus. On positive semidefinite matrices this is the usual PSD square root, and the inner matrix is then Hermitian PSD. So for density matrices is the standard (root) fidelity .
The common lower bound. Define
The sum runs over all ordered pairs with , so each unordered pair appears twice.
First quantity: pretty-good-measurement success. Let
Let be obtained from by applying to its eigenvalues. Under the real-number conventions, eigenvalue (or any negative value) is sent to , so is the pseudo-inverse square root on the support of and on its kernel. The code's quantity is
Second quantity: optimal success. A POVM indexed by is a family of positive semidefinite matrices with . The code defines
This is the real supremum over all such POVMs. By the convention for real suprema, it would be if the set of values were unbounded above.
Conclusion. Under the hypotheses above, both of the following hold:
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.