Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2001.02258 · Physical Review Research

Thermodynamically-efficient local computation and the inefficiency of quantum memory compression

Samuel P. Loomis, James P. Crutchfield

Published Apr 14, 2020• 5 citations
arXivHTMLPDF

Abstract

The authors show that quantum simulations of stochastic processes require less memory than classical simulations---a key quantum advantage over classical computers. However, this compression comes at the cost of increased thermodynamic dissipation. That is, quantum supremacy is incompatible with thermodynamic efficiency.
DOI
10.1103/physrevresearch.2.023039

Related papers

Thermodynamically-efficient local computation and the inefficiency of quantum memory compression

Samuel P. Loomis, James P. Crutchfield

Modularity dissipation identifies how locally implemented computation entails costs beyond those required by Landauer's bound on thermodynamic computing. We establish a general theorem for efficient local computation, giving the necessary and sufficient conditions for a local operation to have zero modularity cost. Applied to thermodynamically-generating stochastic processes it confirms a conjecture that classical generators are efficient if and only if they satisfy retrodiction, which places minimum-memory requirements on the generator. This extends immediately to quantum computation: Any quantum simulator that employs quantum memory compression cannot be thermodynamically efficient.

•Apr 1, 2020•4 citations

Thermal Efficiency of Quantum Memory Compression

Samuel P. Loomis, James P. Crutchfield

Quantum coherence allows for reduced-memory simulators of classical processes. Using recent results in single-shot quantum thermodynamics, we derive a minimal work cost rate for quantum simulators that is quasistatically attainable in the limit of asymptotically infinite parallel simulation. Comparing this cost with the classical regime reveals that quantizing classical simulators not only results in memory compression but also in reduced dissipation. We explore this advantage across a suite of representative examples.

arXiv:1911.00998•Physical Review Letters•Jul 8, 2020•15 citations

Memory compression and thermal efficiency of quantum implementations of nondeterministic hidden Markov models

Thomas J. Elliott

Stochastic modeling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum implementations of deterministic HMMs exhibiting superior memory and thermal efficiency relative to their classical counterparts. In many contexts, however, nondeterministic HMMs are viable alternatives; compared to them, the advantages of current quantum implementations do not always hold. Here, we provide a systematic prescription for constructing quantum implementations of nondeterministic HMMs that reestablish the quantum advantages against this broader class. Crucially, we show that whenever the classical implementation suffers from thermal dissipation due to its need to process information in a time-local manner, our quantum implementations will both mitigate some of this dissipation and achieve an advantage in memory compression.

arXiv:2105.06285•Physical Review A•May 28, 2021•16 citations

Quantum-inspired memory-enhanced stochastic algorithms

John Realpe-Gómez, Nathan Killoran

Stochastic models are highly relevant tools in science, engineering, and society. Recent work suggests emerging quantum computing technologies can substantially decrease the memory requirements for simulating stochastic models. Here we show that some of these recent quantum memory-enhanced algorithms can be either implemented or approximated classically. In other words, we show that it is possible to develop quantum-inspired classical algorithms that require much less memory than the best classical algorithms known to date. Being classical, such algorithms could be implemented in state-of-the-art high-performance computers, which could potentially enhance the study of large-scale complex systems. Furthermore, since memory is the main bottleneck limiting the performance of classical supercomputers in one of the most promising avenues to demonstrate quantum 'supremacy', we expect adaptations of these ideas may potentially further raise the bar for near-term quantum computers to reach such a milestone.

arXiv:1906.00263•Jun 1, 2019•0 citations

Quantum Advantage in Simulating Stochastic Processes

Kamil Korzekwa, Matteo Lostaglio

We investigate the problem of simulating classical stochastic processes through quantum dynamics and present three scenarios where memory or time quantum advantages arise.First, by introducing and analyzing a quantum version of the embeddability problem for stochastic matrices, we show that quantum memoryless dynamics can simulate classical processes that necessarily require memory.Second, by extending the notion of space-time cost of a stochastic process P to the quantum domain, we prove an advantage of the quantum cost of simulating P over the classical cost.Third, we demonstrate that the set of classical states accessible via Markovian master equations with quantum controls is larger than the set of those accessible with classical controls, leading, e.g., to a potential advantage in cooling protocols.

