Distinguishability and Testing

1.1 From matrices to decisions

1.1.1 The trace norm as a measurement advantage

Let us begin with a fair choice: each preparation occurs with probability \(1/2\). Measure in the computational basis \(\{\ket{0},\ket{1}\}\). If the preparation was \(\ket{0}\), you certainly observe \(0\). If it was \(\ket{+}\), you observe \(0\) or \(1\) with equal probability. Outcome \(1\) therefore identifies \(\ket{+}\) without ambiguity, whereas outcome \(0\) leaves both preparations possible.

What should we guess when we see \(0\)? Across many trials, half of all runs start with \(\ket{0}\) and produce \(0\), while one quarter start with \(\ket{+}\) and produce \(0\). Conditional on outcome \(0\), \(\ket{0}\) is twice as likely as \(\ket{+}\). Our decision rule should therefore guess \(\ket{0}\) on outcome \(0\) and \(\ket{+}\) on outcome \(1\). Its overall success probability is

This strategy succeeds \(75\%\) of the time, but nothing in the calculation shows that it is optimal. It only evaluates the basis we happened to pick. Rotating the measurement basis can trade a small error on \(\ket{0}\) for a larger gain on \(\ket{+}\). To find the true maximum, we must optimize over every allowed quantum decision.

The optimal success probability will turn out to be governed by the trace norm. Rather than introducing the trace norm as a definition to memorize, let us carry out the optimization that makes it unavoidable.

1.1.2 Writing down every possible decision

Replace our two pure states by arbitrary density operators \(\rho\) and \(\sigma\), prepared with prior probabilities \(p\) and \(1-p\). We receive a single copy, know the candidate states and priors, and must output a definite guess—no “inconclusive” outcome is permitted.

Even if a physical apparatus has many raw detector channels, our final decision has only two labels. Grouping all outcomes that trigger the guess “\(\rho\)” defines a single measurement effect \(M\); the remaining outcomes form \(I-M\). Randomized decision rules are absorbed into the same operator. By the Born rule,

Every valid effect satisfies the operator inequalities \(0\le M\le I\), meaning that both \(M\) and \(I-M\) are positive semidefinite—equivalently, every eigenvalue of \(M\) lies in \([0,1]\). This guarantees nonnegative probabilities summing to \(1\) on every input state. The effect \(M\) need not be a projector; restricting \(M\) to projectors in advance would assume what we intend to prove.

Weighting the two conditional success probabilities by their priors gives

Now the optimization is transparent. The source fixes the Hermitian operator \(H\). We choose \(M\), subject to \(0\le M\le I\), to maximize \(\tr(MH)\). The baseline \(1-p\) is the success probability of blindly guessing \(\sigma\) without touching the system; \(\tr(MH)\) is the exact advantage added by the measurement.

1.1.3 Finding the best measurement

Because \(H\) is Hermitian, it has an orthonormal eigenbasis \(H=\sum_i h_i\ketbra{i}{i}\). Expanding the trace in this eigenbasis gives

Since \(0\le M\le I\), each diagonal expectation value obeys \(0\le\bra{i}M\ket{i}\le 1\). Whenever \(h_i>0\), we maximize the sum by setting \(\bra{i}M\ket{i}=1\); whenever \(h_i<0\), we set \(\bra{i}M\ket{i}=0\). Every valid measurement effect therefore obeys the upper bound

An upper bound is half of an optimality proof; the other half is exhibiting a physical effect that achieves it. Choose \(M_*\) to be the orthogonal projector onto the positive-eigenvalue subspace of \(H\):

Its diagonal entries in the eigenbasis of \(H\) are \(1\) on every positive eigenspace and \(0\) on every negative eigenspace (zero eigenvalues contribute nothing either way), and \(0\le M_*\le I\) holds automatically. Thus a projective measurement in the eigenbasis of \(H\) achieves the global optimum.

To write the maximum in closed form, let \(a=\sum_{h_i>0}h_i\) be the sum of positive eigenvalues of \(H\) and \(b=\sum_{h_i<0}|h_i|\) the sum of the magnitudes of its negative eigenvalues. Then \(\tr H=a-b=p-(1-p)=2p-1\), while the trace norm \(\|H\|_1=\sum_i|h_i|=a+b\). Adding the two relations gives \(a=(\|H\|_1+2p-1)/2\). Substituting \(a\) into \(1-p+a\) yields the Helstrom bound:

