# The Deutsch problem in quantum computation

1. Mar 1, 2006

### ptabor

I'm doing a research paper on the deutsch problem in QC. My google inquiries have turned up numerous papers on solutions to the problem, but I am having difficulty finding a clear formulation of the problem itself.

Can someone point me in the direction of this information?

2. Mar 1, 2006

### rachmaninoff

http://www.cs.xu.edu/~kinne/quantum/deutche.html

In short,
You have a function f: {0,1} --> {0,1} (there are four possible functions like this). You want to know the answer to the question - is f(0)=f(1)?. A classical circuit (and hence, any classical algorithm) must evaluate f twice: you must evaluate f(0), and also f(1); and then you compare them. With Deutsch's algorithm, if you have a quantum computer you can exploit superposition to answer the question with only one evaluation of f.

3. Mar 1, 2006

### rachmaninoff

To clarify what is on that page:

The Hadamard operator H operates on a single qubit, and its matrix representation is

$$\frac{1}{\sqrt{2}}\left( \begin{array}1 & 1 \\ 1 & -1 \end{array} \right)$$

The unitary operator corresponding to f (operates on two qubits) is:

f(x,y)=(x,y+f(x)) for eigenstates x,y, and extended to arbitrary x,y by linearity.