arXiv:2005.02403•Physical Review X•Apr 22, 2021•33 citations

Thermodynamic Advantage of Quantum Time-Reversal

Alexander B. Boyd, Paul M. Riechers

Classical computations inherently require energy dissipation that increases significantly as the reliability of the computation improves. This dissipation arises when transitions between memory states are not balanced by their time-reversed counterparts. While classical memories exhibit a discrete set of possible time-reversal symmetries, quantum memory offers a continuum. This continuum enables the design of quantum memories that minimize irreversibility. As a result, quantum memory reduces energy dissipation several orders of magnitude below classical memory.

arXiv:2501.04865•Jan 8, 2025•0 citations
Modularity dissipation identifies how locally implemented computation entails costs beyond those required by Landauer's bound on thermodynamic computing. We establish a general theorem for efficient local computation, giving the necessary and sufficient conditions for a local operation to have zero modularity cost. Applied to thermodynamically-generating stochastic processes it confirms a conjecture that classical generators are efficient if and only if they satisfy retrodiction, which places minimum-memory requirements on the generator. This extends immediately to quantum computation: Any quantum simulator that employs quantum memory compression cannot be thermodynamically efficient.
Quantum coherence allows for reduced-memory simulators of classical processes. Using recent results in single-shot quantum thermodynamics, we derive a minimal work cost rate for quantum simulators that is quasistatically attainable in the limit of asymptotically infinite parallel simulation. Comparing this cost with the classical regime reveals that quantizing classical simulators not only results in memory compression but also in reduced dissipation. We explore this advantage across a suite of representative examples.
Stochastic modeling is an essential component of the quantitative sciences, with hidden Markov models (HMMs) often playing a central role. Concurrently, the rise of quantum technologies promises a host of advantages in computational problems, typically in terms of the scaling of requisite resources such as time and memory. HMMs are no exception to this, with recent results highlighting quantum implementations of deterministic HMMs exhibiting superior memory and thermal efficiency relative to their classical counterparts. In many contexts, however, nondeterministic HMMs are viable alternatives; compared to them, the advantages of current quantum implementations do not always hold. Here, we provide a systematic prescription for constructing quantum implementations of nondeterministic HMMs that reestablish the quantum advantages against this broader class. Crucially, we show that whenever the classical implementation suffers from thermal dissipation due to its need to process information in a time-local manner, our quantum implementations will both mitigate some of this dissipation and achieve an advantage in memory compression.
Stochastic models are highly relevant tools in science, engineering, and society. Recent work suggests emerging quantum computing technologies can substantially decrease the memory requirements for simulating stochastic models. Here we show that some of these recent quantum memory-enhanced algorithms can be either implemented or approximated classically. In other words, we show that it is possible to develop quantum-inspired classical algorithms that require much less memory than the best classical algorithms known to date. Being classical, such algorithms could be implemented in state-of-the-art high-performance computers, which could potentially enhance the study of large-scale complex systems. Furthermore, since memory is the main bottleneck limiting the performance of classical supercomputers in one of the most promising avenues to demonstrate quantum 'supremacy', we expect adaptations of these ideas may potentially further raise the bar for near-term quantum computers to reach such a milestone.
We investigate the problem of simulating classical stochastic processes through quantum dynamics and present three scenarios where memory or time quantum advantages arise.First, by introducing and analyzing a quantum version of the embeddability problem for stochastic matrices, we show that quantum memoryless dynamics can simulate classical processes that necessarily require memory.Second, by extending the notion of space-time cost of a stochastic process P to the quantum domain, we prove an advantage of the quantum cost of simulating P over the classical cost.Third, we demonstrate that the set of classical states accessible via Markovian master equations with quantum controls is larger than the set of those accessible with classical controls, leading, e.g., to a potential advantage in cooling protocols.
Classical computations inherently require energy dissipation that increases significantly as the reliability of the computation improves. This dissipation arises when transitions between memory states are not balanced by their time-reversed counterparts. While classical memories exhibit a discrete set of possible time-reversal symmetries, quantum memory offers a continuum. This continuum enables the design of quantum memories that minimize irreversibility. As a result, quantum memory reduces energy dissipation several orders of magnitude below classical memory.