Does the upper bound of computability hold for quantum computers?

Click For Summary
SUMMARY

The upper bound of computability for quantum computers is established as 10120 operations on 1090 bits, as outlined in the discussed paper. This quantification is based on the universe's capacity to register information and perform elementary logic operations, with atomic spin serving as the fundamental bit and spin flips as the basic operations. Despite the complexities introduced by quantum superposition, the author clarifies that the count of operations remains consistent, focusing on elementary operations rather than parallel processing capabilities.

PREREQUISITES
  • Understanding of quantum computing principles, specifically atomic spin and qubits.
  • Familiarity with the concepts of information theory, including bits and operations.
  • Knowledge of the laws of physics as they relate to information processing.
  • Basic comprehension of quantum superposition and its implications for computation.
NEXT STEPS
  • Research the implications of atomic spin in quantum computing.
  • Explore the concept of quantum superposition and its effect on information processing.
  • Study the relationship between classical and quantum operations in computational theory.
  • Investigate the limits of computability in various physical systems beyond quantum computers.
USEFUL FOR

Researchers in quantum computing, physicists exploring the limits of information processing, and computer scientists interested in the theoretical foundations of computation.

EnumaElish
Science Advisor
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?
 
Computer science 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.
 

Similar threads

  • · Replies 13 ·
Replies
13
Views
4K
  • · Replies 11 ·
Replies
11
Views
4K
  • · Replies 39 ·
2
Replies
39
Views
5K
Replies
3
Views
6K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 8 ·
Replies
8
Views
3K
  • · Replies 2 ·
Replies
2
Views
4K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 40 ·
2
Replies
40
Views
5K