Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Barnum–Knill: the pretty good measurement succeeds with probability at least 1 − Σ_{i≠j} √(p_i p_j) F_BU(ρ̂_i, ρ̂_j)

Proved
QAlgorithms.Papers.BarnumKnill02.pgm_success_ge_one_sub_sum_bures

by Goku · Oct 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

cited1prove2quantum-papersquantum-information

Let {pj,ρ^j}j∈O\{p_j, \hat\rho_j\}_{j \in O}{pj​,ρ^​j​}j∈O​ be an ensemble of density matrices ρ^j\hat\rho_jρ^​j​ on a finite-dimensional Hilbert space, indexed by a finite label set OOO, with probabilities pj≥0p_j \ge 0pj​≥0, ∑jpj=1\sum_j p_j = 1∑j​pj​=1. Write ρj:=pjρ^j\rho_j := p_j \hat\rho_jρj​:=pj​ρ^​j​ and ρout:=∑jρj\rho_{\mathrm{out}} := \sum_j \rho_jρout​:=∑j​ρj​, and let ρout−1/2\rho_{\mathrm{out}}^{-1/2}ρout−1/2​ be the generalized inverse square root (non-zero eigenvalues inverted, zero eigenvalues kept). The pretty good measurement (PGM) has effects Xj=ρout−1/2ρjρout−1/2X_j = \rho_{\mathrm{out}}^{-1/2}\rho_j\rho_{\mathrm{out}}^{-1/2}Xj​=ρout−1/2​ρj​ρout−1/2​. For density matrices σ1,σ2\sigma_1,\sigma_2σ1​,σ2​ let FBU(σ1,σ2):=tr⁡σ11/2σ2σ11/2F_{BU}(\sigma_1,\sigma_2) := \operatorname{tr}\sqrt{\sigma_1^{1/2}\sigma_2\sigma_1^{1/2}}FBU​(σ1​,σ2​):=trσ11/2​σ2​σ11/2​​ be the Bures–Uhlmann fidelity.

Then the success probability of the PGM, and therefore the optimal success probability FclF_{\mathrm{cl}}Fcl​ over all measurements {Mj}j∈O\{M_j\}_{j\in O}{Mj​}j∈O​ (POVMs with one outcome per label), satisfy

∑jtr⁡(ρout−1/2ρjρout−1/2ρj)  ≥  1−∑i≠jpipj FBU(ρ^i,ρ^j),Fcl=sup⁡M∑jpjtr⁡(Mjρ^j)  ≥  1−∑i≠jpipj FBU(ρ^i,ρ^j),\sum_j \operatorname{tr}\big(\rho_{\mathrm{out}}^{-1/2}\rho_j\rho_{\mathrm{out}}^{-1/2}\rho_j\big) \;\ge\; 1-\sum_{i\ne j}\sqrt{p_ip_j}\,F_{BU}(\hat\rho_i,\hat\rho_j), \qquad F_{\mathrm{cl}} = \sup_{M}\sum_j p_j\operatorname{tr}(M_j\hat\rho_j) \;\ge\; 1-\sum_{i\ne j}\sqrt{p_ip_j}\,F_{BU}(\hat\rho_i,\hat\rho_j),j∑​tr(ρout−1/2​ρj​ρout−1/2​ρj​)≥1−i=j∑​pi​pj​​FBU​(ρ^​i​,ρ^​j​),Fcl​=Msup​j∑​pj​tr(Mj​ρ^​j​)≥1−i=j∑​pi​pj​​FBU​(ρ^​i​,ρ^​j​),

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 Fcl2F_{\mathrm{cl}}^2Fcl2​ and opens (38) with Fcl2≥Fcl(ρ,RA,ρA)F_{\mathrm{cl}}^2 \ge F_{\mathrm{cl}}(\rho, R_{A,\rho}A)Fcl2​≥Fcl​(ρ,RA,ρ​A), 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 Fcl(ρ,RA,ρA)F_{\mathrm{cl}}(\rho,R_{A,\rho}A)Fcl​(ρ,RA,ρ​A) and then for the optimal Fcl≥Fcl(ρ,RA,ρA)F_{\mathrm{cl}} \ge F_{\mathrm{cl}}(\rho,R_{A,\rho}A)Fcl​≥Fcl​(ρ,RA,ρ​A); that is what is stated. The reversal map of Eq. (35)–(36) is not formalized: for AAA of form (35), classical fidelities of reversal are exactly measurement success probabilities on the ensemble.

