The Deutsch problem in quantum computation

[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?

 

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

 

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

(i.e., f(a0+b1, c0+d1) = acf(0,0)+adf(0,1)+...)

 

[Tez]

The function can take input over x = 0,1,2,..2^n-1 for any integer n.

The key is that you are promised that the function is either constant, or it is balanced. "Constant" means that either f(x)=1 or f(x)=0 for every input x, "balanced" means that f(x)=1 for exactly half of the possible inputs and f(x)=0 for the other half of the inputs.