Does the upper bound of computability hold for quantum computers?

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
1 reply · 2K views
Messages
2,348
Reaction score
124
This paper states that:
Merely by existing, all physical systems register information. And by evolving dynamically in time, they transform and process that information. The laws of physics determine the amount of information that a physical system can register (number of bits) and the number of elementary logic operations that a system can perform (number of ops). The universe is a physical system. This paper quantifies the amount of information that the universe can register and the number of elementary operations that it can have performed over its history. The universe can have performed no more than 10^{120} ops on 10^{90} bits.
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?
 
Physics news on Phys.org
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.