10
$\begingroup$

Deutsch's algorithm is a well known quantum computing $f(0) + f(1)\mod{2}$ with only one one evaluation of $f$. If we replace $+$ with $\cdot$ the problem seems to become rather different. My question is: does there exist a quantum algorithm computing the value of $f(0)\cdot f(1)$ (or AND if you prefer) using only one evaluation of $f$. Otherwise: is it known that such an algorithm does not exist?

Update: I have now become aware of procedure that gives correct answer with a probability greater than what any classical procedure is able. The "error" is one-sided in the sense that it always produces the correct answer when $f(0)\wedge f(1)=1$. This leads me to an extended question: does there exist a quentum algorithm (possibly similar to the one mentioned below) with the property that the result is $1$ only if $f(0)\wedge f(1)=1$? Of course the "best case scenario" would be an algorithm that gives correct answer with probability $1$.

$\endgroup$
11
$\begingroup$

This is Assignment 3, Question 5 in Richard Cleve's ongoing intro to quantum computing course. (Seems like this assignment was due today.)

While we're not supposed to answer homework questions on CSTheory, fortunately the assignment answers all your questions. It also takes you through the construction of the quantum algorithm. I strongly recommend reading it.

$\endgroup$
  • $\begingroup$ Thanks a lot for the answer and the reference. Strange but fortunate coincidence with that assignment. $\endgroup$ – Magnus Find Oct 28 '11 at 6:50
3
$\begingroup$

First, prepare a state $\frac{1}{\sqrt{3}}((-1)^{f(0)}|00\rangle + (-1)^{f(1)}|01\rangle + |11\rangle)$ (which can be done easily using single black-box query and unitaries). Notice that two such states correspondng to different $f$'s have always inner product $\frac{1}{3}$. You can easily turn this observation into an algorithm succeeding with one-sided error $\frac{8}{9}$ or better if you allow two-sided error (note that the best classical procedure can achieve probability at most $\frac{2}{3}$).

$\endgroup$
  • $\begingroup$ I am not sure I totally follow. Anyway, after Robin's answer I did. Thanks for the answer $\endgroup$ – Magnus Find Oct 28 '11 at 6:46

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.