For a general operator \(X\), the trace norm is \(\|X\|_1=\tr\sqrt{X^\dagger X}\), the sum of its singular values. For Hermitian \(H\), the singular values are the absolute eigenvalues \(|h_i|\), which is why \(\|H\|_1\) emerged directly from separating positive and negative eigenspaces. By contrast, the operator norm \(\|X\|_\infty\) keeps only the largest singular value; the two norms answer different operational questions.

When the priors are equal (\(p=1/2\)), the formula motivates the definition of the trace distance:

The factor \(1/2\) normalizes \(T(\rho,\sigma)\) to the interval \([0,1]\). Identical states have \(T=0\) and offer no advantage over a coin flip. Orthogonal states have \(T=1\) and can be distinguished in a single shot without error. Between those extremes, \(T(\rho,\sigma)/2\) is the exact maximum probability advantage over random guessing.

1.1.4 Returning to the qubit

We can now resolve our opening qubit question. In the computational basis \((\ket{0},\ket{1})\), the states \(\rho=\ketbra{0}{0}\), \(\sigma=\ketbra{+}{+}\), and their difference \(D=\rho-\sigma\) are

Squaring \(D\) gives \(D^2=I/2\), so the eigenvalues of \(D\) are \(\pm 1/\sqrt2\). Hence \(\|D\|_1=\sqrt2\), and

Our initial \(75\%\) strategy was suboptimal. The positive eigenvector of \(D\) is \(\ket{m_\rho}=\cos(\pi/8)\ket{0}-\sin(\pi/8)\ket{1}\), paired with the orthogonal vector \(\ket{m_\sigma}=\sin(\pi/8)\ket{0}+\cos(\pi/8)\ket{1}\). Instead of aligning the measurement with \(\ket{0}\), the Helstrom basis straddles \(\ket{0}\) and \(\ket{+}\) symmetrically, tilting by \(\pi/8\) (\(22.5^\circ\)) away from each state so both conditional success probabilities equal \(\cos^2(\pi/8)\approx 85.4\%\).

The optimal measurement sacrifices certainty on \(\ket{0}\) to gain a larger improvement on \(\ket{+}\). Even so, the success probability remains strictly below \(1\). That residual error of \(\sin^2(\pi/8)\approx 0.146\) is fundamental: no physical measurement on a single copy can overcome the non-orthogonality of \(\ket{0}\) and \(\ket{+}\).

1.2 Fidelity and physical processing

1.2.1 Why discarding cannot improve a test

Suppose we pass the supplied state through a noisy device before trying to identify it. Could the device make the task easier? It might help a poorly chosen detector, but can it beat the optimal measurement on the original input?

Regard the composite procedure—noisy device followed by output measurement—as a single measurement apparatus acting on the original input. Because our earlier optimization already ranged over every valid input measurement, prepending a fixed physical process cannot increase \(p_{\mathrm{guess}}\). For equal priors, this operational fact immediately yields contractivity of the trace distance:

where \(\mathcal N\) is any quantum channel—a deterministic, trace-preserving completely positive map (developed systematically in Chapter 2).

We can verify the apparatus argument algebraically. If \(M\) is an output measurement effect, the effective input operator is \(\mathcal N^\dagger(M)\), where the Hilbert–Schmidt adjoint \(\mathcal N^\dagger\) is defined by \(\tr[M\mathcal N(\tau)]=\tr[\mathcal N^\dagger(M)\tau]\) for all \(\tau\). Because \(\mathcal N\) is positive and trace-preserving, \(\mathcal N^\dagger\) is positive and unital (\(\mathcal N^\dagger(I)=I\)). Therefore \(0\le M\le I\) implies \(0\le\mathcal N^\dagger(M)\le I\): every output effect pulls back to a valid input effect, so the set of achievable success probabilities can only shrink.

The requirement that \(\mathcal N\) be deterministic (trace-preserving) is essential. If we postselect on a rare heralding outcome and discard failed runs, the surviving renormalized states can have a larger trace distance than the inputs. That postselection probability must be accounted for separately; contractivity applies to the complete trace-preserving process.

1.2.2 Overlap as a second comparison

