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

Question

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

Answer 1

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.

Answer 2

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