Does the upper bound of computability hold for quantum computers?

AI Thread Summary
The paper discusses how all physical systems inherently register and process information, with the laws of physics dictating the limits of this capability. It quantifies the universe's capacity to register information as 10^90 bits and perform a maximum of 10^120 elementary operations. This establishes an upper bound of computability for physical systems, including quantum computers. The discussion clarifies that this upper bound applies to quantum computers, as they utilize atomic spins for bits and spin flips for operations. While quantum superposition allows for increased information processing, the count of elementary operations remains consistent, focusing on the number of bit flips rather than the parallel processing capabilities of qubits.
EnumaElish
Science Advisor
Messages
2,346
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.
 
In my discussions elsewhere, I've noticed a lot of disagreement regarding AI. A question that comes up is, "Is AI hype?" Unfortunately, when this question is asked, the one asking, as far as I can tell, may mean one of three things which can lead to lots of confusion. I'll list them out now for clarity. 1. Can AI do everything a human can do and how close are we to that? 2. Are corporations and governments using the promise of AI to gain more power for themselves? 3. Are AI and transhumans...
Sorry if 'Profile Badge' is not the correct term. I have an MS 365 subscription and I've noticed on my Word documents the small circle with my initials in it is sometimes different in colour document to document (it's the circle at the top right of the doc, that, when you hover over it it tells you you're signed in; if you click on it you get a bit more info). Last night I had four docs with a red circle, one with blue. When I closed the blue and opened it again it was red. Today I have 3...
Back
Top