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

A Question About Grover's Algorithm (Quantum Computing)

  1. Jul 10, 2009 #1
    Hey guys,

    After taking linear algebra I decided I could try my hand at learning some introductory QC algorithms, and downloading this introductory paper from arxiv: http://arxiv.org/abs/quant-ph/0301079v1
    After mulling through it for a couple of days, I got a little disturbed by their sketchy index finding function at the bottom of page 14, stated as follows:

    Erm...'let us assume'?
    Since the function f(i) can be implemented in a classical computer, I understand that we can decompose this function into AND and NOT gates and turn them into the Toffoli and CNOT quantum equivalents, and thereby apply the function f(i) via quantum gates. But wouldn't the entire database infrastructure have to be..err...in qubits for this to work?

    Also, what's stopping me from defining almost any function whatsoever, marking it in the same way, and use Grover's algorithm to find the marked element(s)?
    For example, could I replace that function f(i) with my own, say:

    f(N,i) = 1 if N%i == 0
    f(N, i) = 0 otherwise

    [where N = 2^(2*# of qubits) ]

    and use it to increase the likelihood of finding prime factors, thereby using Grover's algorithm as an inefficient replacement for Shor's?

    I feel like there's something I'm not getting...

    Thanks for the help,

    (Note: sorry for this isn't the right thread for this topic; move if necessary)
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted