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:2606.26162

Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics

Agung Trisetyarso, Lenny Putri Yulianti, Kridanto Surendro

quant-phSubmitted Jun 24, 2026• Announced Jun 25, 2026• 0 citations
arXivHTMLPDF

Abstract

We introduce \emph{Dissipative Quantum Multiplicative Weights with Sampling Feedback} (DQMW-Sample), an online-learning primitive in which engineered open quantum-system dynamics prepare a Gibbs state whose computational-basis measurement supplies the loss feedback. The central conceptual contribution is to lift the computational hardness of constant-temperature Gibbs sampling into a physically realizable online-learning primitive. By engineering a Davies-type dissipator whose per-round feedback cannot be efficiently simulated classically, we obtain a learning-theoretic separation in which DQMW-Sample achieves asymptotically sublinear regret while every efficient classical learner suffers constant average regret on a suitably constructed instance. We further prove that the spectral gap of the engineered dissipator contracts hardware noise, yielding sublinear noise-induced regret under a balanced dissipation schedule, and we strengthen the single-round hardness to the full adaptive interaction: an efficient classical simulator of the entire $T$-round feedback process would collapse the polynomial hierarchy. We state the required realizability assumption in explicit form and report an initial hardware characterization on the IBM Heron~r2 processor. These results position DQMW-Sample as a concrete route toward computational advantage in online learning that is grounded in complexity theory and compatible with near-term superconducting hardware.

Comments
main manuscript 10 pages, 9 figrues, appendixes 19 pages

Related papers

Dissipative Quantum Multiplicative Weights

Agung Trisetyarso

Dissipative Quantum Multiplicative Weights (DQMW) is proposed as a quantum algorithm for online matrix learning that achieves the same regret guarantees as classical Matrix Multiplicative Weights while offering significant practical advantages for near-term quantum devices. By leveraging engineered dissipation in the Lindblad master equation, DQMW naturally incorporates physical noise and requires only polynomially scaling classical memory, in contrast to previous quantum formulations that demand exponential classical resources. We derive rigorous regret bounds, establish a no-regret condition under appropriate dissipation schedules, and prove robustness to hardware noise. Notably, the algorithm does not rely on quantum coherence to attain its performance, but instead provides a resource-efficient and noise-resilient framework suitable for implementation on current quantum hardware.

•Jun 18, 2026•0 citations

Quantum Computational Advantage with Constant-Temperature Gibbs Sampling

Thiago Bergamaschi, Chi-Fang Chen, Yunchao Liu

A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physically-motivated model of quantum computation. However, whether quantum computational advantage can be achieved within this realistic physical setup has remained open, due to the challenge of finding systems that thermalize quickly, but are classically intractable. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures, and prove that this task demonstrates quantum computational advantage. We design a family of commuting local Hamiltonians (parent Hamiltonians of shallow quantum circuits) and prove that they rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). On the other hand, we show that no polynomial time classical algorithm can sample from the measurement outcome distribution by reducing to the classical hardness of sampling from noiseless shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits against input noise.

arXiv:2404.14639•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•42 citations

Simulating Thermal Properties of Bose-Hubbard Models on a Quantum Computer

Simon Becker, Cambyse Rouzé, Robert Salzmann

While recent advances have established efficient quantum algorithms for preparing Gibbs states of finite-dimensional systems, comparable complexity results for bosonic and other infinite-dimensional models remain unexplored. We introduce the first general rigorous Gibbs sampling framework for bosonic many-body systems, showing that physically relevant bosonic models admit gapped dissipative generators, enabling efficient preparation of thermal states, provided that the spectral gap scales favourably with the number of modes. Although our results hold for broad classes of models, we illustrate them using Bose-Hubbard Hamiltonians, both within and beyond the mean-field regime. In both cases, we show that the associated dissipative generators maintain a positive spectral gap, thereby implying exponential convergence to the thermal state. For the Gibbs sampler corresponding to the full Bose-Hubbard model, we obtain a spectral-gap lower bound $Ce^{-cn}$, where $n$ is the number of modes. We apply our results to provide a Gibbs-state preparation algorithm on qubit hardware, with runtime polynomial in the number of modes and the inverse spectral gap, and thereby obtain a quantum algorithm to compute thermal properties of the model. This provides the first mathematically controlled route to Gibbs sampling in infinite-dimensional systems, with implications for quantum simulation, thermalization, and many-body complexity, where quantum advantages may arise.

quant-pharXiv:2604.06077•Apr 8, 2026•3 citations

Efficient and SPAM-Robust Ansatz-Free Lindbladian Learning

Savar D. Sinha

Describing the dynamics of open systems is essential for fault-tolerant quantum computation. Under Markovian assumptions, we can characterize dissipative dynamics via the Lindbladian. Using Bell sampling, we provide an efficient, ansatz-free Lindbladian learning algorithm with polynomial-time classical postprocessing. Motivated by the prevalence of state preparation and measurement (SPAM) noise on near-term devices, we also introduce the first efficient SPAM-robust protocol capable of learning the gauge-independent components of sparse Lindbladians to arbitrary precision in the presence of constant-order SPAM error. In doing so, we provide the first rigorous characterization of the gauge degrees of freedom in noisy Lindbladian learning, precisely identifying which components remain learnable under SPAM noise.

quant-pharXiv:2606.20706•Jun 17, 2026•8 citations

Reinforcement learning for quantum processes with memory

Josep Lumbreras, Ruo Cheng Huang, Yanglin Hu +2 more

In reinforcement learning, an agent interacts sequentially with an environment to maximize a reward, receiving only partial, probabilistic feedback. This creates a fundamental exploration-exploitation trade-off: the agent must explore to learn the hidden dynamics while exploiting this knowledge to maximize its target objective. While extensively studied classically, applying this framework to quantum systems requires dealing with hidden quantum states that evolve via unknown dynamics. We formalize this problem via a framework where the environment maintains a hidden quantum memory evolving via unknown quantum channels, and the agent intervenes sequentially using quantum instruments. For this setting, we adapt an optimistic maximum-likelihood estimation algorithm. We extend the analysis to continuous action spaces, allowing us to model general positive operator-valued measures (POVMs). By controlling the propagation of estimation errors through quantum channels and instruments, we prove that the cumulative regret of our strategy scales as $\widetilde{\mathcal{O}}(\sqrt{K})$ over $K$ episodes. Furthermore, via a reduction to the multi-armed quantum bandit problem, we establish information-theoretic lower bounds demonstrating that this sublinear scaling is strictly optimal up to polylogarithmic factors. As a physical application, we consider state-agnostic work extraction. When extracting free energy from a sequence of non-i.i.d. quantum states correlated by a hidden memory, any lack of knowledge about the source leads to thermodynamic dissipation. In our setting, the mathematical regret exactly quantifies this cumulative dissipation. Using our adaptive algorithm, the agent uses past energy outcomes to improve its extraction protocol on the fly, achieving sublinear cumulative dissipation, and, consequently, an asymptotically zero dissipation rate.

quant-pharXiv:2603.25138•Mar 27, 2026•3 citations

Learning with Quantum Examples: Multiclass, Online, and Smoothed Settings

Preetham Mohan

As quantum computing progresses toward fault-tolerant architectures, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory, and in particular learning from quantum examples, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e., worst-case) PAC learning, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast, under the uniform distribution, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together, these results reveal a striking dichotomy. However, this understanding has largely been developed in the context of learning Boolean functions in the batch setting, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning, online learning, and smoothed learning. In the multiclass PAC setting, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes, finding that quantum examples continue to yield no distribution-independent separation from classical examples, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon, we develop a smoothed learning framework that constrains distributions to be smooth, interpolating between the concentrated-distribution regime, in which no quantum advantage exists, and the uniform-distribution regime, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions, we establish the robustness of quantum Fourier sampling throughout a nontrivial near-uniform regime in the batch setting and observe that these guarantees extend naturally to the online setting. We further analyze several approaches to recovering the target function once its Fourier support has been identified and, based on these observations, formulate conjectures supporting the persistence of the unbounded quantum advantage throughout this regime. Together, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting, showing that quantum-classical separations depend on the interplay between hypothesis class structure, distributional assumptions, and the degree of adversarial control permitted in the learning process.

