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

Grover's algorithm

  1. Oct 24, 2011 #1
    Could anyone explain me how Grover's algorithm works.
    I read the article on wiki about it:
    http://en.wikipedia.org/wiki/Grover_algorithm" [Broken]
    but I don't see any relation between classical problem of searching an
    element in unsorted database and its alledge quicker quantum solution.

    In classical problem we have a set of unsorted objects from and we want
    to find one particular object. What is the quantum counterpart of this?
     
    Last edited by a moderator: May 5, 2017
  2. jcsd
  3. Oct 24, 2011 #2

    xts

    User Avatar

    I think it is a kind of misunderstanding to call it a 'database search' (Grover is responsible for that misleading title)
    What the algorithm really does is to find that unique value for which the (quantum-computational) function returns 1, while for all other possible states it returns 0. You may call this function a 'comparison with a key for database', but that seems to be very simplified analogy.

    You may want to read original Grover's paper: http://arxiv.org/abs/quant-ph/9605043

    However I haven't heard about any Grover's realisation other than trivial (algorithm returns the input value, the function to be used is a Kronecker's delta)
     
  4. Oct 24, 2011 #3
    I agree with you. I think that one can compare this algorithm to algorithm of
    finding an argument for which a given function has particular value.

    I only don't understand why so many people claim that quantum computing
    surpasses classical one, because the Grover's algorithm
    searches unsorted database in [tex]O(\sqrt{n})[/tex]
    whereas the best classical algorithm is linear. For me these two algorithms
    solve slightly different problems.
     
  5. Oct 24, 2011 #4

    xts

    User Avatar

    Yes, it is what actually Grover's algorithm does.
    Just with some restrictions: there must be exactly one argument such, that function returns that value. And - what much worse - the function must be possible to be implemented as a quantum algorithm.
     
  6. Oct 31, 2011 #5
    I'm curious about which functions that can be implemented classically are theoretically hard to implement with a quantum algorithm?
     
  7. Oct 31, 2011 #6
    Classical computation is a subset of quantum computation. So anything you can do classically can be done with a quantum computer. I think you know that, and are meaning to ask, with which problems is it difficult to take advantage of the quantum nature of the machine?

    The advantage of quantum computers is massive parallelism. You will find that with most problems parallelism does surprisingly little or no good. According to the theorists quantum computers won't help solve problems in NP.
     
  8. Oct 31, 2011 #7
    Hmm, how about data base search? If the data base is in ordinary computer storage it seems to me that a quantum algorithm would not help you at all. The data would have to be stored as quantum superpositions.

    But I could be wrong about this.
     
  9. Oct 31, 2011 #8

    thanks
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook