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

Agung Trisetyarso, Lenny Putri Yulianti, Kridanto Surendro · 2026

Read Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics by Agung Trisetyarso, Lenny Putri Yulianti, Kridanto Surendro (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26162.txt.

Introduction

Agung Trisetyarso, Lenny Putri Yulianti, and Kridanto Surendro design an online learning method that runs on engineered quantum dynamics. Multiplicative weights is a workhorse rule for learning from repeated feedback. Their variant, DQMW-Sample, prepares a Gibbs state with a tailored open-system process each round. Measuring that state supplies the feedback. The twist is computational hardness: simulating the feedback classically is provably hard at constant temperature.

Separation results follow. On a crafted problem, their learner's regret shrinks toward zero per round over time. Every efficient classical learner keeps constant average regret there. Noise works in their favour as well: the dissipator's spectral gap contracts hardware noise, keeping noise-driven regret sublinear. A stronger result covers the whole adaptive interaction at once. An efficient classical simulator for all rounds would collapse the polynomial hierarchy. Early tests run on an IBM Heron processor.

Catalog record

CREATORAgung Trisetyarso, Lenny Putri Yulianti, Kridanto Surendro
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE99 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26162

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dissipative Quantum Multiplicative Weights with Sampling Feedback: A Classically Hard Primitive Realized via Engineered Open-System Dynamics Agung Trisetyarso, Lenny Putri Yulianti, Kridanto Surendro Abstract We introduce 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 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. 1 Introduction Multiplicative-weights methods are among the most versatile primitives in online learning and optimization: a single update rule underlies algorithms for boosting, zero-sum games, and approximate semidefinite programming [ 4 , 5 , 6 ] . Their matrix generalization—matrix multiplicative weights (MMW), equivalently matrix exponentiated-gradient updates—maintains a density operator and updates it through a Gibbs map \rho_{t}\propto\exp(-\eta\sum_{s<t}L_{s}) , achieving O(\sqrt{T\log d}) regret over the set of d -dimensional density operators [ 7 , 8 ] . This Gibbs-state structure is what connects online learning to physics: the same exponential-family object that an MMW learner must compute is the thermal state that an engineered open quantum system prepares as the fixed point of its dissipative dynamics. The idea of preparing quantum states by engineering dissipation rather than unitary evolution is now well established. Dissipative state engineering uses tailored system–bath couplings so that a target state is the unique steady state of a Lindblad generator [ 32 , 33 ] , and such open-system dynamics have been realized on trapped-ion and other platforms [ 35 , 36 ] . When the engineered jump operators satisfy a Kubo–Martin–Schwinger (KMS) detailed-balance condition, the steady state is precisely the Gibbs state of an effective Hamiltonian, and the rate of approach to it is governed by the spectral gap of the dissipator [ 37 , 38 ] . Dissipative Quantum Multiplicative Weights (DQMW) exploits exactly this correspondence: it realizes the MMW Gibbs map physically, letting an engineered Davies generator drive the learner’s state to the thermal state of the cumulative loss. Conceptual contribution. The central insight of this work is that the computational hardness of sampling from a constant-temperature Gibbs state can be lifted into a physically realizable online-learning primitive . By engineering open-system dynamics whose steady state is the desired Gibbs state and using a computational-basis measurement as loss feedback, we obtain a multiplicative-weights algorithm whose per-round update cannot be efficiently simulated classically (under standard complexity assumptions). This approach is qualitatively different from most existing quantum online-learning proposals, which either rely on expectation values (efficiently simulable classically) or require coherent access to quantum oracles. DQMW-Sample thus provides a concrete route toward computational advantage in online learning that is grounded in complexity theory rather than query complexity or coherence assumptions alone. The key technical step is to connect the recent hardness result of Bergamaschi, Chen and Liu for constant-temperature Gibbs sampling to the multiplicative-weights framework via engineered dissipation, while making the required realizability assumption fully explicit. A natural question is whether this physical realization buys any genuine computational advantage over its classical counterpart. The answer is subtle. If the loss feedback is the expectation \bar{\ell}_{t}=\operatorname{Tr}[L(t)\rho_{\mathrm{Gibbs}}(t)] , the dynamics reduce per round to classical replicator dynamics on populations and inherit no hardness—a manifestation of the broader phenomenon, exposed by the dequantization program, that low-rank or expectation-based quantum routines often admit efficient classical analogues [ 22 , 23 , 24 ] . The situation changes when the feedback is a sample : a single computational-basis measurement of the prepared Gibbs state. Sampling from the measurement distribution of a thermal state is, in general, a strictly harder task than estimating expectations, and recent complexity-theoretic work has pinned down a regime where it is classically intractable. Bergamaschi, Chen and Liu [ 1 ] (BCL) construct a family of O(1) -local Hamiltonians for which sampling from the computational-basis distribution of the constant-temperature Gibbs state cannot be done in classical polynomial time unless the polynomial hierarchy collapses. This sharpens the boundary between the efficiently preparable high-temperature regime [ 2 , 3 ] and the genuinely hard constant-temperature window. In this work we study the sampling-based variant, DQMW-Sample, in which the multiplicative-weights update is driven by realized measurement outcomes rather than expectations, and we ask what the BCL hardness implies for it as an online-learning primitive. Our contributions are as follows. (i) Lifting BCL hardness into an online-learning primitive. We prove that the per-round sampling feedback of DQMW-Sample is classically intractable in a well-defined regime (Lemma A.5 ), via an explicit reduction from the constant-temperature Gibbs-sampling problem of Bergamaschi, Chen and Liu. We isolate the load-bearing realizability assumption (Assumption A.3 ) explicitly rather than absorb it, keeping the conditional nature of the claim visible. (ii) A learning-theoretic separation and an adaptive collapse. Building on this primitive, we exhibit an online-learning instance on which DQMW-Sample is asymptotically no-regret while every efficient classical learner suffers \Omega(1) average regret (Theorem A.14 )—a separation that is computational rather than information-theoretic, since the obstruction is the polynomial-time reconstruction of a hard sample rather than query access. We then strengthen the single-round result to a statement about the entire adaptive interaction: under a mild reachability condition (Assumption A.16 ) and a transcript-marginal reduction (Lemma A.18 ), an efficient classical simulator of the full T -round feedback process would collapse the polynomial hierarchy (Theorem A.19 ). The key difficulty overcome here is adaptivity: a classical simulator is free to steer the realized trajectory away from the hard window, and we neutralize this freedom by reducing from the joint transcript law rather than any single conditional state. This contributes to the active program on the quantum advantage of online learning of quantum states [ 10 , 11 ] . (iii) Noise robustness and a hardware-grounded feasibility study. On the physical side, we prove a noise-robustness theorem (Theorem A.9 ) showing that the spectral gap \gamma_{0} of the engineered dissipator contracts hardware-noise deviations, so that the noise-induced regret is O(\delta\sqrt{T}) under a balanced dissipation schedule \gamma_{0}=\Theta(\sqrt{T}) — provided the noise strength and the dissipation rate are independently controllable (assumption R2). Because the operation that implements engineered dissipation on near-term superconducting hardware—mid-circuit measurement followed by conditional reset—is itself a dominant noise source, R2 is not obviously satisfied. To probe it, we report a Lindblad-model emulation parametrized by published calibration data for the 156-qubit IBM Heron r2 processor ibm_kingston , together with an initial batched hardware characterization. Throughout, we label Lindblad results

Read the complete text