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

    Tez

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: The Deutsch problem in quantum computation
  1. Quantum computing (Replies: 3)

Loading...