Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I'm not sure whether research-level is appropriate for this; someone who knows better, please remove it if that is appropriate. – David Z May 31 '12 at 20:31
This is definitely not research level. – Steve Flammia Jun 4 '12 at 20:59
up vote 7 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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