Ultimate physical limits to computation

1999/08/13 by Seth Lloyd · 11 voices · 38 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Computability, Logic, AI Algorithms

paper · pdf · doi:10.1038/35023282

Abstract

Computers are physical systems: what they can and cannot do is dictated by the laws of physics. In particular, the speed with which a physical device can process information is limited by its energy and the amount of information that it can process is limited by the number of degrees of freedom it possesses. This paper explores the physical limits of computation as determined by the speed of light c, the quantum scale ℏ and the gravitational constant G. As an example, quantitative bounds are put to the computational power of an `ultimate laptop' with a mass of one kilogram confined to a volume of one liter.

Cited by

• Fundamental decoherence from quantum gravity: a pedagogical review
• Are We Living in a Computer Simulation?
• Complexity Equals Action
• Page transition for the complexity of an evaporating black hole
• The Cognitive Kardashev Scale: Quantifying the Material Envelope of Civilisational Computation
• Autonomous quantum processing unit: an autonomous thermal computing machine & its physical limitations
• Hitchhiker's Guide to the Swampland: The Cosmologist's Handbook to the String‐Theoretical Swampland Programme
• The unreasonable likelihood of being: origin of life, terraforming, and AI
• Astrophysical constraints on the simulation hypothesis for this Universe: why it is (nearly) impossible that we live in a simulation
• Complexity measures in QFT and constrained geometric actions
• Freezing Swampland: A Krylov Complexity Criterion for the Weak Gravity Conjecture
• Difference Principle and Black-hole Thermodynamics
• Computational Cosmic Censorship
• The Universe Learning Itself: On the Evolution of Dynamics from the Big Bang to Machine Intelligence
• Quantum Computation
• Impossibility Results in AI: A Survey
• Type III Societies (Apparently) Do Not Exist
• Propagation-Distance Limit for a Classical Nonlocal Optical System
• Systems that saturate the Margolus-Levitin quantum speed limit
• Variations on a Theme of Krylov
• Timelike Holographic Complexity
• On Complexity of Holographic Flavors
• Quantum-Enhanced Measurements: Beating the Standard Quantum Limit
• Thermodynamic Computing
• A Computational Model for Quantum Measurement
• Blink and you'll miss it -- How Technological Acceleration Shrinks SETI's Narrow Detection Window
• Black Hole Entropy and Complexity Growth in Horndeski Gravity within the AdS/BCFT Framework
• Quantum speed limits based on Jensen-Shannon and Jeffreys divergences for general physical processes
• Spontaneous Ultraweak Photon Emission from Biological Systems and the Endogenous Light Field
• The ultimate physical limits to reversibility
• Quantum speed limit for the OTOC from an open systems perspective
• Probing the Black Hole Interior with Holographic Entanglement Entropy and the Role of AdS/BCFT Correspondence
• Applications of Algorithmic Probability to the Philosophy of Mind
• Dynamics-independent bounds on state transformations and precision in open quantum systems
• Saturable Quantum Speed Limits for Imaginary-Time Evolution
• The Cost of Nonlocality: A Dynamical Performance Equation of Energy-Entanglement-Complexity
• Speed limits on classical chaos
• The Goldbach Conjecture as an Informational Economy Principle: A Heuristic Framework from Computational Physics

Discussions

• Physical Limits to Computation (2000) [pdf] [hn, 40 points, 21 comments]
• Ultimate physical limits to computation [hn, 7 points, 0 comments]
• Ultimate physical limits to computation [hn, 5 points, 0 comments]
• Ultimate physical limits to computation (2000) [pdf] [hn, 5 points, 0 comments]
• Physical Limits to Computation [hn, 2 points, 0 comments]
• What's the power of an "ultimate laptop" (of 1kg mass in 1L volume) [hn, 2 points, 1 comments]
• Ultimate physical limits to computation, Seth Lloyd (2000) [hn, 2 points, 0 comments]
• Nature: The Ultimate Physical Limits of Computation [hn, 2 points, 0 comments]
• Physical Limits to Computation (2000) [hn, 2 points, 0 comments]
• Ultimate Physical Limits to Computation (2000) [hn, 2 points, 0 comments]
• Ultimate physical limits to computation [hn, 1 points, 0 comments]

Related

• Physical complexity and black hole quantum computers
• Universal Limits on Computation
• On the computational capabilities of physical systems part I: the impossibility of infallible computation
• Limits on Efficient Computation in the Physical World
• Uncomputability and physical law