Quantum computational advantage with constant-temperature Gibbs sampling

Abstract

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.

To appear in FOCS 2024. v2: Improved main result to constant locality

References in corpus (24)

• Universal Quantum Computation with ideal Clifford gates and noisy ancillas
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum conditional mutual information and approximate Markov chains
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Stability of Frustration-Free Hamiltonians
• A dissipative quantum Church-Turing theorem
• Computational advantage of quantum random sampling
• Quantum advantage with noisy shallow circuits in 3D
• Quantum logarithmic Sobolev inequalities and rapid mixing
• Quantum Belief Propagation
• Completely positive master equation for arbitrary driving and small level spacing
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Quantum algorithm for Petz recovery channels and pretty good measurements
• Mixing properties of stochastic quantum Hamiltonians
• Thermal State Preparation via Rounding Promises
• Rapid thermalization of spin chain commuting Hamiltonians
• Complete entropic inequalities for quantum Markov chains
• Entropy Production of Doubly Stochastic Quantum Channels
• Quantum conditional relative entropy and quasi-factorization of the relative entropy
• Entropy decay for Davies semigroups of a one dimensional quantum lattice
• Szegedy Walk Unitaries for Quantum Maps
• Robust sparse IQP sampling in constant depth
• Fault-tolerant quantum speedup from constant depth quantum circuits
• Quantum advantage from energy measurements of many-body quantum systems

Cited by in corpus (8)

• Efficient quantum Gibbs samplers with Kubo--Martin--Schwinger detailed balance condition
• Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
• Lindblad engineering for quantum Gibbs state preparation under the eigenstate thermalization hypothesis
• Instability of steady-state mixed-state symmetry-protected topological order to strong-to-weak spontaneous symmetry breaking
• Quantum natural gradient with thermal-state initialization
• Natural gradient and parameter estimation for quantum Boltzmann machines
• Constrained free energy minimization for the design of thermal states and stabilizer thermodynamic systems
• A Randomized Method for Simulating Lindblad Equations and Thermal State Preparation