Trace distance quantifies how well two states can be told apart. Often we ask the complementary question: how closely does a prepared state \(\sigma\) match a pure target state \(\ket{\psi}\)? Measuring the target projector \(\ketbra{\psi}{\psi}\) accepts \(\sigma\) with probability \(\bra{\psi}\sigma\ket{\psi}\).

Extending this overlap test to arbitrary mixed states \(\rho\) and \(\sigma\) defines the Uhlmann fidelity:

Here \(\sqrt\rho\) denotes the unique positive semidefinite square root of \(\rho\). When \(\rho=\ketbra{\psi}{\psi}\) is pure, \(\sqrt\rho=\ketbra{\psi}{\psi}\), and \(\sqrt\rho\sqrt\sigma=\ket{\psi}\bra{\psi}\sqrt\sigma\) is a rank-one operator whose single nonzero singular value is \(\sqrt{\bra{\psi}\sigma\ket{\psi}}\). Squaring its trace norm recovers \(F(\ketbra{\psi}{\psi},\sigma)=\bra{\psi}\sigma\ket{\psi}\). For two pure states \(\ket{\psi}\) and \(\ket{\phi}\), this reduces to the familiar squared overlap \(F=|\braket{\psi}{\phi}|^2\).

Throughout this course, \(F(\rho,\sigma)\) denotes this squared fidelity; some texts call \(\sqrt{F(\rho,\sigma)}=\|\sqrt\rho\sqrt\sigma\|_1\) the fidelity instead. Identical states have \(F=1\), while states with orthogonal supports have \(F=0\). Higher fidelity means greater similarity, whereas higher trace distance means greater distinguishability.

1.2.3 Connecting fidelity to distinguishability

For any two pure states \(\ket{\psi}\) and \(\ket{\phi}\), trace distance and fidelity determine each other exactly. Choose a global phase so that \(c=\braket{\psi}{\phi}=\sqrt{F}\ge 0\). When \(c<1\), we can write \(\ket{\phi}=c\ket{\psi}+\sqrt{1-c^2}\ket{\eta}\) for a unit vector \(\ket{\eta}\) orthogonal to \(\ket{\psi}\). In the orthonormal basis \((\ket{\psi},\ket{\eta})\), the difference of their density matrices is

This \(2\times 2\) matrix has trace \(0\) and determinant \(-(1-c^2)\), so its nonzero eigenvalues are \(\pm\sqrt{1-c^2}\). Half the sum of their magnitudes gives \(T=\sqrt{1-c^2}=\sqrt{1-F}\) (which also holds trivially at \(c=1\), where \(F=1\) and \(T=0\)).

For mixed states, a single number \(F(\rho,\sigma)\) no longer pins down \(T(\rho,\sigma)\) uniquely, but the two measures remain tightly coupled by the Fuchs–van de Graaf inequalities:

(See Watrous, Chapter 3 for the full proof via Uhlmann’s theorem.) These bounds convert fidelity benchmarks into worst-case distinguishability guarantees. Notice the square root on the upper bound: a gate or state preparation with fidelity \(F\ge 0.99\) guarantees \(T\le 0.1\), not \(T\le 0.01\).

To see why the pure-state equality fails when even one state is mixed, compare \(\rho=\ketbra{0}{0}\) with the maximally mixed qubit \(\sigma=I/2\). Here \(F(\rho,\sigma)=\bra{0}(I/2)\ket{0}=1/2\), while \(\rho-\sigma=\frac12\operatorname{diag}(1,-1)\) has eigenvalues \(\pm 1/2\) and trace distance \(T=1/2<\sqrt{1-F}=1/\sqrt2\).

Like trace distance, fidelity obeys a data-processing inequality under every quantum channel \(\mathcal N\): \(F(\mathcal N(\rho),\mathcal N(\sigma))\ge F(\rho,\sigma)\). Noise can only erase distinctions and make states appear more alike.

1.3 Asymmetric tests

1.3.1 Constraints instead of equal costs

Minimum-error discrimination treats every mistake according to its prior weight. In many experiments, however, the two hypotheses play asymmetric roles: \(\rho\) may represent a rare physical signal that we must not miss, while \(\sigma\) represents background noise. Missing a true signal and triggering a false alarm carry different operational costs.

