Consider the following setting.

I am either given the density matrix $|\psi\rangle \langle \psi|^{\otimes k}$ or the density matrix $\frac{\mathbb{I}^{\otimes k}}{2^{nk}}$, where $\mathbb{I}$ is the $2^{n} \times 2^{n}$ identity matrix.

It is known that $$ |\psi\rangle = C|0^{n}\rangle, $$ for some $C$ which is chosen at random from an ensemble that forms a $k$-design. $$ \mathbb{E}[|\psi\rangle\langle\psi|^{\otimes k}] = \frac{1}{|C|}\sum_{C}C ^{\otimes k}|0\rangle\langle 0|C^{\dagger \otimes k} = \int_{C \sim \text{Haar}} C^{\otimes k}|0\rangle\langle0|C^{\dagger \otimes k} dC_1. $$

We could ask: for any choice of $|\psi\rangle \langle \psi|^{\otimes k}$, what is the optimal test that distinguishes between these two density matrices?

Note that there is a simple strategy that distinguishes between these two states with high probability. Trace out $k-2$ copies, and just perform the SWAP test on the first two copies. No matter what $|\psi\rangle$ we are given, since $|\psi\rangle$ is a pure state, our procedure would accept with probability $1$ when we are given (multiple copies of) $|\psi\rangle$, and accept with a low probability when we are given (multiple copies of) the maximally mixed state.

However, according to this paper (Lemma 20), the optimal test, by utilizing the unitary invariance property of $k$ designs, can also be written in a very specific form.

  1. Perform weak Schur sampling on the state you are given.
  2. Obtain outcome $\lambda$ (where $\lambda$ is a partition of $k$ --- for example, $(4, 1)$ is a partition of $5$.)
  3. Accept with probability $\alpha_{\lambda}$ where $$ \alpha_{\lambda} = d_{\lambda} ~s(x_1, x_2, \ldots, x_{2^{n}}), $$

where $s$ is called the Schur polynomial; $x_1, x_2, \ldots, x_{2^{n}}$ are the eigenvalues corresponding to the density matrix of a single copy of the state; and $d_{\lambda}$ is the dimension of the square matrix associated with the partition $\lambda$. Everything is elucidated in the paper.

However, the eigenvalues corresponding to a single copy of a maximally mixed state over $n$ qubits is $\left(\frac{1}{2^{n}}, \frac{1}{2^{n}}, \ldots, \frac{1}{2^{n}} \right)$. Since a $k$-design is also a $1$ design, the eigenvalues for a single copy of the other density matrix is also $\left(\frac{1}{2^{n}}, \frac{1}{2^{n}}, \ldots, \frac{1}{2^{n}} \right)$. So, the probability of distinguishing these two density matrices using the supposedly optimal Schur sampling method is exactly $0$ --- which is clearly worse than the SWAP test.

How can the Schur sampling method still be optimal?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.