I'm trying to prove the claim that

Given two pure states: $|\psi_i\rangle$ and $|\phi_i\rangle$ such that $|\,|\psi_i\rangle - |\phi_i\rangle\,|\le \delta$ then no measurement can distinguish between them with probability greater than $4\delta$.

Unfortunately, still haven't made any progress. Any help will be appreciated.

  • 5
    $\begingroup$ Hi and welcome to Quantum Computing SE. Could you please add more details, e.g. what you have done so far? $\endgroup$ Jan 4 at 21:44
  • 5
    $\begingroup$ Try making it more specific. Suppose one of the states is $|0\rangle$ and the other is $\cos(\theta) |0\rangle + \sin(\theta) |1\rangle$ for small $\theta$. $\endgroup$ Jan 4 at 23:23
  • 3
    $\begingroup$ erm... if two states have a very small overlap (bounded by $\delta$, small) then they are not very similar states. $\endgroup$
    – DaftWullie
    Jan 5 at 8:29
  • 1
    $\begingroup$ You probably want to look at the Helstrom measurement. See, for example, this answer: quantumcomputing.stackexchange.com/a/4172/1837 and follow @CraigGidney 's suggestion. $\endgroup$
    – DaftWullie
    Jan 5 at 8:30

1 Answer 1


The claim does not specify what protocols for distinguishing quantum states are acceptable. In particular, it does not state whether we are allowed to err or reserve judgment. Below, we note success probability for protocols allowed to err and compute success probability for an error-free protocol. The success probability of the former is not bounded by $4\delta$. The success probability of the latter obeys a stricter bound. Hopefully, this helps.

Protocols with errors

If we imagine that the desired protocol receives as input a quantum state which is promised to be either $|\psi\rangle$ or $|\phi\rangle$ and must output "$\psi$" or "$\phi$" and the protocol is allowed to err then we see that the success probability of random guessing is $P_{\text{success}}=\frac12$. Consequently, good protocols allowed to err that actually take advantage of the knowledge of $|\phi\rangle$ and $|\psi\rangle$ would have $P_{\text{success}}\ge\frac12$.

Error-free protocol

POVM for error-free protocol

Let us therefore consider protocols that are not allowed to err, but may output "do not know". Denote by $E_\psi$, $E_\phi$ and $F$ the POVM elements corresponding to the outputs "$\psi$", "$\phi$" and "do not know", respectively. The three operators are positive semidefinite and $E_\psi+E_\phi+F=I$. Suppose for simplicity that we are dealing with qubits. Since we are not allowed to err $E_\psi$ is a scalar multiple of the projector on a subspace orthogonal to $|\phi\rangle$ and similarly for $E_\phi$. Assuming, for further simplification, equal success probabilities for the two inputs, we have

$$ E_\psi=p|\phi^\perp\rangle\langle\phi^\perp|\quad E_\phi=p|\psi^\perp\rangle\langle\psi^\perp|\tag1 $$

for some $p\in[0,1]$ and some choice of $|\phi^\perp\rangle$ and $|\psi^\perp\rangle$ with $\langle\phi|\phi^\perp\rangle=0$ and $\langle\psi|\psi^\perp\rangle=0$. We may choose $|\psi^\perp\rangle$ such that

$$ |\phi\rangle\equiv\alpha|\psi\rangle+\beta|\psi^\perp\rangle\tag2 $$

where $\equiv$ denotes equality up to global phase and where $\alpha$ and $\beta$ are non-negative real numbers$^1$. Also, we can define

$$ |\phi^\perp\rangle:=\beta|\psi\rangle-\alpha|\psi^\perp\rangle.\tag3 $$

Then in the $|\psi\rangle$,$|\psi^\perp\rangle$ basis the POVM elements take the form

$$ E_\phi=p|\psi^\perp\rangle\langle\psi^\perp|=p\begin{bmatrix}0&0\\0&1\end{bmatrix}\\ E_\psi=p|\phi^\perp\rangle\langle\phi^\perp|=p\begin{bmatrix}\beta^2&-\alpha\beta\\-\alpha\beta&\alpha^2\end{bmatrix}\\ F=I-E_\phi-E_\psi=\begin{bmatrix} 1-p\beta^2&p\alpha\beta\\ p\alpha\beta&1-p-p\alpha^2 \end{bmatrix}.\tag4 $$

By Sylvester's criterion, $F$ is positive semidefinite if and only if

$$ 1-p\beta^2\ge 0\\ 1-p-p\alpha^2\ge 0 \\ \det F\ge 0.\tag5 $$

The first inequality is always satisfied and the second means that $p\le\frac{1}{1+\alpha^2}$. For the third, we compute

$$ \begin{align} \det F&=(1-p\beta^2)(1-p-p\alpha^2)-p^2\alpha^2\beta^2\\ &=\beta^2p^2-2p+1 \end{align}\tag6 $$

and find that

$$ p\in\left(-\infty,\frac{1-\alpha}{\beta^2}\right]\cup\left[\frac{1+\alpha}{\beta^2}, +\infty\right).\tag7 $$

Putting it all together we see that $E_\psi$, $E_\phi$, $F$ is a valid POVM if and only if $p\in[0,\frac{1-\alpha}{\beta^2}]$.

Success probability in error-free protocol

Now, the probability of success on input $|\phi\rangle$ and $|\psi\rangle$ is

$$ P_{\text{success},\phi}=\langle\phi|E_\phi+E_\psi|\phi\rangle=p|\langle\phi|\psi^\perp\rangle|^2=p\beta^2\\ P_{\text{success},\psi}=\langle\psi|E_\phi+E_\psi|\psi\rangle=p|\langle\psi|\phi^\perp\rangle|^2=p\beta^2\tag8 $$

which is maximized when $p=\frac{1-\alpha}{\beta^2}$. In this case, $P_{\text{success}}=1-\alpha$. Finally,

$$ \||\psi\rangle-|\phi\rangle\|^2=\langle\psi|\psi\rangle-\langle\psi|\phi\rangle-\langle\phi|\psi\rangle+\langle\phi|\phi\rangle=2-2\alpha\tag9 $$

so $\||\psi\rangle-|\phi\rangle\|\le\delta$ implies $2-2\alpha\le \delta^2$. Therefore, $P_{\text{success}}\le\frac{\delta^2}{2}\le 4\delta$.

$^1$ This is another way of saying what Craig Gidney suggested in the comments.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.