The paper "Quantum Computational Advantage with Constant-Temperature Gibbs Sampling" by Thiago Bergamaschi, Chi-Fang Chen, and Yunchao Liu explores the possibility of achieving quantum computational advantage in realistic physical setups where a quantum system is coupled to a bath at a fixed, finite temperature. The authors focus on sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures and prove that this task demonstrates quantum computational advantage. Key contributions include: 1. **Design of a Family of Hamiltonians**: The authors design a family of commuting almost-local Hamiltonians (parent Hamiltonians of shallow quantum circuits) that rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). 2. **Classical Hardness**: They show that no polynomial-time classical algorithm can sample from the measurement outcome distribution, reducing the problem to the classical hardness of sampling from noiseless shallow quantum circuits. 3. **Fault-Tolerance Scheme**: The key step involves constructing a fault-tolerance scheme for shallow IQP circuits against input noise, which is crucial for the classical hardness argument. The main result is that for any constant inverse-temperature \(\beta = \Theta(1)\), there exists a family of \(n\)-qubit, commuting, \(O(\log \log n)\)-local Hamiltonians such that: - The Gibbs state \(\rho_{\beta}\) is rapidly thermalizing, converging in polylogarithmic time. - The Gibbs state is classically intractable to sample from, based on certain complexity-theoretic assumptions. The paper also discusses the efficiency of quantum Gibbs state preparation and the fault-tolerance of shallow IQP circuits, providing a detailed analysis of the mixing time of the associated Davies generators and the implementation of these algorithms on a quantum computer. Additionally, it explores the classical hardness of Gibbs sampling under measurement errors and the BQP completeness of Gibbs sampling with adaptive single-qubit measurements.The paper "Quantum Computational Advantage with Constant-Temperature Gibbs Sampling" by Thiago Bergamaschi, Chi-Fang Chen, and Yunchao Liu explores the possibility of achieving quantum computational advantage in realistic physical setups where a quantum system is coupled to a bath at a fixed, finite temperature. The authors focus on sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures and prove that this task demonstrates quantum computational advantage. Key contributions include: 1. **Design of a Family of Hamiltonians**: The authors design a family of commuting almost-local Hamiltonians (parent Hamiltonians of shallow quantum circuits) that rapidly converge to their Gibbs states under the standard physical model of thermalization (as a continuous-time quantum Markov chain). 2. **Classical Hardness**: They show that no polynomial-time classical algorithm can sample from the measurement outcome distribution, reducing the problem to the classical hardness of sampling from noiseless shallow quantum circuits. 3. **Fault-Tolerance Scheme**: The key step involves constructing a fault-tolerance scheme for shallow IQP circuits against input noise, which is crucial for the classical hardness argument. The main result is that for any constant inverse-temperature \(\beta = \Theta(1)\), there exists a family of \(n\)-qubit, commuting, \(O(\log \log n)\)-local Hamiltonians such that: - The Gibbs state \(\rho_{\beta}\) is rapidly thermalizing, converging in polylogarithmic time. - The Gibbs state is classically intractable to sample from, based on certain complexity-theoretic assumptions. The paper also discusses the efficiency of quantum Gibbs state preparation and the fault-tolerance of shallow IQP circuits, providing a detailed analysis of the mixing time of the associated Davies generators and the implementation of these algorithms on a quantum computer. Additionally, it explores the classical hardness of Gibbs sampling under measurement errors and the BQP completeness of Gibbs sampling with adaptive single-qubit measurements.