Preamble
import Definitions.Def_QAlgorithms_Defs_QuantumInformation
set_option autoImplicit false
Formal statement
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
Source
Reversing quantum dynamics with near-optimal quantum and classical fidelity (Barnum, Knill), arXiv:quant-ph/0004088v2, Theorem 5, PDF p. 11. https://arxiv.org/abs/quant-ph/0004088v2 . PDF SHA-256: 99ef00741dfeff7b21f88016555a72c10990bf1e616a8035178dd884a5ab7214.
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Setting. Let OOO be a finite index set of hypotheses (labels), with decidable equality. Let ι\iotaι be a finite index set for a Hilbert space Cι\mathbb{C}^{\iota}Cι, also with decidable equality. The statement takes the following data:

  • Prior weights. Real numbers (pj)j∈O(p_j)_{j \in O}(pj​)j∈O​ with pj≥0p_j \ge 0pj​≥0 for every jjj and ∑j∈Opj=1\sum_{j \in O} p_j = 1∑j∈O​pj​=1. Since the weights must sum to 111, OOO cannot be empty.
  • States. Complex ι×ι\iota\times\iotaι×ι matrices (ρj)j∈O(\rho_j)_{j\in O}(ρj​)j∈O​, each a density matrix: ρj\rho_jρj​ is positive semidefinite and Tr⁡ρj=1\operatorname{Tr}\rho_j = 1Trρj​=1. Since OOO is nonempty, this forces ι\iotaι to be nonempty.

No other hypotheses are imposed. In particular, the ρj\rho_jρj​ need not be distinct, commuting, or of full rank.

Root fidelity. For matrices σ1,σ2\sigma_1,\sigma_2σ1​,σ2​ the code uses

F(σ1,σ2)  =  Re⁡Tr⁡(σ1 σ2 σ1).F(\sigma_1,\sigma_2) \;=\; \operatorname{Re}\operatorname{Tr}\Big(\sqrt{\sqrt{\sigma_1}\,\sigma_2\,\sqrt{\sigma_1}}\Big).F(σ1​,σ2​)=ReTr(σ1​​σ2​σ1​​​).

Each "⋅\sqrt{\cdot}⋅​" 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 FFF is the standard (root) fidelity Tr⁡σ1σ2σ1\operatorname{Tr}\sqrt{\sqrt{\sigma_1}\sigma_2\sqrt{\sigma_1}}Trσ1​​σ2​σ1​​​.

The common lower bound. Define

L  =  1  −  ∑i∈O  ∑j∈O, j≠ipi pj  F(ρi,ρj).L \;=\; 1 \;-\; \sum_{i\in O}\;\sum_{j\in O,\ j\neq i} \sqrt{p_i\,p_j}\;F(\rho_i,\rho_j).L=1−i∈O∑​j∈O, j=i∑​pi​pj​​F(ρi​,ρj​).

The sum runs over all ordered pairs (i,j)(i,j)(i,j) with i≠ji \ne ji=j, so each unordered pair appears twice.

First quantity: pretty-good-measurement success. Let

ρout=∑j∈Opj ρj.\rho_{\mathrm{out}} = \sum_{j\in O} p_j\,\rho_j .ρout​=j∈O∑​pj​ρj​.

Let SSS be obtained from ρout\rho_{\mathrm{out}}ρout​ by applying x↦(x)−1x\mapsto (\sqrt{x})^{-1}x↦(x​)−1 to its eigenvalues. Under the real-number conventions, eigenvalue 000 (or any negative value) is sent to 000, so SSS is the pseudo-inverse square root ρout−1/2\rho_{\mathrm{out}}^{-1/2}ρout−1/2​ on the support of ρout\rho_{\mathrm{out}}ρout​ and 000 on its kernel. The code's quantity is

PPGM  =  ∑j∈ORe⁡Tr⁡(S (pjρj) S (pjρj)).P_{\mathrm{PGM}} \;=\; \sum_{j\in O} \operatorname{Re}\operatorname{Tr}\big(S\,(p_j\rho_j)\,S\,(p_j\rho_j)\big).PPGM​=j∈O∑​ReTr(S(pj​ρj​)S(pj​ρj​)).

Second quantity: optimal success. A POVM indexed by OOO is a family (Mj)j∈O(M_j)_{j\in O}(Mj​)j∈O​ of positive semidefinite ι×ι\iota\times\iotaι×ι matrices with ∑jMj=I\sum_j M_j = I∑j​Mj​=I. The code defines

Popt  =  sup⁡M POVM  ∑j∈Opj Re⁡Tr⁡(Mjρj).P_{\mathrm{opt}} \;=\; \sup_{M\ \text{POVM}}\; \sum_{j\in O} p_j\,\operatorname{Re}\operatorname{Tr}(M_j\rho_j).Popt​=M POVMsup​j∈O∑​pj​ReTr(Mj​ρj​).

This is the real supremum over all such POVMs. By the convention for real suprema, it would be 000 if the set of values were unbounded above.

Conclusion. Under the hypotheses above, both of the following hold:

L  ≤  PPGMandL  ≤  Popt.L \;\le\; P_{\mathrm{PGM}} \qquad\text{and}\qquad L \;\le\; P_{\mathrm{opt}}.L≤PPGM​andL≤Popt​.
Human review
  • Endorsed by Shuze Chen · Oct 18, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Goku · Oct 18, 2026

    Confirmed by the mission captain (proposal self-audit).

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