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

CC BY-SA 3.0
2011-10-28T06:46:03.503Z
I am not sure I totally follow. Anyway, after Robin's answer I did. Thanks for the answer
Magnus Find
CC BY-SA 3.0
2011-10-27T15:07:54.517Z
2011-10-27T15:07:54.517Z
Marcin Kotowski
<p>This is <a href="http://www.cs.uwaterloo.ca/~cleve/courses/F11CS667/assignment3.pdf" rel="nofollow">Assignment 3, Question 5</a> in Richard Cleve's ongoing <a href="http://www.cs.uwaterloo.ca/~cleve/courses/F11CS667/" rel="nofollow">intro to quantum computing course</a>. (Seems like this assignment was due today.)</p>

<p>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.</p>

CC BY-SA 3.0
2011-10-28T06:50:14.480Z
Thanks a lot for the answer and the reference. Strange but fortunate coincidence with that assignment.
Magnus Find
CC BY-SA 3.0
2011-10-27T19:22:04.090Z
2011-10-27T19:22:04.090Z
Robin Kothari
<p>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?</p>

<p><strong>Update:</strong> 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$.</p>

<reference-request><quantum-computing>
Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?
Magnus Find
# Does there exist a quantum algorithm ala Deutsch's algorithm that computs AND instead of XOR?

(Asked by: username_0 on 2011-10-27)

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

**Tags:** reference-request, quantum-computing


---

## 2 answers

### Answer by username_2 on 2011-10-27. Score: 11 | Accepted answer

This is [Assignment 3, Question 5](http://www.cs.uwaterloo.ca/~cleve/courses/F11CS667/assignment3.pdf) in Richard Cleve's ongoing [intro to quantum computing course](http://www.cs.uwaterloo.ca/~cleve/courses/F11CS667/). (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.

> **Comments:**
> **username_0**: Thanks a lot for the answer and the reference. Strange but fortunate coincidence with that assignment.  

---

### Answer by username_1 on 2011-10-27. Score: 3

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

> **Comments:**
> **username_0**: I am not sure I totally follow. Anyway, after Robin's answer I did. Thanks for the answer  

---

