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

Quantum Information

  1. Aug 27, 2005 #1

    In my university there is a bit of a fuss about Quantum Information (QI). A few professors work in this field and there have been some conferences where they try to explain to the rest what is QI and so on. I think it is safe to say I know a bit of quantum mechanics, not at a professional level though, but I cant understand why having bits in a superposition of states makes computing more efficient and fast. Theoreticaly, you can drastically cut down in search times, and it is said that they could actually make encrypted messages unsafe. I think most encryption is based on very large prime numbers which would be factorized with this quantum computer (!?). I know all this is old news but can anyone explain the crucial point that accounts for this boost in computing power?
  2. jcsd
  3. Aug 28, 2005 #2
  4. Aug 28, 2005 #3


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    A typical function on a Quantum Computer operates on the basis states like this:

    |x>|y> → |x>|y + f(x)>

    So, if you have a big superposition of states, then one application of your function gets applied to every basis state in the superposition!

    Of course, there is a catch: you can only get one answer out of the computer, and you can't directly control which one.

    However, if you can write some other function g that can identify the desired result out of the n possible results, then Grover's algorithm lets you get the desired result with high probability. (It involves applying g and some other stuff √n times, where n is the total number of possible results)

    Grover's algorithm is often described as an algorithm that can search an n-long list in √n time.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook