Simple Algorithm
Quantum Computing · Rydberg State · 28 min

State Discrimination & the Helstrom Bound

The best possible way to tell two states apart.

You are handed one copy of a state that is either ρ0\rho_0 or ρ1\rho_1. How well can you guess which? The answer, the Helstrom bound, takes one line, and it anchors a whole theory: many hypotheses, error-free (unambiguous) discrimination, many copies, and the quantum Chernoff and Stein exponents.

What you’ll learn

  • Derive the Helstrom–Holevo bound and construct the optimal measurement.
  • Formulate multi-hypothesis discrimination as a semidefinite program, with the Holevo–Yuen–Kennedy–Lax optimality conditions and the pretty good measurement.
  • Prove the Ivanovic–Dieks–Peres bound for unambiguous discrimination.
  • State the asymptotic error exponents: the quantum Chernoff bound and quantum Stein's lemma.

Two hypotheses: the Helstrom–Holevo bound

A source emits ρ0\rho_0 with prior probability p0p_0, or ρ1\rho_1 with p1=1−p0p_1 = 1-p_0. You measure a two-outcome POVM {E0, E1=I−E0}\{E_0,\ E_1 = \id-E_0\} and guess according to the outcome.

DerivationOptimal success probability
  1. Psucc=p0Tr⁡(E0ρ0)+p1Tr⁡((I−E0)ρ1)=p1+Tr⁡(E0 Γ),Γ:=p0ρ0−p1ρ1P_{\text{succ}} = p_0\Tr(E_0\rho_0)+p_1\Tr\big((\id-E_0)\rho_1\big) = p_1+\Tr\big(E_0\,\Gamma\big),\qquad \Gamma := p_0\rho_0-p_1\rho_1

    Everything depends on the Hermitian Helstrom operator Γ\Gamma.

  2. max⁡0≤E0≤ITr⁡(E0Γ)=Tr⁡Γ+\max_{0\le E_0\le\id}\Tr(E_0\Gamma) = \Tr\Gamma_+

    Take E0E_0 to be the projector onto the positive eigenspace of Γ\Gamma, exactly as in the proof that trace distance is the best bias.

  3. Tr⁡Γ+=12(∥Γ∥1+Tr⁡Γ)=12(∥Γ∥1+p0−p1)\Tr\Gamma_+ = \tfrac12\big(\norm{\Gamma}_1+\Tr\Gamma\big) = \tfrac12\big(\norm{\Gamma}_1+p_0-p_1\big)

    Because Γ=Γ+−Γ−\Gamma = \Gamma_+-\Gamma_- and ∥Γ∥1=Tr⁡Γ++Tr⁡Γ−\norm{\Gamma}_1 = \Tr\Gamma_++\Tr\Gamma_-.

  4. Psuccopt=12(1+∥p0ρ0−p1ρ1∥1)P_{\text{succ}}^{\text{opt}} = \tfrac12\Big(1+\norm{p_0\rho_0-p_1\rho_1}_1\Big)

    Using p1+12(p0−p1)=12p_1+\tfrac12(p_0-p_1) = \tfrac12. For equal priors this is 12(1+D(ρ0,ρ1))\tfrac12\big(1+D(\rho_0,\rho_1)\big), with DD the trace distance.

Predict before you look

Equal priors, ∣ψ0⟩=∣0⟩\ket{\psi_0} = \ket0 and ∣ψ1⟩=cos⁡θ2∣0⟩+sin⁡θ2∣1⟩\ket{\psi_1} = \cos\tfrac\theta2\ket0+\sin\tfrac\theta2\ket1 with θ=60∘\theta = 60^\circ. What is the optimal success probability?

Show the answer

0.75

s=cos⁡30∘=32s = \cos30^\circ = \tfrac{\sqrt3}2, so P=12(1+1−34)=12(1+12)=34P = \tfrac12\big(1+\sqrt{1-\tfrac34}\big) = \tfrac12\big(1+\tfrac12\big) = \tfrac34. On the Bloch sphere the two states are 60∘60^\circ apart, and D=12∣r⃗0−r⃗1∣=sin⁡30∘=12D = \tfrac12\abs{\vec r_0-\vec r_1} = \sin30^\circ = \tfrac12.

For qubits with equal priors, the optimal measurement is the observable n^⋅σ⃗\hat n\cdot\vec\sigma with n^∝r⃗0−r⃗1\hat n\propto\vec r_0-\vec r_1: guess ρ0\rho_0 on outcome +1+1. Priors matter, too. If Γ≥0\Gamma\ge0, then ∥Γ∥1=p0−p1\norm{\Gamma}_1 = p_0-p_1 and the optimum Psucc=p0P_{\text{succ}} = p_0 is reached by ignoring the system and always guessing ρ0\rho_0: a measurement helps only when it can overturn the prior.

Many hypotheses: a semidefinite program

For mm states ρi\rho_i with priors pip_i, the optimal success probability is a semidefinite program (SDP), and its dual certifies optimality:

Psuccopt=max⁡Ei≥0∑iEi=I ∑ipiTr⁡(Eiρi) = min⁡Z : Z≥piρi ∀i Tr⁡ZP^{\text{opt}}_{\text{succ}} = \max_{\substack{E_i\ge0\\ \sum_iE_i = \id}}\ \sum_ip_i\Tr(E_i\rho_i)\ =\ \min_{Z\,:\ Z\ge p_i\rho_i\ \forall i}\ \Tr Z
Weak duality takes one line: ∑ipiTr⁡(Eiρi)≤∑iTr⁡(EiZ)=Tr⁡Z\sum_ip_i\Tr(E_i\rho_i)\le\sum_i\Tr(E_iZ) = \Tr Z, because Z−piρi≥0Z-p_i\rho_i\ge0 and Ei≥0E_i\ge0. Both problems are strictly feasible, so strong duality holds and the two values agree.
Check your understanding

Five equiprobable states of a qubit, otherwise arbitrary. What is the best upper bound, valid for every such ensemble, on the success probability of any measurement?

  1. 11
  2. 1/21/2
  3. 2/52/5
  4. 1/51/5
Show the answer

C. 2/52/5

Psucc=15∑iTr⁡(Eiρi)≤15∑iTr⁡Ei=15Tr⁡I=25P_{\text{succ}} = \tfrac15\sum_i\Tr(E_i\rho_i)\le\tfrac15\sum_i\Tr E_i = \tfrac15\Tr\id = \tfrac25. The bound is attained, for example, by five pure states equally spaced on a great circle of the Bloch sphere, measured with their PGM.

Unambiguous discrimination

DerivationProof of the bound
  1. ⟨ψ0∣ψ1⟩=⟨ψ0∣(E0+E1+E?)∣ψ1⟩=⟨ψ0∣E?∣ψ1⟩\braket{\psi_0|\psi_1} = \bra{\psi_0}\big(E_0+E_1+E_?\big)\ket{\psi_1} = \bra{\psi_0}E_?\ket{\psi_1}

    Let {E0,E1,E?}\{E_0,E_1,E_?\} be error-free: ⟨ψ1∣E0∣ψ1⟩=0\bra{\psi_1}E_0\ket{\psi_1} = 0, which forces E0∣ψ1⟩=0E_0\ket{\psi_1} = 0 because E0≥0E_0\ge0; likewise E1∣ψ0⟩=0E_1\ket{\psi_0} = 0. Therefore

  2. s2≤q0 q1≤(q0+q12)2s^2\le q_0\,q_1\le\Big(\frac{q_0+q_1}{2}\Big)^2

    Apply Cauchy–Schwarz to the positive semidefinite form (u,v)↦⟨u∣E?∣v⟩(u,v)\mapsto\bra uE_?\ket v, with qi=⟨ψi∣E?∣ψi⟩q_i = \bra{\psi_i}E_?\ket{\psi_i} the probability of an inconclusive result on ∣ψi⟩\ket{\psi_i}, then AM–GM:

  3. With equal priors Psucc=1−12(q0+q1)≤1−sP_{\text{succ}} = 1-\tfrac12(q_0+q_1)\le1-s. □\square Achievability: the three-outcome POVM of the Excited State lesson, realized by the two-qubit circuit in Naimark Dilation.

With unequal priors p0≤p1p_0\le p_1, the optimum is 1−2p0p1 s1-2\sqrt{p_0p_1}\,s as long as s≤p0/p1s\le\sqrt{p_0/p_1}. Beyond that threshold it is better to give up on the less likely state and use a projective measurement that only ever identifies ∣ψ1⟩\ket{\psi_1}, succeeding with probability p1(1−s2)p_1(1-s^2) (Jaeger & Shimony 1995). For more than two states, pure states can be unambiguously discriminated, each with nonzero success probability, iff they are linearly independent (Chefles 1998).

Figure of meritOptimum for ∣0⟩\ket0 vs ∣+⟩\ket+, equal priorsOptimal measurement
Minimum error (Helstrom)success cos⁡2π8≈0.854\cos^2\tfrac\pi8\approx0.854, error ≈0.146\approx0.146projective
Unambiguous (Ivanovic–Dieks–Peres)success 1−12≈0.2931-\tfrac1{\sqrt2}\approx0.293, never wrong, inconclusive ≈0.707\approx0.707three-outcome POVM
Unambiguous, projective onlysuccess 0.250.25measure ZZ (or XX)

Many copies: error exponents

With nn copies, ρi→ρi⊗n\rho_i\to\rho_i^{\otimes n}, and the optimal error falls exponentially in nn. Two regimes are fully understood.

For pure states Tr⁡(ρ0αρ11−α)=∣⟨ψ0∣ψ1⟩∣2\Tr\big(\rho_0^\alpha\rho_1^{1-\alpha}\big) = \abs{\braket{\psi_0|\psi_1}}^2 for every 0<α<10<\alpha<1, so ξQCB=−log⁡∣⟨ψ0∣ψ1⟩∣2\xi_{\text{QCB}} = -\log\abs{\braket{\psi_0|\psi_1}}^2. This matches the exact nn-copy Helstrom error for equal priors, 12(1−1−s2n)≈14s2n\tfrac12\big(1-\sqrt{1-s^{2n}}\big)\approx\tfrac14s^{2n}, since nn copies have overlap sns^n.

Attaining these exponents generally requires collective measurements across the copies. For two pure states, however, measuring one copy at a time with adaptive feed-forward (Bayesian updating of the prior) already attains the optimal nn-copy error; for mixed states, such local strategies can fall short of the collective optimum.

Key takeaways

  • Helstrom–Holevo: Psuccopt=12(1+∥p0ρ0−p1ρ1∥1)P_{\text{succ}}^{\text{opt}} = \tfrac12\big(1+\norm{p_0\rho_0-p_1\rho_1}_1\big), achieved by projecting onto the positive part of p0ρ0−p1ρ1p_0\rho_0-p_1\rho_1.
  • Many hypotheses: an SDP whose dual certificate Z≥piρiZ\ge p_i\rho_i gives the Holevo–Yuen–Kennedy–Lax conditions; the pretty good measurement is within a square of optimal.
  • Unambiguous discrimination of two equiprobable pure states succeeds with probability at most 1−∣⟨ψ0∣ψ1⟩∣1-\abs{\braket{\psi_0|\psi_1}}, which requires a genuine POVM.
  • With nn copies, errors decay exponentially: with the Chernoff exponent −log⁡min⁡αTr⁡ρ0αρ11−α-\log\min_\alpha\Tr\rho_0^\alpha\rho_1^{1-\alpha} (symmetric) or the relative entropy (Stein, asymmetric).

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

Equal priors, ρ0=∣0⟩ ⁣⟨0∣\rho_0 = \dyad0 and ρ1=I/2\rho_1 = \id/2. What is the optimal success probability?

  1. 1/21/2
  2. 3/43/4
  3. cos⁡2π8≈0.854\cos^2\tfrac\pi8\approx0.854
  4. 11
Show the answer

B. 3/43/4

D(∣0⟩ ⁣⟨0∣,I/2)=12∣z^−0⃗∣=12D(\dyad0,\id/2) = \tfrac12\abs{\hat z-\vec0} = \tfrac12, so P=12(1+12)=34P = \tfrac12\big(1+\tfrac12\big) = \tfrac34. Concretely: measure ZZ, guess ρ0\rho_0 on 00 and ρ1\rho_1 on 11.

