Generalized Zurek's bound on the cost of an individual classical or quantum computation

Abstract

We consider the minimal thermodynamic cost of an individual computation, where a single input $x$ is mapped to a single output $y$. In prior work, Zurek proposed that this cost was given by $K(x|y)$, the conditional Kolmogorov complexity of $x$ given $y$ (up to an additive constant which does not depend on $x$ or $y$). However, this result was derived from an informal argument, applied only to deterministic computations, and had an arbitrary dependence on the choice of protocol (via the additive constant). Here we use stochastic thermodynamics to derive a generalized version of Zurek's bound from a rigorous Hamiltonian formulation. Our bound applies to all quantum and classical processes, whether noisy or deterministic, and it explicitly captures the dependence on the protocol. We show that $K(x|y)$ is a minimal cost of mapping $x$ to $y$ that must be paid using some combination of heat, noise, and protocol complexity, implying a tradeoff between these three resources. Our result is a kind of "algorithmic fluctuation theorem" with implications for the relationship between the Second Law and the Physical Church-Turing thesis.

arXiv commentNew version fixes some LaTeX errors (some references messed up)

References in corpus (44)

• Concentrating Partial Entanglement by Local Operations
• Quantifying Coherence
• Nonequilibrium fluctuations, fluctuation theorems, and counting statistics in quantum systems
• Colloquium. Quantum Fluctuation Relations: Foundations and Applications
• Fundamental limitations for quantum and nano thermodynamics
• Second Law of Thermodynamics with Discrete Quantum Feedback Control
• The thermodynamic meaning of negative entropy
• Work extraction and thermodynamics for individual quantum systems
• Classical and Quantum Fluctuation Theorems for Heat Exchange
• Quantum Information Processing with Finite Resources -- Mathematical Foundations
• An improved Landauer Principle with finite-size corrections
• Fluctuation Theorem with Information Exchange: Role of Correlations in Stochastic Thermodynamics
• Truly work-like work extraction
• Speed Limit for Classical Stochastic Processes
• Information processing and the second law of thermodynamics: an inclusive, Hamiltonian approach
• The Minimal Work Cost of Information Processing
• Quantum fluctuation theorems for arbitrary environments: adiabatic and non-adiabatic entropy production
• Quantum Kolmogorov Complexity
• Distribution of work in isothermal non-equilibrium processes
• Thermodynamics of discrete quantum processes
• Generalising Landauer's Principle
• Quantum work statistics close to equilibrium
• Quantum Kolmogorov Complexity Based on Classical Descriptions
• Thermodynamic limits of dynamic cooling
• Play. Pause. Rewind. Measuring local entropy production and extractable work in active matter
• Above and Beyond the Landauer Bound: Thermodynamics of Modularity
• Charging assisted by thermalization
• Identifying Functional Thermodynamics in Autonomous Maxwellian Ratchets
• Universal and accessible entropy estimation using a compression algorithm
• A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
• Fluctuation Theorems for a Quantum Channel
• Computable functions, quantum measurements, and quantum dynamics
• Fluctuation theorems from Bayesian retrodiction
• The Asymptotic Cooling of Heat-Bath Algorithmic Cooling
• Fundamental costs in the production and destruction of persistent polymer copies
• Thermodynamics of computing with circuits
• Dependence of dissipation on the initial distribution over states
• Thermodynamic costs of Turing Machines
• Initial-State Dependence of Thermodynamic Dissipation for any Quantum Process
• The impossibility of Landauer's bound for almost every quantum state
• Dependence of integrated, instantaneous, and fluctuating entropy production on the initial state in quantum and classical processes
• Space-bounded Church-Turing thesis and computational tractability of closed systems
• The Free Energy of a General Computation
• Microscopic Reversibility and Macroscopic Irreversibility: From a viewpoint of Algorithmic Randomness

Cited by in corpus (2)

• Landauer Principle and Thermodynamics of Computation
• Hamiltonian quantum gates -- energetic advantage from entangleability