Quantum Computing: Moving Beyond Goedel?

from Google AI:

The intersection of Kurt Gödel’s Incompleteness Theorems, Richard Feynman’s vision for quantum computing, and the limitations of physical simulation touches on fundamental questions about the limits of mathematics, logic, and reality.

1. Gödel’s Incompleteness Theorems (1931):

• Gödel proved that any consistent formal system capable of describing basic arithmetic cannot be both complete and consistent.
• Incompleteness: There are true statements within the system that cannot be proven using the system's own rules.
• Self-Consistency: The system cannot prove its own consistency.
• Implication: Mathematics is an open, non-zippable system, not a finite set of axiomatic truths.

2. Feynman’s Quantum Computer (1981–1982): 

• Richard Feynman proposed quantum computers because he realized that simulating quantum mechanical systems on a classical computer is computationally overwhelming (scaling exponentially). 
• Nature is Quantum: Feynman argued that since nature is quantum mechanical, a simulator must be quantum mechanical to be efficient. 
• Beyond Classical Limits: A quantum computer uses superposition (qubits in multiple states simultaneously) to bypass the exponential slowdown of classical, deterministic computers

3. Connecting Incompleteness, Quantum, and Feynman Uncomputability in Physics:

• While Gödel addressed mathematics, recent research suggests that Gödelian incompleteness applies to physics. For instance, determining the "spectral gap" in certain quantum systems is proven to be undecidable (uncomputable), meaning no computer—classical or quantum—can solve it.
• Limitations of Simulation: Although quantum computers are more powerful than classical ones, they are still "computers" (based on physical laws). Some suggest that if a system is fundamentally uncomputable, a quantum computer cannot solve it, implying that Feynman’s dream of simulating all of nature might encounter fundamental, logical limitations.
• Decidability vs. Computability: Gödel’s results show that some truths are not provable. Quantum mechanics introduces intrinsic, probabilistic "uncertainty" (not just epistemic, but fundamental) that differs from the deterministic "uncomputability" that Shannon-Turing computers face, though quantum systems themselves can hold "hidden information".

Feynman’s quantum computer solves the exponential complexity problem of classical simulation, but it does not bypass the logical limitations established by Gödel. Both fields point to a reality that is richer than any single, finite, axiomatic, or algorithmic system can completely describe