Let the measurement effect \(M\) correspond to accepting the signal hypothesis \(\rho\). The two conditional error probabilities are

Given an externally specified tolerance \(\epsilon\in[0,1]\) on the missed-signal probability \(\alpha\le\epsilon\), we seek the test that minimizes the false-alarm probability:

No prior probabilities appear in this formulation: \(\alpha\) and \(\beta\) are conditioned on their respective hypotheses. Consequently, the Helstrom projector from Section 1.1 need not be optimal here.

1.3.2 Spending a false-alarm budget

We can see the structure of the optimal test in a two-outcome commuting example. Suppose \(\rho=\operatorname{diag}(0.8,0.2)\) and \(\sigma=\operatorname{diag}(0.3,0.7)\) share the eigenbasis \(\{\ket{a},\ket{b}\}\). Because off-diagonal entries of \(M\) do not affect \(\tr(M\rho)\) or \(\tr(M\sigma)\), we may take \(M=\operatorname{diag}(m_a,m_b)\) with \(0\le m_a,m_b\le 1\), where \(m_a\) and \(m_b\) are the probabilities of accepting the signal upon observing outcome \(a\) or \(b\).

The error probabilities are \(\alpha=1-0.8m_a-0.2m_b\) and \(\beta=0.3m_a+0.7m_b\). At tolerance \(\epsilon=0.2\), setting \(m_a=1\) and \(m_b=0\) achieves \(\alpha=0.2\) with false-alarm rate \(\beta=0.3\). Can any other pair \((m_a,m_b)\) do better?

Compare the price of signal acceptance on each outcome. Raising \(m_a\) increases signal acceptance \(\tr(M\rho)\) at a false-alarm cost of \(0.3/0.8=0.375\) per unit of signal gained. Raising \(m_b\) costs \(0.7/0.2=3.5\) false alarms per unit of signal gained. Outcome \(a\) provides signal acceptance nearly ten times more cheaply than outcome \(b\). Every optimal test must therefore saturate \(m_a=1\) before assigning any acceptance weight to \(m_b\); otherwise shifting acceptance weight from \(b\) to \(a\) would preserve \(\tr(M\rho)\) while strictly lowering \(\beta\).

Ordering outcomes by \(\sigma_i/\rho_i\) (or equivalently by the likelihood ratio \(\rho_i/\sigma_i\)) is the classical Neyman–Pearson lemma. Here it emerges directly from comparing marginal false-alarm costs.

1.3.3 From a solved example to a general method

Notice that the optimal effect \(M=\operatorname{diag}(1,0.5)\) in Worked check 1.3 is not a projector. Allowing general POVM effects \(0\le M\le I\) from the outset was essential: at the boundary of an inequality constraint, the optimal test may require randomization on a threshold outcome.

When \(\rho\) and \(\sigma\) do not commute, no shared eigenbasis reduces the problem to classical likelihood ratios. Even so, minimizing \(\tr(M\sigma)\) subject to \(0\le M\le I\) and \(\tr(M\rho)\ge 1-\epsilon\) is a semidefinite program (SDP): a linear objective minimized over the intersection of linear constraints with the cone of positive semidefinite matrices.

Convexity plays a central operational role here. If two effects \(M_1\) and \(M_2\) both satisfy the miss constraint, then any convex combination \(tM_1+(1-t)M_2\) with \(0\le t\le 1\)—physically realized by flipping a biased coin to choose which test to run—is also feasible, and its error probabilities average linearly. Exhibiting a candidate effect \(M\) with \(\tr(M\sigma)=b\) proves the upper bound \(\beta_\epsilon\le b\); semidefinite programming duality provides the matching lower bound that certifies optimality.

We have developed two single-copy paradigms for quantum hypothesis testing: symmetric minimum-error discrimination governed by \(\|\rho-\sigma\|_1\), and asymmetric constrained testing governed by semidefinite programming. When the source instead supplies \(n\) independent copies \(\rho^{\otimes n}\) or \(\sigma^{\otimes n}\), the optimal false-alarm rate \(\beta_\epsilon(n)\) decays exponentially in \(n\) at a rate set by the quantum relative entropy—the centerpiece of Chapter 3. First, Chapter 2 develops the mathematical theory of the quantum channels that transform states between preparation and measurement.