Question 2

For two pure states with overlap s=∣⟨ψ0∣ψ1⟩∣<1s = \abs{\braket{\psi_0|\psi_1}}<1 and equal priors, how does the minimum error probability for nn copies decay?

  1. As s2ns^{2n} up to a constant, i.e. with Chernoff exponent −log⁡∣⟨ψ0∣ψ1⟩∣2-\log\abs{\braket{\psi_0|\psi_1}}^2
  2. As sns^n
  3. Polynomially, like 1/n1/n
  4. As (1−s)n(1-s)^n
Show the answer

A. As s2ns^{2n} up to a constant, i.e. with Chernoff exponent −log⁡∣⟨ψ0∣ψ1⟩∣2-\log\abs{\braket{\psi_0|\psi_1}}^2

The nn-copy states have overlap sns^n, so Perr=12(1−1−s2n)≈14s2nP_{\text{err}} = \tfrac12\big(1-\sqrt{1-s^{2n}}\big)\approx\tfrac14s^{2n}, matching ξQCB=−log⁡s2\xi_{\text{QCB}} = -\log s^2.

Question 3

Which statement about the pretty good measurement (PGM) is correct?

  1. It is optimal for every ensemble
  2. It always succeeds with probability at least 1/21/2
  3. It is defined only for commuting states
  4. It satisfies PsuccPGM≥(Psuccopt)2P^{\text{PGM}}_{\text{succ}}\ge\big(P^{\text{opt}}_{\text{succ}}\big)^2 for every ensemble
Show the answer

D. It satisfies PsuccPGM≥(Psuccopt)2P^{\text{PGM}}_{\text{succ}}\ge\big(P^{\text{opt}}_{\text{succ}}\big)^2 for every ensemble

The Barnum–Knill bound makes the PGM near-optimal whenever the optimum is close to 1. It is exactly optimal for geometrically uniform pure-state ensembles, but not in general.

Question 4

In quantum Stein's lemma, which quantity is the optimal exponent of the type-II error?

  1. The trace distance D(ρ0,ρ1)D(\rho_0,\rho_1)
  2. −log⁡F(ρ0,ρ1)-\log F(\rho_0,\rho_1)
  3. The relative entropy D(ρ0∥ρ1)=Tr⁡ρ0(log⁡ρ0−log⁡ρ1)D(\rho_0\|\rho_1) = \Tr\rho_0(\log\rho_0-\log\rho_1)
  4. The Chernoff exponent ξQCB\xi_{\text{QCB}}
Show the answer

C. The relative entropy D(ρ0∥ρ1)=Tr⁡ρ0(log⁡ρ0−log⁡ρ1)D(\rho_0\|\rho_1) = \Tr\rho_0(\log\rho_0-\log\rho_1)

With the type-I error held below a constant, the type-II error decays as e−nD(ρ0∥ρ1)e^{-nD(\rho_0\|\rho_1)}. The Chernoff exponent governs the symmetric setting, where both errors are weighted by priors, and is never larger than the relative entropy.

Further reading

  • C. W. Helstrom, Quantum Detection and Estimation Theory (Academic Press, 1976).
  • A. S. Holevo, "Statistical decision theory for quantum systems", Journal of Multivariate Analysis 3, 337 (1973); H. P. Yuen, R. S. Kennedy & M. Lax, "Optimum testing of multiple hypotheses in quantum detection theory", IEEE Transactions on Information Theory 21, 125 (1975).
  • K. M. R. Audenaert, J. Calsamiglia, R. Muñoz-Tapia, E. Bagan, Ll. Masanes, A. Acín & F. Verstraete, "Discriminating states: the quantum Chernoff bound", Physical Review Letters 98, 160501 (2007).
  • H. Barnum & E. Knill, "Reversing quantum dynamics with near-optimal quantum and classical fidelity", Journal of Mathematical Physics 43, 2097 (2002).
  • S. M. Barnett & S. Croke, "Quantum state discrimination", Advances in Optics and Photonics 1, 238 (2009).