Tutorial: Purity Testing

In this problem set you will prove an exponential separation between single-copy and two-copy algorithms for purity testing. Each exercise builds on the last; proofs of supporting lemmas are provided, while the key arguments are left for you.

Definition 1 Purity Testing

Given an unknown quantum state $\rho$ promised to be either pure or $\epsilon$-far in trace distance from all pure states, determine which is the case with probability at least $2/3$.

Roadmap

Part I. Show the swap test yields an $O(1/\epsilon)$-copy algorithm, then prove a matching $\Omega(1/\epsilon)$ lower bound.
Part II. Establish that any single-copy algorithm requires $\Omega(2^{n/2})$ copies — an exponential separation.

Part I

Purity Testing with Two-Copy Measurements

Recall that the swap test on two copies of $\rho$ accepts with probability

$$p_{\mathrm{acc}} \;=\; \mathrm{tr}[\rho^{\otimes 2} \cdot \Pi_{\mathrm{sym}}^{d,2}]. \tag{1}$$

Exercise 1 Purity Testing Upper Bound

Intermediate

Prove that Purity can be tested with $O(1/\epsilon)$ copies of $\rho$.

(a) Completeness. Show that if $\rho$ is pure, the swap test accepts with certainty.

(b) Soundness. Suppose $\rho$ is $\epsilon$-far from every pure state. Show $\operatorname{tr}(\rho^2) \le 1-\epsilon$, and conclude $p_{\mathrm{acc}} \le 1-\epsilon/2$.

(c) Repetition. By running $T$ independent swap tests (accepting iff all pass), show $T = O(1/\epsilon)$ suffices for error $\le 1/3$.

Write $\rho = \sum_i \lambda_i |\psi_i\rangle\!\langle\psi_i|$ with $\lambda_1 \ge \lambda_2 \ge \cdots$. The closest pure state is $|\psi_1\rangle$, so the distance assumption gives $\lambda_1 \le 1-\epsilon$. Then use $\sum_i \lambda_i^2 \le \max_i \lambda_i \cdot \sum_j \lambda_j$.

Each test accepts with probability $\le 1-\epsilon/2$, so all $T$ accept with probability $\le (1-\epsilon/2)^T \le e^{-\epsilon T/2}$. Set $\le 1/3$.

A Matching Lower Bound

We now show $\Omega(1/\epsilon)$ copies are necessary.

Exercise 2 Purity Testing Lower Bound

Intermediate

Prove that testing purity requires $T = \Omega(1/\epsilon)$ copies.

(a) Consider $\rho_0 = |0\rangle\!\langle 0|$ and $\rho_\epsilon = (1-\epsilon)|0\rangle\!\langle 0| + \epsilon|1\rangle\!\langle 1|$. Verify $\rho_\epsilon$ is $\epsilon$-far from $\rho_0$, so any purity tester distinguishes $\rho_0^{\otimes T}$ from $\rho_\epsilon^{\otimes T}$ with probability $\ge 2/3$.

(b) Using the Holevo–Helstrom theorem and the Fuchs–van de Graaf inequality, show

$$p_{\mathrm{succ}} \;\le\; \frac{1}{2}\!\left(1 + \sqrt{1-(1-\epsilon)^T}\right).$$

You may use that fidelity is multiplicative and $\mathrm{F}(\rho_0,\rho_\epsilon)^2 = 1-\epsilon$.

(c) Combine (a) and (b) to conclude $T \ge \Omega(1/\epsilon)$.

Holevo–Helstrom: $p_{\mathrm{succ}} \le \tfrac{1}{2}(1+d_{\mathrm{tr}})$. Fuchs–van de Graaf: $d_{\mathrm{tr}} \le \sqrt{1-F^2}$. Multiplicativity: $F^2=(1-\epsilon)^T$. Impose $p_{\mathrm{succ}}\ge 2/3$ to get $(1-\epsilon)^T\le 8/9$, then take logs.

Part II

Exponential Lower Bound for Single-Copy Testers

Any single-copy algorithm for purity testing on $n$-qubit states ($d=2^n$) must use $\Omega(d^{1/2})=\Omega(2^{n/2})$ copies. The key ingredient is a lower bound on the permanent of a Gram matrix.

Permanents of PSD Matrices

Definition 2 Permanent

The permanent of an $n\times n$ matrix $A=(A_{ij})$ is $\displaystyle\mathrm{per}(A)=\sum_{\pi\in S_n}\prod_{i=1}^n A_{i\,\pi(i)}$.

Lemma 3 Permanent Lower Bound (Grone-Pierce, 1988)

Let $A$ be $n\times n$ PSD with $|a_{ii}|=1$ for all $i$. Then $\mathrm{per}(A)\ge \frac{1}{n}\|A\|_F^2$.

Exercise 3 Gram Matrix Permanent Bound

Intermediate

Let $\{|\psi_t\rangle\}_{t=1}^T$ be pure states in $\mathbb{C}^d$ with Gram matrix $G_{tt'}=\langle\psi_t|\psi_{t'}\rangle$. Using Lemma 3, prove:

$$\mathrm{per}(G)\;\ge\;\begin{cases}1,&T\le d,\\T/d,&T>d.\end{cases}$$

Lemma 3 gives $\mathrm{per}(G)\ge\frac{1}{T}\|G\|_F^2$. Since $\|G\|_F^2 = T + \sum_{i\ne j}|\langle\psi_i|\psi_j\rangle|^2 \ge T$, we get $\mathrm{per}(G)\ge 1$. An orthonormal set shows tightness.

Let $r=\mathrm{rank}(G)\le d$. Cauchy–Schwarz: $T^2=(\sum_k\lambda_k)^2\le r\sum_k\lambda_k^2 = r\|G\|_F^2\le d\|G\|_F^2$. Hence $\|G\|_F^2\ge T^2/d$, giving $\mathrm{per}(G)\ge T/d$.

From Permanents to Permutation Overlaps

Lemma 4 Permutation Overlap Bound

For any pure states $|\psi_1\rangle,\dots,|\psi_T\rangle\in\mathbb{C}^d$,

$$\sum_{\pi\in S_T}\operatorname{tr}\!\left(P_d(\pi)\,\bigotimes_{t=1}^T|\psi_t\rangle\!\langle\psi_t|\right)\;\ge\;1.$$

The action of $P_d(\pi)$ permutes tensor factors:

$$\sum_{\pi\in S_T}\operatorname{tr}\!\left(P_d(\pi)\bigotimes_t|\psi_t\rangle\!\langle\psi_t|\right) = \sum_{\pi\in S_T}\prod_t\langle\psi_t|\psi_{\pi^{-1}(t)}\rangle = \mathrm{per}(G),$$

where $G$ is the Gram matrix. Since $G$ is PSD with unit diagonal, Exercise 3 gives $\mathrm{per}(G)\ge 1$. ■

The Main Event

Proposition 5 Exponential Lower Bound (Chen-Cotler-Huang-Li, 2022)

Any algorithm using (potentially adaptive) single-copy measurements requires $T\ge\Omega(d^{1/2})$ copies to distinguish (with probability $\ge 2/3$) whether $\rho\in\mathcal{D}(\mathbb{C}^d)$ is a Haar-random pure state or $\mathbb{I}/d$.

Exercise 4 Prove the Exponential Lower Bound

Advanced

Prove Proposition 5 following this outline:

(a) Set up the likelihood ratio. Consider distinguishing $\rho=\mathbb{I}/d$ from $\rho=|v\rangle\!\langle v|$ with $|v\rangle$ Haar-random. After $T$ adaptive single-copy measurements producing outcome string $\ell$, show

$$\frac{\mathbb{E}_v[p^{|v\rangle\!\langle v|}(\ell)]}{p^{\mathbb{I}/d}(\ell)} = d^T\operatorname{tr}\!\left(\mathbb{E}_v[|v\rangle\!\langle v|^{\otimes T}]\;\bigotimes_{t=1}^T|\psi_{s_t}\rangle\!\langle\psi_{s_t}|\right).$$

(b) Apply the Haar integral. Using the identity

$$\underset{\varphi}{\mathbb{E}}\;\varphi^{\otimes T} \;=\; \frac{\Pi_{\mathrm{sym}}^{d,T}}{\operatorname{tr} \Pi_{\mathrm{sym}}^{d,T}} \;=\; \frac{\Pi_{\mathrm{sym}}^{d,T}}{d[T]} \;=\; \frac{\sum_{\pi \in S_T} P_d(\pi)}{d(d+1)\cdots(d+T-1)}$$

and Lemma 4, show

$$\frac{\mathbb{E}_v[p^{|v\rangle\!\langle v|}(\ell)]}{p^{\mathbb{I}/d}(\ell)} \;\ge\; \prod_{t=0}^{T-1}\!\left(1+\frac{t}{d}\right)^{-1}.$$

(c) Bound the product. Show the RHS is at least $1 - \frac{T(T-1)}{2d}$.

(d) Conclude. Via Le Cam's method, deduce $d_{\mathrm{TV}}\le O(T^2/d)$ and $T\ge\Omega(d^{1/2})$.

Take logs: $-\sum_{t=0}^{T-1}\log(1+t/d)\ge -\sum_{t=0}^{T-1}t/d = -T(T-1)/(2d)$. Then $e^{-x}\ge 1-x$.

Le Cam's one-sided method: if the likelihood ratio is $\ge 1-\delta$ for all $\ell$, then $d_{\mathrm{TV}}\le\delta$. A successful algorithm needs $\Omega(1)\le d_{\mathrm{TV}}$, forcing $T^2/d=\Omega(1)$.

Summary

Exercises 1–2 establish two-copy sample complexity $\Theta(1/\epsilon)$. Exercise 4 shows any single-copy algorithm requires $\Omega(2^{n/2})$ copies. Together: an exponential separation between single-copy and two-copy purity testing.

This problem set accompanies the MATH 595 lecture notes. If you find errors or have questions, please reach out.