# Does the upper bound of computability hold for quantum computers?

• EnumaElish
In summary, the paper discusses how physical systems register and process information, with the laws of physics determining the amount of information and number of logic operations that can be performed. The universe, being a physical system, has a maximum capacity of 10^{120} ops and 10^{90} bits. This limit also applies to quantum computers, with the author considering atomic spin as the most elementary bit and spin flip as the most elementary operation. While quantum superposition can cause confusion, the author counts the number of elementary operations regardless of whether they are performed in parallel or within the same physical system.
EnumaElish
Homework Helper
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.

The upper bound of computability stated in the paper does not apply to quantum computers in the same way as it applies to classical computers. Quantum computers operate on the principles of quantum mechanics, which allow for the manipulation of information in ways that are not possible with classical computers. Therefore, the laws of physics that determine the amount of information and operations for classical computers may not necessarily apply to quantum computers.

In fact, there is evidence that quantum computers have the potential to surpass the limitations of classical computers in terms of computational power and efficiency. This is due to the ability of quantum computers to process and manipulate information in a parallel and superpositioned manner.

However, it is important to note that the upper bound of computability for quantum computers is still a topic of ongoing research and debate. While there is evidence that quantum computers have the potential to exceed the limitations of classical computers, it is not yet fully understood how this will be achieved and what the ultimate upper bound may be.

In conclusion, while the upper bound of computability stated in the paper may hold for classical computers, it does not necessarily apply to quantum computers. The unique properties of quantum mechanics may allow for the potential of quantum computers to surpass this upper bound, but further research and development is needed to fully understand the potential of quantum computing.

## 1. What is the upper bound of computability for quantum computers?

The upper bound of computability for quantum computers is not yet fully known. It is believed to be greater than that of classical computers, but the exact limit is still being researched and debated.

## 2. Can quantum computers solve problems that are currently unsolvable by classical computers?

Yes, quantum computers have the potential to solve certain problems that are currently unsolvable by classical computers. This is due to their ability to perform calculations using quantum bits (qubits) which can exist in multiple states simultaneously, allowing for more efficient processing of certain tasks.

## 3. How does the upper bound of computability affect the potential of quantum computing?

The upper bound of computability plays a crucial role in determining the potential of quantum computing. It sets the limitations for what types of problems can be solved and at what scale, and also determines the complexity of these solutions.

## 4. Are there any known examples of problems that quantum computers can solve faster than classical computers?

Yes, there are several examples of problems that have been proven to be solvable faster by quantum computers. One well-known example is Shor's algorithm, which can efficiently factor large numbers, a task that is believed to be intractable for classical computers.

## 5. Is there ongoing research to further understand the upper bound of computability for quantum computers?

Yes, there is ongoing research in this area as scientists continue to explore the potential of quantum computing. New developments in both theory and technology are constantly being made to better understand the upper bound of computability and push its limits.

• Computing and Technology
Replies
13
Views
2K
• Quantum Physics
Replies
39
Views
3K
Replies
9
Views
1K
Replies
2
Views
971
• Quantum Physics
Replies
8
Views
1K
• Computing and Technology
Replies
4
Views
5K
• Beyond the Standard Models
Replies
1
Views
934
Replies
36
Views
1K
• Quantum Physics
Replies
2
Views
1K