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

    EnumaElish

    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

    -Job-

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

Have something to add?



Similar Discussions: Does the upper bound of computability hold for quantum computers?
  1. Quantum Computing (Replies: 9)

  2. Quantum computers (Replies: 1)

Loading...