Ultimate physical limits to computation

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 $\hslash$ 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.

22 pages, plain TeX, submitted to Nature, replaced to incorporate additional content and references

References in corpus (1)

• Coherent control of macroscopic quantum states in a single-Cooper-pair box

Cited by in corpus (410)

• Quantum-enhanced measurements: beating the standard quantum limit
• Complexity Equals Action
• Complexity, action, and black holes
• Quantum speed limits: from Heisenberg's uncertainty principle to optimal quantum control
• Computational capacity of the universe
• Quantum speed limit for non-Markovian dynamics
• Quantum speed limits in open system dynamics
• Limits on Fundamental Limits to Computation
• Chopped random-basis quantum optimization
• The fundamental limit on the rate of quantum dynamics: the unified bound is tight
• On the Time Dependence of Holographic Complexity
• Noether charge, black hole volume, and complexity
• Complexity of Formation in Holography
• Trade-off between speed and cost in shortcuts to adiabaticity
• Quantum Computation as Gravity
• Energy-time uncertainty relation for driven quantum systems
• Complexity Growth for AdS Black Holes
• Tradeoffs for reliable quantum information storage in 2D systems
• Geometric derivation of the quantum speed limit
• Quantum Speed Limits Across the Quantum-to-Classical Transition
• Circuit complexity in interacting QFTs and RG flows
• Quantum Complexity and Negative Curvature
• Consciousness as a State of Matter
• Quantum Speed Limit is Not Quantum
• Stochastic thermodynamics of computation
• Quantum speedup in a memory environment
• The Minimal Work Cost of Information Processing
• Boltzmann brains and the scale-factor cutoff measure of the multiverse
• Tightening Quantum Speed Limits for Almost All States
• Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve and universal reversible logic gate
• Fluctuations in extractable work bound the charging power of quantum batteries
• Quantum Computational Complexity -- From Quantum Information to Black Holes and Back
• Quantum Speed Limit for Perfect State Transfer in One Dimension
• Speed limit for open quantum systems
• Environment assisted speed-up of the field evolution in cavity QED
• On Volumes of Subregions in Holography and Complexity
• Communication at the quantum speed limit along a spin chain
• Discontinuities of the quantum Fisher information and the Bures metric
• Time Evolution of Complexity: A Critique of Three Methods
• Single-atom demonstration of quantum Landauer principle
• Bypassing the bandwidth theorem with PT symmetry
• Universal chaotic dynamics from Krylov space
• Black holes, complexity and quantum chaos
• Quantum Coherence Sets The Quantum Speed Limit For Mixed States
• Selected topics in Planck-scale physics
• Fundamental decoherence from quantum gravity: a pedagogical review
• Holographic Complexity in Vaidya Spacetimes I
• Simple expression for the quantum Fisher information matrix
• Ultimate Speed Limits to the Growth of Operator Complexity
• Estimation of Gaussian quantum states
• Holographic Complexity of Einstein-Maxwell-Dilaton Gravity
• Complexity Growth with Lifshitz Scaling and Hyperscaling Violation
• Holographic Complexity Equals Which Action?
• Mechanism for quantum speedup in open quantum systems
• Unifying Quantum and Classical Speed Limits on Observables
• On Complexity for Higher Derivative Gravities
• Tight, robust, and feasible quantum speed limits for open dynamics
• Holographic Spacetimes as Quantum Circuits of Path-Integrations
• Krylov complexity and orthogonal polynomials
• Quantum-speed-limit time for multiqubit open systems
• The effect of Dilaton on the holographic complexity growth
• A free energy principle for generic quantum systems
• Quantum Speed Limit Bounds in an Open Quantum Evolution
• A Complexity for Quantum Field Theory States and Application in Thermofield Double States
• From computation to black holes and space-time foam
• Galactic Gradients, Postbiological Evolution and the Apparent Failure of SETI
• Complexity for Conformal Field Theories in General Dimensions
• The role of entanglement in dynamical evolution
• Conservative Quantum Computing
• Algorithmic Theories of Everything
• Geometric quantum speed limits: a case for Wigner phase space
• Speeding up critical system dynamics through optimized evolution
• Complexity in de Sitter Space
• Chaotic strings in AdS/CFT
• Complexity Growth Rate in Lovelock Gravity
• On the Connection Between Entanglement and the Speed of Quantum Evolution
• Evolution of Complexity Following a Global Quench
• Quantum fluctuations hinder finite-time information erasure near the Landauer limit
• Holographic subregion complexity under a thermal quench
• Zermelo Navigation and a Speed Limit to Quantum Information Processing
• Action growth of charged black holes with a single horizon
• The thermodynamic efficiency of computations made in cells across the range of life
• Action quantum speed limits
• Demonstration of quantum brachistochrones between distant states of an atom
• Strong energy condition and complexity growth bound in holography
• The Beginning and the End: The Meaning of Life in a Cosmological Perspective
• Subregion Action and Complexity
• Entanglement and the Lower Bounds on the Speed of Quantum Evolution
• Quantum speed limit for a mixed initial state
• The Quantum Speed Limit of Optimal Controlled Phasegates for Trapped Neutral Atoms
• Holographic complexity and non-commutative gauge theory
• Physical limits of inference
• Complexity growth rates for AdS black holes in massive gravity and $f(R)$ gravity
• Complexity of the AdS Soliton
• Surface Counterterms and Regularized Holographic Complexity
• Almost Certain Escape from Black Holes
• Sewing spacetime with Lorentzian threads: complexity and the emergence of time in quantum gravity
• Time Dependence of Holographic Complexity in Gauss-Bonnet Gravity
• On the time dependence of holographic complexity in a dynamical Einstein-dilaton model
• Time-optimal navigation through quantum wind
• Aspects of The First Law of Complexity
• Holographic complexity and action growth in massive gravities
• Constraints on the Universe as a Numerical Simulation
• Quantum speed limits and optimal Hamiltonians for driven systems in mixed states
• Divergences in the rate of complexification
• Testing Holographic Conjectures of Complexity with Born-Infeld Black Holes
• Complexity is Simple
• Observing crossover between quantum speed limits
• Fundamental work cost of quantum processes
• Speed limits in Liouville space for open quantum systems
• Complexity and Behind the Horizon Cut Off
• Complexity of Holographic Superconductors
• Complexity for Charged Thermofield Double States
• Thermodynamics of computing with circuits
• Quantum speed limits on operator flows and correlation functions
• On complexity growth in massive gravity theories, the effects of chirality and more
• Fast quantum computation at arbitrarily low energy
• Quantum Speed Limits under Continuous Quantum Measurements
• Role of non-Markovianity and backflow of information in the speed of quantum evolution
• Controlling quantum critical dynamics of isolated systems
• Topological Speed Limit
• Neurons as hierarchies of quantum reference frames
• Complexity and action for warped AdS black holes
• Estimation of the information contained in the visible matter of the universe
• Quantum complexity in gravity, quantum field theory, and quantum information science
• Goos-Hanchen shift of a spin-wave beam transmitted through anisotropic interface between two ferromagnets
• Holographic complexity of anisotropic black branes
• Performance Evaluation of Adiabatic Quantum Computation via Quantum Speed Limits and Possible Applications to Many-Body Systems
• Fundamental Speed Limits to the Generation of Quantumness
• Tight Upper Bound Of The Maximum Speed Of Evolution Of A Quantum State
• Nonequilibrium thermodynamics of erasure with superconducting flux logic
• On the Noether charge and the gravity duals of quantum complexity
• Nonequilibrium uncertainty principle from information geometry
• Thoughts on Holographic Complexity and its Basis-dependence
• Holographic Complexity Growth Rate in Horndeski Theory
• Thermodynamic costs of Turing Machines
• Quantum dynamical speedup in correlated noisy channels
• Quantum Evolution Time Limit: a General Non-Markovian Bound
• Quantum speed limit of a photon under non-Markovian dynamics
• Extensions of the Mandelstam-Tamm quantum speed limit to systems in mixed states
• General Bounds on Holographic Complexity
• Computing with a single qubit faster than the computation quantum speed limit
• Algorithmic Pseudorandomness in Quantum Setups
• Complexity Functionals and Complexity Growth Limits in Continuous MERA Circuits
• Spacetime foam
• Emergent biological principles and the computational properties of the universe
• Volume and complexity for warped AdS black holes
• Quantum speed limit for a relativistic electron in a uniform magnetic field
• Complexity and phase transitions in a holographic QCD model
• Fundamental energy cost of finite-time computing
• $T\bar{T}$ Deformation and the Complexity=Volume Conjecture
• Chaos and Complexity for Inverted Harmonic Oscillators
• Excited-state quantum phase transition and the quantum speed limit
• Quantum control limited by quantum decoherence
• Complexity and entanglement in non-local computation and holography
• Comparison of holographic and field theoretic complexities by time dependent thermofield double states
• Action Growth in $f\left(R\right)$ Gravity
• Complexity/Action duality of shock wave geometry in a massive gravity theory
• Information Equation of State
• Quantum teleportation through time-shifted AdS wormholes
• Entangling protocols due to non-Markovian dynamics
• Physically-Relativized Church-Turing Hypotheses
• Complexity growth of rotating black holes with a probe string
• On volume subregion complexity in Vaidya spacetime
• Thermodynamic Information Geometry and Complexity Growth of Warped AdS Black Hole and the WAdS${}_3$/CFT${}_2$ Correspondence
• Quantum speed limit for thermal states
• The nonequilibrium cost of accurate information processing
• Holographic complexity and thermodynamics of AdS black holes
• Modified "complexity equals action" conjecture
• On Complexity of Jackiw-Teitelboim Gravity
• Multiparameter Quantum Estimation Theory in Quantum Gaussian states
• On the Role of Counterterms in Holographic Complexity
• Hunting Quantum Gravity with Analogs: the case of graphene
• Efficiency Theory: a Unifying Theory for Information, Computation and Intelligence
• Holographic complexity in charged Vaidya black hole
• The Future of Scientific Simulations: from Artificial Life to Artificial Cosmogenesis
• Dear Qubitzers, GR=QM
• Physical time-energy cost of a quantum process determines its information fidelity
• Complexity growth and shock wave geometry in AdS-Maxwell-power-Yang-Mills theory
• On the time dependence of holographic complexity for charged AdS black holes with scalar hair
• Controlled quantum state transfer in $XX$ spin chains at the Quantum Speed Limit
• Quantum speed limit for robust state characterization and engineering
• More on Complexity in Finite Cut Off Geometry
• Impossibility Results in AI: A Survey
• Landauer Principle and Thermodynamics of Computation
• Quantum Control in Open and Periodically Driven Systems
• Volume complexity of dS bubbles
• Non-signaling deterministic models for non-local correlations have to be uncomputable
• Quantum speed limit in quantum sensing
• Holographic complexity growth in a FLRW universe
• Terminal Holographic Complexity
• Approximation of Reachable Set for Coherently Controlled Open Quantum Systems: Application to Quantum State Engineering
• Complexity, Information Geometry, and Loschmidt Echo near Quantum Criticality
• Time-Energy Measure for Quantum Processes
• Optimal uncertainty relations in a modified Heisenberg algebra
• Thermodynamic Computing
• Evolution of Holographic Complexity Near Critical Point
• Quantum Foam and Quantum Gravity Phenomenology
• Complexity Growth in Flat Spacetimes
• Holographic complexity for black branes with momentum relaxation
• Holographic complexity of charged Taub-NUT-AdS black holes
• Spacetime Foam, Holographic Principle, and Black Hole Quantum Computers
• Complexity of Hyperscaling Violating Theories at Finite Cutoff
• Holographic complexity of Jackiw-Teitelboim gravity from Karch-Randall braneworld
• Revisit on holographic complexity in two-dimensional gravity
• Universality of Black Hole Quantum Computing
• Can Intelligence Explode?
• Quantum speed limit for states and observables of perturbed open systems
• Towards the speed limit of high fidelity 2-qubit gates
• Landauer Bound for Analog Computing Systems
• Space-bounded Church-Turing thesis and computational tractability of closed systems
• Quantum teleprotation with sonic black holes
• Twisted soft photon hair implants on Black Holes
• Thermodynamic correlation inequality
• Holographic complexity of Born-Infeld black holes
• Zeno meets modern science
• Holographic Dark Information Energy
• Negative Feedback and Physical Limits of Genes
• Ohmic Reservoir-based non-Markovianity and Quantum Speed Limit Time
• Complexity and Multi-boundary Wormholes
• Comments on Joint Terms in Gravitational Action
• Accuracy of the adiabatic-impulse approximation for closed and open quantum systems
• Holographic complexity: braneworld gravity versus the Lloyd bound
• Complexity growth in Gubser-Rocha models with momentum relaxation
• Quantum information processing: The case of vanishing interaction energy
• Holographic Complexity Bounds
• Quantum speed limits in arbitrary phase spaces
• Holographic complexity in general quadratic curvature theory of gravity
• Quantum Speed Limit under Brachistochrone Evolution
• A comparison between D-wave and a classical approximation algorithm and a heuristic for computing the ground state of an Ising spin glass
• Chapter: Vulnerability of Quantum Information Systems to Collective Manipulation
• Type III Societies (Apparently) Do Not Exist
• Stringy Effects and the Role of the Singularity in Holographic Complexity
• Complexity Growth Following Multiple Shocks
• Effects of quintessence dark energy on the action growth and butterfly velocity
• Quantum speed limit of Jaynes-Cummings model with detuning for arbitrary initial states
• Generalized speed and cost rate in transitionless quantum driving
• Experimentally probing Landauer's principle in the quantum many-body regime
• Elementary solution to the time-independent quantum navigation problem
• Optimal Ordered Problem Solver
• Subsystem Information Capacity in Random Circuits and Hamiltonian Dynamics
• On Quantum Complexity
• Complexity measures in QFT and constrained geometric actions
• Holographic Complexity in FRW Spacetimes
• Unconditionally secure quantum commitments with preprocessing
• A single-world consistent interpretation of quantum mechanics from fundamental time and length uncertainties
• Complexity growth of massive black hole with a probe string
• Reconsidering the black hole final state in Dirac fields
• Black Holes and Marchenko-Pastur Distribution
• Reparameterization Dependence is Useful for Holographic Complexity
• Analyticity constraints bound the decay of the spectral form factor
• Physical limits on information processing
• Quantumness and speedup limit of a qubit under transition frequency modulation
• Entangled Space-Time
• Quantum Speed Limits Based on Schatten Norms: Universality and Tightness
• Dissipative Quantum Dynamics and Optimal Control using Iterative Time Ordering: An Application to Superconducting Qubits
• Action complexity of charged black holes with higher derivative interactions
• Quantum Speed Limit With Forbidden Speed Intervals
• Geometric quantum complexity of bosonic oscillator systems
• On the Interpretation of Energy as the Rate of Quantum Computation
• Lower Bounds for the Trotter Error
• Phase covariant channel: Quantum speed limit of evolution
• Purity Speed Limit of Open Quantum Systems from Magic Subspaces
• Holographic Complexity in a Charged Supersymmetric Black Holes
• Quantum speed limit from a quantum-state-diffusion method
• Hybrid quantum-classical simulation of quantum speed limits in open quantum systems
• Action Growth of Dyonic Black Holes and Electromagnetic Duality
• Subpicosecond $X$ rotations of atomic clock states
• Upper bound about cross-sections inside black holes and complexity growth rate
• Fluctuation Relation for Qubit-Calorimetry
• Complexity growth for topological black holes by holographic method
• A Holographic Bound for D3-Brane
• Speed limit of quantum dynamics near the event horizon of black holes
• Quantum Limit on Computational Time and Speed
• Entanglement-assisted quantum speedup: Beating local quantum speed limits
• The Universe of Minds
• Holographic complexity under a global quantum quench
• Complexity and typical microstates
• The Log Log Prior for the Frequency of Extraterrestrial Intelligences
• Fundamental Principle of Information-to-Energy Conversion
• Family of Exact and Inexact Quantum Speed Limits for Completely Positive and Trace-Preserving Dynamics
• Number of information and its relation to the cosmological constant resulting from Landauer's principle
• A Computational Model for Quantum Measurement
• Holographic Cavalieri Principle as a Universal relation between Holographic Complexity and Holographic Entanglement Entropy
• Holographic Complexity of Subregions in the Hyperscaling Violating Theories
• Holographic Interpretation of Shannon Entropy of Coherence of Quantum Pure States
• On Measuring Cognition and Cognitive Augmentation
• Distinguishability times and asymmetry monotone-based quantum speed limits in the Bloch ball
• Concept of unified local field theory and nonlocality of matter
• Modified quantum-speed-limit bounds for open quantum dynamics in quantum channels
• Optimal quantum speed for mixed states
• Landauer limit of energy dissipation in a magnetostrictive particle
• Holographic Boundary Conformal Field Theory within Horndeski Gravity
• Bremermann's limit in cGh-physics
• Position dependence of Nielsen complexity for the Thermofield double state
• Towards a Fisher-information description of complexity in de Sitter universe
• Localizing and excluding quantum information; or, how to share a quantum secret in spacetime
• Near-Landauer-Bound Quantum Computing Using Single Spins
• Family of attainable geometric quantum speed limits
• Probability and consequences of living inside a computer simulation
• Quantum Molecular Robots
• Holographic complexity for nonlinearly charged Lifshitz black holes
• A Geometrical Derivation of a Family of Quantum Speed Limit Results
• Hitchhiker's Guide to the Swampland: The Cosmologist's Handbook to the string-theoretical Swampland Programme
• Finite time measurements by Unruh-DeWitt detector and Landauer's principle
• Insensitivity of the complexity rate of change to the conformal anomaly and Lloyd's bound as a possible renormalization condition
• Consensus between Epistemic Agents is Difficult
• Upper bounds of holographic entanglement entropy growth rate for thermofield double states
• Ultimate Limits to Computation: Anharmonic Oscillator
• Complexity Conjecture of Regular Electric Black Holes
• Efficient Implementation and the Product State Representation of Numbers
• Quantum dynamical speedup for correlated initial states
• Stronger Quantum Speed Limit For Mixed Quantum States
• A Unifying Quantum Speed Limit For Time-Independent Hamiltonian Evolution
• On Complexity of Holographic Flavors
• Quantum black holes, partition of integers and self-similarity
• Time-Energy Costs of Quantum Measurements
• Problem Complexity Research from Energy Perspective
• On the Complexity of a Charged Quantum Oscillator
• Information, information processing and gravity
• Gödel Incompleteness and the Black Hole Information Paradox
• Complexity as a holographic probe of strong cosmic censorship
• Effective information bounds in modified quantum mechanics
• Quantum speed limit for the OTOC from an open systems perspective
• Reparameterization Dependence and Holographic Complexity of Black Holes
• Tighter Lower Bounds on Quantum Annealing Times
• Affinity-based geometric discord and quantum speed limits of its creation and decay
• Krylov complexity of purification
• Complexity Growth of Dyonic Black holes with Quartic Field Strength Corrections
• Coherent Quantum Speed Limits
• Quantum speed-up process of atom in dissipative cavity
• Minimum Energy-Surface Required by Quantum Memory Devices
• Artificial Intelligence Probes for Interstellar Exploration and Colonization
• Rebuilding the Habitable Zone from the Bottom Up with Computational Zones
• Computability and Complexity of Unconventional Computing Devices
• Approaching Landauer's Bound In A Spin-Encoded Quantum Computer
• A Bound on Equipartition of Energy
• Induced Metric And Matrix Inequalities On Unitary Matrices
• Quantum evolution speed in the finite-temperature bosonic environment
• Nuclear Spin 3=2 Electric Quadrupole Relaxation as a Quantum Computation
• Information hiding and retrieval in Rydberg wave packets using half-cycle pulses
• Correlations and energy in mediated dynamics
• Holographic complexity of Born-Infeld gravity
• Hempel's dilemma and the physics of computation
• Quantum speed limits in dephasing dynamics of a qubit system coupled to thermal environments
• On the similarity of Information Energy to Dark Energy
• A time-dependent Tsirelson's bound from limits on the rate of information gain in quantum systems
• Revisiting thermodynamics in computation and information theory
• Probing the Black Hole Interior with Holographic Entanglement Entropy and the Role of AdS/BCFT Correspondence
• Physical limits on computation by assemblies of allosteric proteins
• Applications of Algorithmic Probability to the Philosophy of Mind
• Quantum speed limits based on Jensen-Shannon and Jeffreys divergences for general physical processes
• Quantum collapse as undecidable proposition in an Everettian multiverse
• Full-counting statistics of information content and heat quantity in the steady state and the optimum capacity
• Computational Complexity in Analogue Gravity
• The ultimate physical limits to reversibility
• Switchback effect of holographic complexity in multiple-horizon black holes
• Complexity of Magnetization and Magnetic Simplification
• Quantifying Resource Use in Computations
• Quantum speed limits for an open system in contact with a thermal bath
• Complexity vs. Vorticity
• The Computational Power of Minkowski Spacetime
• Holographic complexity of rotating black holes
• An Architecture of Deterministic Quantum Central Processing Unit
• Quantum speed limit and nonclassicality in open quantum system models using the Wigner function
• What is the maximum rate at which entropy of a string can increase?
• A local model of quantum Turing machines
• The Universal Arrow of Time V-VI: (Part V) Unpredictable dynamics (Part VI) Future of artificial intelligence - Art, not Science: Practical Application of Unpredictable Systems
• Astrophysical constraints on the simulation hypothesis for this Universe: why it is (nearly) impossible that we live in a simulation
• Propagation-Distance Limit for a Classical Nonlocal Optical System
• Systems that saturate the Margolus-Levitin quantum speed limit
• Nonlinear speed-ups in ultracold quantum gases
• Modulating quantum evolution of moving-qubit by using classical driving
• The temporal resolution limit in quantum sensing
• A Geometric Quantum Speed Limit: Theoretical Insights and Photonic Implementation
• Tight bounds of quantum speed limit for noisy dynamics via maximum rotation angles
• Engines of Parsimony: Part I; Limits on Computational Rates in Physical Systems
• Upper bound inequality for calculation time in simulated annealing analogous to adiabatic theorem in quantum systems
• Thermal Quantum Speed Limit for Classical-Driving Open Systems
• Probe strings on AdS accelerating black holes
• A useful fundamental speed limit for the imaginary-time Schrodinger equation
• Geometric measure of quantum complexity in cosmological systems
• Ultimate Intelligence Part II: Physical Measure and Complexity of Intelligence
• Simulating Auxiliary Inputs, Revisited
• Is the Universe roughly-tuned for computing?
• Speed limits on classical chaos
• The pollen and the electron: a study in randomness
• Complexity of the Einstein-Born-Infeld-Massive Black holes
• Inverse anisotropic catalysis and complexity
• Semantic Network Layering
• Ultimate Intelligence Part III: Measures of Intelligence, Perception and Intelligent Agents
• Comments on Information Erasure in Black Hole
• Global causality in space-time universe
• Control cost and quantum speed limit time in controlled almost exact state transmission in open systems
• The zero energy quantum informtaiton processing
• On Logic Gates with Complex Numbers
• Difference Principle and Black-hole Thermodynamics
• Quantum partial coherence measures constructed from Fisher information
• Holographic Interpretation of Relative State Complexity
• Quantum time uncertainty in Schwarzschild-anti-de Sitter black holes
• Can we debug the Universe?
• Ultimate Intelligence Part I: Physical Completeness and Objectivity of Induction
• Is Post Selection Physical: A Device Independent Outlook
• Do the uncertainty relations really have crucial significances for physics ?
• Quantum speed limit for observables from quantum asymmetry
• Quantifying Shannon's Work Function for Cryptanalytic Attacks
• The Dyson Minds 2025 Workshop: SETI around Black Holes
• The Accelerating Universe and the Second Law
• Quantum Computation
• The problem of what exists