•Jan 1, 2026•0 citations
We introduce \emph{Dissipative Quantum Multiplicative Weights with Sampling Feedback} (DQMW-Sample), an online-learning primitive in which engineered open quantum-system dynamics prepare a Gibbs state whose computational-basis measurement supplies the loss feedback. The central conceptual contribution is to lift the computational hardness of constant-temperature Gibbs sampling into a physically realizable online-learning primitive. By engineering a Davies-type dissipator whose per-round feedback cannot be efficiently simulated classically, we obtain a learning-theoretic separation in which DQMW-Sample achieves asymptotically sublinear regret while every efficient classical learner suffers constant average regret on a suitably constructed instance. We further prove that the spectral gap of the engineered dissipator contracts hardware noise, yielding sublinear noise-induced regret under a balanced dissipation schedule, and we strengthen the single-round hardness to the full adaptive interaction: an efficient classical simulator of the entire TTT-round feedback process would collapse the polynomial hierarchy. We state the required realizability assumption in explicit form and report an initial hardware characterization on the IBM Heron~r2 processor. These results position DQMW-Sample as a concrete route toward computational advantage in online learning that is grounded in complexity theory and compatible with near-term superconducting hardware.
Dissipative Quantum Multiplicative Weights (DQMW) is proposed as a quantum algorithm for online matrix learning that achieves the same regret guarantees as classical Matrix Multiplicative Weights while offering significant practical advantages for near-term quantum devices. By leveraging engineered dissipation in the Lindblad master equation, DQMW naturally incorporates physical noise and requires only polynomially scaling classical memory, in contrast to previous quantum formulations that demand exponential classical resources. We derive rigorous regret bounds, establish a no-regret condition under appropriate dissipation schedules, and prove robustness to hardware noise. Notably, the algorithm does not rely on quantum coherence to attain its performance, but instead provides a resource-efficient and noise-resilient framework suitable for implementation on current quantum hardware.
A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physically-motivated model of quantum computation. However, whether quantum computational advantage can be achieved within this realistic physical setup has remained open, due to the challenge of finding systems that thermalize quickly, but are classically intractable. Here we consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures, and prove that this task demonstrates quantum computational advantage. We design a family of commuting local Hamiltonians (parent Hamiltonians of shallow quantum circuits) and prove that they rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). On the other hand, we show that no polynomial time classical algorithm can sample from the measurement outcome distribution by reducing to the classical hardness of sampling from noiseless shallow quantum circuits. The key step in the reduction is constructing a fault-tolerance scheme for shallow IQP circuits against input noise.
While recent advances have established efficient quantum algorithms for preparing Gibbs states of finite-dimensional systems, comparable complexity results for bosonic and other infinite-dimensional models remain unexplored. We introduce the first general rigorous Gibbs sampling framework for bosonic many-body systems, showing that physically relevant bosonic models admit gapped dissipative generators, enabling efficient preparation of thermal states, provided that the spectral gap scales favourably with the number of modes. Although our results hold for broad classes of models, we illustrate them using Bose-Hubbard Hamiltonians, both within and beyond the mean-field regime. In both cases, we show that the associated dissipative generators maintain a positive spectral gap, thereby implying exponential convergence to the thermal state. For the Gibbs sampler corresponding to the full Bose-Hubbard model, we obtain a spectral-gap lower bound Ce−cnCe^{-cn}Ce−cn, where nnn is the number of modes. We apply our results to provide a Gibbs-state preparation algorithm on qubit hardware, with runtime polynomial in the number of modes and the inverse spectral gap, and thereby obtain a quantum algorithm to compute thermal properties of the model. This provides the first mathematically controlled route to Gibbs sampling in infinite-dimensional systems, with implications for quantum simulation, thermalization, and many-body complexity, where quantum advantages may arise.
Describing the dynamics of open systems is essential for fault-tolerant quantum computation. Under Markovian assumptions, we can characterize dissipative dynamics via the Lindbladian. Using Bell sampling, we provide an efficient, ansatz-free Lindbladian learning algorithm with polynomial-time classical postprocessing. Motivated by the prevalence of state preparation and measurement (SPAM) noise on near-term devices, we also introduce the first efficient SPAM-robust protocol capable of learning the gauge-independent components of sparse Lindbladians to arbitrary precision in the presence of constant-order SPAM error. In doing so, we provide the first rigorous characterization of the gauge degrees of freedom in noisy Lindbladian learning, precisely identifying which components remain learnable under SPAM noise.
In reinforcement learning, an agent interacts sequentially with an environment to maximize a reward, receiving only partial, probabilistic feedback. This creates a fundamental exploration-exploitation trade-off: the agent must explore to learn the hidden dynamics while exploiting this knowledge to maximize its target objective. While extensively studied classically, applying this framework to quantum systems requires dealing with hidden quantum states that evolve via unknown dynamics. We formalize this problem via a framework where the environment maintains a hidden quantum memory evolving via unknown quantum channels, and the agent intervenes sequentially using quantum instruments. For this setting, we adapt an optimistic maximum-likelihood estimation algorithm. We extend the analysis to continuous action spaces, allowing us to model general positive operator-valued measures (POVMs). By controlling the propagation of estimation errors through quantum channels and instruments, we prove that the cumulative regret of our strategy scales as O~(K)\widetilde{\mathcal{O}}(\sqrt{K})O(K​) over KKK episodes. Furthermore, via a reduction to the multi-armed quantum bandit problem, we establish information-theoretic lower bounds demonstrating that this sublinear scaling is strictly optimal up to polylogarithmic factors. As a physical application, we consider state-agnostic work extraction. When extracting free energy from a sequence of non-i.i.d. quantum states correlated by a hidden memory, any lack of knowledge about the source leads to thermodynamic dissipation. In our setting, the mathematical regret exactly quantifies this cumulative dissipation. Using our adaptive algorithm, the agent uses past energy outcomes to improve its extraction protocol on the fly, achieving sublinear cumulative dissipation, and, consequently, an asymptotically zero dissipation rate.
As quantum computing progresses toward fault-tolerant architectures, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory, and in particular learning from quantum examples, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e., worst-case) PAC learning, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast, under the uniform distribution, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together, these results reveal a striking dichotomy. However, this understanding has largely been developed in the context of learning Boolean functions in the batch setting, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning, online learning, and smoothed learning. In the multiclass PAC setting, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes, finding that quantum examples continue to yield no distribution-independent separation from classical examples, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon, we develop a smoothed learning framework that constrains distributions to be smooth, interpolating between the concentrated-distribution regime, in which no quantum advantage exists, and the uniform-distribution regime, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions, we establish the robustness of quantum Fourier sampling throughout a nontrivial near-uniform regime in the batch setting and observe that these guarantees extend naturally to the online setting. We further analyze several approaches to recovering the target function once its Fourier support has been identified and, based on these observations, formulate conjectures supporting the persistence of the unbounded quantum advantage throughout this regime. Together, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting, showing that quantum-classical separations depend on the interplay between hypothesis class structure, distributional assumptions, and the degree of adversarial control permitted in the learning process.