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

Does the upper bound of computability hold for quantum computers?

  1. Oct 30, 2006 #1


    User Avatar
    Science Advisor
    Homework Helper

    This paper states that:
    This means that the upper bound of computability is "10^{120} ops on 10^{90} bits." Question: does this upper bound apply to quantum computers as well?
  2. jcsd
  3. Oct 31, 2006 #2


    User Avatar
    Science Advisor

    It does, assuming these are reasonable bounds. The author is using atomic spin as the most elementary bit and a spin flip as the most elementary operation (a bit flip), both of which are used in quantum computers.
    It can cause some confusion the fact that a quantum computer makes use of quantum superposition, since then a single operation in n qubits yields twice the information processing as a single operation in n-1 qubits.
    Nevertheless, a single operation in n bits consists of n elementary operations (bit flips), and this is what the author is counting. We're counting the number of elementary operations, independently of whether they're performed in parallel or are part of the same physical system.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook