Consider this problem in quantum cryptography:

We have two pure states $\phi_1,\phi_2$ as input and constants $0 \leq \alpha <\beta \leq 1 $, where "Yes instances" are those for which $$\left|\left<\phi_1,\phi_2\right>\right| \leq \alpha$$ and "No instances" are those for which $$\left|\left<\phi_1,\phi_2\right>\right|\geq \beta$$

I need to devise a quantum circuit that accepts "Yes instances" with probability at least $p$, and "No instances" with at most probability $q$ for some $q<p$.

How can I do this? Is there a reference in which this problem is solved?

Thanks in advance.

  • 1
    $\begingroup$ I'm not sure whether research-level is appropriate for this; someone who knows better, please remove it if that is appropriate. $\endgroup$
    – David Z
    May 31, 2012 at 20:31
  • 2
    $\begingroup$ This is definitely not research level. $\endgroup$ Jun 4, 2012 at 20:59

1 Answer 1


There is a circuit which returns a "1" measurement outcome with probability $\frac{1}{2} \left(1-\left|\left<\phi_1|\phi_2\right>\right|^2\right)$, so this does what you ask with $p=\frac{1-\alpha}{2}$ and $q=\frac{1-\beta}{2}$ (but double check those $p,q$ values because I am short on sleep at the moment). The circuit is shown on the top of page 682 of Buhrman, Cleve, Massar, de Wolf (2010), Rev. Mod. Phys. 82, 665–698. The idea is that a $\left|+\right>$ state controls a controlled-swap of the two input states. The control state is then measured in the $X$ basis. If the states are identical then nothing happens to the control qubit, otherwise it decoheres in the $Z$ basis.

There are also some no-go theorems limiting the possible values of $p$ and $q$ in Pang, Wu, Chen (2011) Phys. Rev. A 84, 062313, although I haven't actually read this paper.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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