Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The Deutsch problem in quantum computation

  1. Mar 1, 2006 #1
    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. jcsd
  3. Mar 1, 2006 #2

    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.
  4. Mar 1, 2006 #3
    To clarify what is on that page:

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

    [tex]\frac{1}{\sqrt{2}}\left( \begin{array}1 & 1 \\ 1 & -1
    \end{array} \right)[/tex]

    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)+...)
  5. Mar 2, 2006 #4


    User Avatar

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook