# Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

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$.

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}$).