Gibbs Sampling gives Quantum Advantage at Constant Temperatures with O(1)-Local Hamiltonians
Summarize this article with:
AbstractSampling from Gibbs states – states corresponding to system in thermal equilibrium – has recently been shown to be a task for which quantum computers are expected to achieve super-polynomial speed-up compared to classical computers, provided the locality of the Hamiltonian increases with the system size [1]. We extend these results to show that this quantum advantage still occurs for Gibbs states of Hamiltonians with O(1)-local interactions at constant temperature by showing classical hardness-of-sampling and demonstrating such Gibbs states can be prepared efficiently using a quantum computer. In particular, we show hardness-of-sampling is maintained even for 5-local Hamiltonians on a 3D lattice. We additionally show that the hardness-of-sampling is robust when we are only able to make imperfect measurements.Featured image: Schematic showing a phase transition in complexity of Gibbs sampling as temperature changes.Popular summaryDetermining the properties of Gibbs states — the state a system takes when it is in thermal equilibrium — is an important task in physics and computer science. Beyond its practical implications, a major open question has been "how quantum are thermal states for realistic physical systems?" Do thermal effects completely wash out all quantum properties of thermal states, or do quantum effects remain important in studying these states? In this work we show that at constant temperature (i.e., temperature which does not scale with the system size) there are local Hamiltonians for which quantum computers achieve a super-polynomial speedup relative to classical computers for the task of sampling bit strings from the Gibbs state.► BibTeX data@article{Rajakumar2026gibbssamplinggives, doi = {10.22331/q-2026-01-22-1981}, url = {https://doi.org/10.22331/q-2026-01-22-1981}, title = {Gibbs {S}ampling gives {Q}uantum {A}dvantage at {C}onstant {T}emperatures with {O}(1)-{L}ocal {H}amiltonians}, author = {Rajakumar, Joel and Watson, James D.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1981}, month = jan, year = {2026} }► References [1] Thiago Bergamaschi, Chi-Fang Chen, and Yunchao Liu, ``Quantum computational advantage with constant-temperature Gibbs sampling'' 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1063-1085 (2024). https://doi.org/10.1109/FOCS61266.2024.00071 [2] Kristan Temme, Tobias J Osborne, Karl G Vollbrecht, David Poulin, and Frank Verstraete, ``Quantum metropolis sampling'' Nature 471, 87–90 (2011). https://doi.org/10.1038/nature09770 [3] Fernando GSL Brandaoand Michael J Kastoryano ``Finite correlation length implies efficient preparation of quantum thermal states'' Communications in Mathematical Physics 365, 1–16 (2019). https://doi.org/10.1007/s00220-018-3150-8 [4] Jonathan E Moussa ``Low-depth quantum metropolis algorithm'' arXiv preprint arXiv:1903.01451 (2019). https://doi.org/10.48550/arXiv.1903.01451 [5] Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O’Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brandao, and Garnet Kin-Lic Chan, ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution'' Nature Physics 16, 205–210 (2020). https://doi.org/10.1038/s41567-019-0704-4 [6] Evgeny Mozgunovand Daniel Lidar ``Completely positive master equation for arbitrary driving and small level spacing'' Quantum 4, 227 (2020). https://doi.org/10.22331/q-2020-02-06-227 [7] Chi-Fang Chenand Fernando GSL Brandão ``Fast thermalization from the eigenstate thermalization hypothesis'' arXiv preprint arXiv:2112.07646 (2021). https://doi.org/10.48550/arXiv.2112.07646 [8] Pawel Wocjanand Kristan Temme ``Szegedy walk unitaries for quantum maps'' Communications in Mathematical Physics 402, 3201–3231 (2023). https://doi.org/10.1007/s00220-023-04797-4 [9] Oles Shtankoand Ramis Movassagh ``Preparing thermal states on noiseless and noisy programmable quantum processors'' arXiv e-prints arXiv–2112 (2021). https://doi.org/10.48550/arXiv.2112.14688 [10] Daniel Zhang, Jan Lukas Bosse, and Toby Cubitt, ``Dissipative quantum Gibbs sampling'' arXiv preprint arXiv:2304.04526 (2023). https://doi.org/10.48550/arXiv.2304.04526 [11] Chi-Fang Chen, Michael J Kastoryano, Fernando GSL Brandão, and András Gilyén, ``Quantum thermal state preparation'' arXiv preprint arXiv:2303.18224 (2023). https://doi.org/10.48550/arXiv.2303.18224 [12] Jiaqing Jiangand Sandy Irani ``Quantum Metropolis Sampling via Weak Measurement'' arXiv preprint arXiv:2406.16023 (2024). https://doi.org/10.48550/arXiv.2406.16023 [13] Hongrui Chen, Bowen Li, Jianfeng Lu, and Lexing Ying, ``A randomized method for simulating Lindblad equations and thermal state preparation'' Quantum 9, 1917 (2025). https://doi.org/10.22331/q-2025-11-20-1917 [14] Sirui Lu, Mari Carmen Bañuls, and J Ignacio Cirac, ``Algorithms for quantum simulation at finite energies'' PRX Quantum 2, 020321 (2021). https://doi.org/10.1103/PRXQuantum.2.020321 [15] Alexander Schuckert, Annabelle Bohrdt, Eleanor Crane, and Michael Knap, ``Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics'' Physical Review B 107, L140410 (2023). https://doi.org/10.1103/PhysRevB.107.L140410 [16] Khaldoon Ghanem, Alexander Schuckert, and Henrik Dreyer, ``Robust extraction of thermal observables from state sampling and real-time dynamics on quantum computers'' Quantum 7, 1163 (2023). https://doi.org/10.22331/q-2023-11-03-1163 [17] Chi-Fang Chen, Michael J Kastoryano, and András Gilyén, ``An efficient and exact noncommutative quantum gibbs sampler'' arXiv preprint arXiv:2311.09207 (2023). https://doi.org/10.48550/arXiv.2311.09207 [18] András Gilyén, Chi-Fang Chen, Joao F Doriguello, and Michael J Kastoryano, ``Quantum generalizations of Glauber and Metropolis dynamics'' arXiv preprint arXiv:2405.20322 (2024). https://doi.org/10.48550/arXiv.2405.20322 [19] Daniel Stilck França ``Perfect sampling for quantum gibbs states'' Quantum Info. Comput. 18, 361–388 (2018). https://doi.org/10.26421/qic18.5-6-1 [20] Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar, ``Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems'' Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing 378–386 (2020). https://doi.org/10.1145/3357713.3384322 [21] Ryan L Mannand Tyler Helmuth ``Efficient algorithms for approximating quantum partition functions'' Journal of Mathematical Physics 62 (2021). https://doi.org/10.22331/q-2023-10-25-1155 [22] Chao Yinand Andrew Lucas ``Polynomial-time classical sampling of high-temperature quantum Gibbs states'' arXiv preprint arXiv:2305.18514 (2023). https://doi.org/10.48550/arXiv.2305.18514 [23] Cambyse Rouzé, Daniel Stilck França, and Álvaro M Alhambra, ``Efficient thermalization and universal quantum computing with quantum Gibbs samplers'' Proceedings of the 57th Annual ACM Symposium on Theory of Computing 1488–1495 (2025). https://doi.org/10.1145/3717823.3718268 [24] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang, ``High-temperature Gibbs states are unentangled and efficiently preparable'' 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1027–1036 (2024). https://doi.org/10.1109/FOCS61266.2024.00068 [25] Allan Sly ``Computational transition at the uniqueness threshold'' 2010 IEEE 51st Annual Symposium on Foundations of Computer Science 287–296 (2010). https://doi.org/10.1109/FOCS.2010.34 [26] Isaac J Crosson, Dave Bacon, and Kenneth R Brown, ``Making classical ground-state spin computing fault-tolerant'' Physical Review E 82, 031106 (2010). https://doi.org/10.1103/PhysRevE.82.031106 [27] Allan Slyand Nike Sun ``The computational hardness of counting in two-spin models on d-regular graphs'' 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science 361–369 (2012). https://doi.org/10.1109/FOCS.2012.56 [28] Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan, ``Quantum Hamiltonian complexity in thermal equilibrium'' Nature Physics 18, 1367–1370 (2022). https://doi.org/10.1038/s41567-022-01742-5 [29] Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtěch Havlíček, and Guanyu Zhu, ``Quantum complexity of the Kronecker coefficients'' PRX Quantum 5, 010329 (2024). https://doi.org/10.1103/PRXQuantum.5.010329 [30] Fernando GSL Brandão ``Entanglement theory and the quantum simulation of many-body physics'' arXiv preprint arXiv:0810.0026 (2008). https://doi.org/10.48550/arXiv.0810.0026 [31] David Gamarnik, Bobak T. Kiani, and Alexander Zlokapa, ``Slow Mixing of Quantum Gibbs Samplers'' arXiv e-prints arXiv:2411.04300 (2024). https://doi.org/10.48550/arXiv.2411.04300 arXiv:2411.04300 [32] Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, ``Optimizing random local Hamiltonians by dissipation'' arXiv e-prints arXiv:2411.02578 (2024). https://doi.org/10.48550/arXiv.2411.02578 arXiv:2411.02578 [33] Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, and Leo Zhou, ``Local minima in quantum systems'' Proceedings of the 56th Annual ACM Symposium on Theory of Computing 1323–1330 (2024). https://doi.org/10.1038/s41567-025-02781-4 [34] Štěpán Šmíd, Richard Meister, Mario Berta, and Roberto Bondesan, ``Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems'' arXiv e-prints arXiv:2510.04954 (2025). https://doi.org/10.48550/arXiv.2510.04954 arXiv:2510.04954 [35] Thiago Bergamaschiand Chi-Fang Chen ``Quantum Spin Chains Thermalize at All Temperatures'' arXiv e-prints arXiv:2510.08533 (2025). https://doi.org/10.48550/arXiv.2510.08533 arXiv:2510.08533 [36] Andrew M Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang, ``Quantum algorithms for sampling log-concave distributions and estimating normalizing constants'' Advances in Neural Information Processing Systems 35, 23205–23217 (2022). https://doi.org/10.5555/3600270.3601956 [37] Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, ``Quantum algorithm for estimating volumes of convex bodies'' ACM Transactions on Quantum Computing 4, 1–60 (2023). https://doi.org/10.1145/3588579 [38] Keisuke Fujiiand Shuhei Tamate ``Computational quantum-classical boundary of noisy commuting quantum circuits'' Scientific Reports 6, 25598 (2016). https://doi.org/10.1038/srep25598 [39] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd, ``Achieving quantum supremacy with sparse and noisy commuting quantum computations'' Quantum 1, 8 (2017). https://doi.org/10.22331/q-2017-04-25-8 [40] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert, ``Anticoncentration theorems for schemes showing a quantum speedup'' Quantum 2, 65 (2018). https://doi.org/10.22331/q-2018-05-22-65 [41] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd, ``Average-case complexity versus approximate simulation of commuting quantum computations'' Physical review letters 117, 080501 (2016). https://doi.org/10.1103/PhysRevLett.117.080501 [42] Joel Rajakumar, James D Watson, and Yi-Kai Liu, ``Polynomial-time classical simulation of noisy iqp circuits with constant depth'' Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 1037–1056 (2025). https://doi.org/10.1137/1.9781611978322.30 [43] Keisuke Fujii ``Quantum Computation with Topological Codes: from qubit to topological fault-tolerance'' Springer (2015). https://doi.org/10.1007/978-981-287-996-7 [44] Scott Aaronson ``Quantum computing, postselection, and probabilistic polynomial-time'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461, 3473–3482 (2005). https://doi.org/10.1098/rspa.2005.1546 [45] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin, ``Sample complexity of device-independently certified “quantum supremacy”'' Physical review letters 122, 210502 (2019). https://doi.org/10.1103/PhysRevLett.122.210502 [46] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven, ``Characterizing quantum supremacy in near-term devices'' Nature Physics 14, 595–600 (2018). https://doi.org/10.1038/s41567-018-0124-x [47] Dominik Hangleiter, Marcin Kalinowski, Dolev Bluvstein, Madelyn Cain, Nishad Maskara, Xun Gao, Aleksander Kubica, Mikhail D Lukin, and Michael J Gullans, ``Fault-Tolerant Compiling of Classically Hard Instantaneous Quantum Polynomial Circuits on Hypercubes'' PRX Quantum 6, 020338 (2025). https://doi.org/10.1103/PRXQuantum.6.020338 [48] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang, ``Learning quantum Hamiltonians at any temperature in polynomial time'' Proceedings of the 56th Annual ACM Symposium on Theory of Computing 1470–1477 (2024). https://doi.org/10.1145/3618260.3649619 [49] Fernando GSL Brandaoand Krysta M Svore ``Quantum speed-ups for solving semidefinite programs'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 415–426 (2017). https://doi.org/10.1109/FOCS.2017.45 [50] Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov, ``Interaction screening: Efficient and sample-optimal learning of Ising models'' Advances in neural information processing systems 29 (2016). https://doi.org/10.5555/3157382.3157389 [51] Adam Klivansand Raghu Meka ``Learning graphical models using multiplicative weights'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 343–354 (2017). https://doi.org/10.1109/FOCS.2017.39 [52] Daniel Gottesmanand Sandy Irani ``The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems'' 2009 50th Annual IEEE Symposium on Foundations of Computer Science 95–104 (2009). https://doi.org/10.1109/focs.2009.22 [53] Sevag Gharibian, Stephen Piddock, and Justin Yirka, ``Oracle Complexity Classes and Local Measurements on Physical Hamiltonians'' 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 154, 20:1–20:37 (2020). https://doi.org/10.4230/LIPIcs.STACS.2020.20 [54] James D. Watson, Johannes Bausch, and Sevag Gharibian, ``The Complexity of Translationally Invariant Problems Beyond Ground State Energies'' 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 254, 54:1–54:21 (2023). https://doi.org/10.4230/LIPIcs.STACS.2023.54 [55] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, ``Sample-efficient learning of interacting quantum systems'' Nature Physics 17, 931–935 (2021). https://doi.org/10.1038/s41567-021-01232-0 [56] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, ``Efficient learning of commuting Hamiltonians on lattices'' Electronic notes (2021). [57] Jeongwan Haah, Robin Kothari, and Ewin Tang, ``Optimal learning of quantum Hamiltonians from high-temperature Gibbs states'' 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 135–146 (2022). https://doi.org/10.1109/FOCS54457.2022.00020 [58] Álvaro M Alhambra ``Quantum many-body systems in thermal equilibrium'' PRX Quantum 4, 040201 (2023). https://doi.org/10.1103/PRXQuantum.4.040201 [59] Cambyse Rouzé, Daniel Stilck França, Emilio Onorati, and James D Watson, ``Efficient learning of ground and thermal states within phases of matter'' Nature Communications 15, 7755 (2024). https://doi.org/10.1038/s41467-024-51439-x [60] Cambyse Rouzéand Daniel Stilck França ``Learning quantum many-body systems from a few copies'' Quantum 8, 1319 (2024). https://doi.org/10.22331/q-2024-04-30-1319 [61] Luis Pedro García-Pintos, Kishor Bharti, Jacob Bringewatt, Hossein Dehghani, Adam Ehrenberg, Nicole Yunger Halpern, and Alexey V Gorshkov, ``Estimation of Hamiltonian parameters from thermal states'' Physical Review Letters 133, 040802 (2024). https://doi.org/10.1103/PhysRevLett.133.040802 [62] Dominik Hangleiterand Jens Eisert ``Computational advantage of quantum random sampling'' Rev. Mod. Phys. 95, 035001 (2023). https://doi.org/10.1103/RevModPhys.95.035001 [63] Dan Shepherdand Michael J. Bremner ``Temporally unstructured quantum computation'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413–1439 (2009). https://doi.org/10.1098/rspa.2008.0443 [64] Dan Shepherd ``Binary Matroids and Quantum Probability Distributions'' (2010). arXiv:1005.1744 [65] Daniel James Shepherd arXiv preprint arXiv:1005.1425 (2010). https://doi.org/10.48550/arXiv.10050 [66] David Grossand Dominik Hangleiter ``Secret extraction attacks against obfuscated IQP circuits'' (2023). https://doi.org/10.1103/PRXQuantum.6.020314Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-22 10:05:09: Could not fetch cited-by data for 10.22331/q-2026-01-22-1981 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-22 10:05:15: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractSampling from Gibbs states – states corresponding to system in thermal equilibrium – has recently been shown to be a task for which quantum computers are expected to achieve super-polynomial speed-up compared to classical computers, provided the locality of the Hamiltonian increases with the system size [1]. We extend these results to show that this quantum advantage still occurs for Gibbs states of Hamiltonians with O(1)-local interactions at constant temperature by showing classical hardness-of-sampling and demonstrating such Gibbs states can be prepared efficiently using a quantum computer. In particular, we show hardness-of-sampling is maintained even for 5-local Hamiltonians on a 3D lattice. We additionally show that the hardness-of-sampling is robust when we are only able to make imperfect measurements.Featured image: Schematic showing a phase transition in complexity of Gibbs sampling as temperature changes.Popular summaryDetermining the properties of Gibbs states — the state a system takes when it is in thermal equilibrium — is an important task in physics and computer science. Beyond its practical implications, a major open question has been "how quantum are thermal states for realistic physical systems?" Do thermal effects completely wash out all quantum properties of thermal states, or do quantum effects remain important in studying these states? In this work we show that at constant temperature (i.e., temperature which does not scale with the system size) there are local Hamiltonians for which quantum computers achieve a super-polynomial speedup relative to classical computers for the task of sampling bit strings from the Gibbs state.► BibTeX data@article{Rajakumar2026gibbssamplinggives, doi = {10.22331/q-2026-01-22-1981}, url = {https://doi.org/10.22331/q-2026-01-22-1981}, title = {Gibbs {S}ampling gives {Q}uantum {A}dvantage at {C}onstant {T}emperatures with {O}(1)-{L}ocal {H}amiltonians}, author = {Rajakumar, Joel and Watson, James D.}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1981}, month = jan, year = {2026} }► References [1] Thiago Bergamaschi, Chi-Fang Chen, and Yunchao Liu, ``Quantum computational advantage with constant-temperature Gibbs sampling'' 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1063-1085 (2024). https://doi.org/10.1109/FOCS61266.2024.00071 [2] Kristan Temme, Tobias J Osborne, Karl G Vollbrecht, David Poulin, and Frank Verstraete, ``Quantum metropolis sampling'' Nature 471, 87–90 (2011). https://doi.org/10.1038/nature09770 [3] Fernando GSL Brandaoand Michael J Kastoryano ``Finite correlation length implies efficient preparation of quantum thermal states'' Communications in Mathematical Physics 365, 1–16 (2019). https://doi.org/10.1007/s00220-018-3150-8 [4] Jonathan E Moussa ``Low-depth quantum metropolis algorithm'' arXiv preprint arXiv:1903.01451 (2019). https://doi.org/10.48550/arXiv.1903.01451 [5] Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O’Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brandao, and Garnet Kin-Lic Chan, ``Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution'' Nature Physics 16, 205–210 (2020). https://doi.org/10.1038/s41567-019-0704-4 [6] Evgeny Mozgunovand Daniel Lidar ``Completely positive master equation for arbitrary driving and small level spacing'' Quantum 4, 227 (2020). https://doi.org/10.22331/q-2020-02-06-227 [7] Chi-Fang Chenand Fernando GSL Brandão ``Fast thermalization from the eigenstate thermalization hypothesis'' arXiv preprint arXiv:2112.07646 (2021). https://doi.org/10.48550/arXiv.2112.07646 [8] Pawel Wocjanand Kristan Temme ``Szegedy walk unitaries for quantum maps'' Communications in Mathematical Physics 402, 3201–3231 (2023). https://doi.org/10.1007/s00220-023-04797-4 [9] Oles Shtankoand Ramis Movassagh ``Preparing thermal states on noiseless and noisy programmable quantum processors'' arXiv e-prints arXiv–2112 (2021). https://doi.org/10.48550/arXiv.2112.14688 [10] Daniel Zhang, Jan Lukas Bosse, and Toby Cubitt, ``Dissipative quantum Gibbs sampling'' arXiv preprint arXiv:2304.04526 (2023). https://doi.org/10.48550/arXiv.2304.04526 [11] Chi-Fang Chen, Michael J Kastoryano, Fernando GSL Brandão, and András Gilyén, ``Quantum thermal state preparation'' arXiv preprint arXiv:2303.18224 (2023). https://doi.org/10.48550/arXiv.2303.18224 [12] Jiaqing Jiangand Sandy Irani ``Quantum Metropolis Sampling via Weak Measurement'' arXiv preprint arXiv:2406.16023 (2024). https://doi.org/10.48550/arXiv.2406.16023 [13] Hongrui Chen, Bowen Li, Jianfeng Lu, and Lexing Ying, ``A randomized method for simulating Lindblad equations and thermal state preparation'' Quantum 9, 1917 (2025). https://doi.org/10.22331/q-2025-11-20-1917 [14] Sirui Lu, Mari Carmen Bañuls, and J Ignacio Cirac, ``Algorithms for quantum simulation at finite energies'' PRX Quantum 2, 020321 (2021). https://doi.org/10.1103/PRXQuantum.2.020321 [15] Alexander Schuckert, Annabelle Bohrdt, Eleanor Crane, and Michael Knap, ``Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics'' Physical Review B 107, L140410 (2023). https://doi.org/10.1103/PhysRevB.107.L140410 [16] Khaldoon Ghanem, Alexander Schuckert, and Henrik Dreyer, ``Robust extraction of thermal observables from state sampling and real-time dynamics on quantum computers'' Quantum 7, 1163 (2023). https://doi.org/10.22331/q-2023-11-03-1163 [17] Chi-Fang Chen, Michael J Kastoryano, and András Gilyén, ``An efficient and exact noncommutative quantum gibbs sampler'' arXiv preprint arXiv:2311.09207 (2023). https://doi.org/10.48550/arXiv.2311.09207 [18] András Gilyén, Chi-Fang Chen, Joao F Doriguello, and Michael J Kastoryano, ``Quantum generalizations of Glauber and Metropolis dynamics'' arXiv preprint arXiv:2405.20322 (2024). https://doi.org/10.48550/arXiv.2405.20322 [19] Daniel Stilck França ``Perfect sampling for quantum gibbs states'' Quantum Info. Comput. 18, 361–388 (2018). https://doi.org/10.26421/qic18.5-6-1 [20] Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar, ``Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems'' Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing 378–386 (2020). https://doi.org/10.1145/3357713.3384322 [21] Ryan L Mannand Tyler Helmuth ``Efficient algorithms for approximating quantum partition functions'' Journal of Mathematical Physics 62 (2021). https://doi.org/10.22331/q-2023-10-25-1155 [22] Chao Yinand Andrew Lucas ``Polynomial-time classical sampling of high-temperature quantum Gibbs states'' arXiv preprint arXiv:2305.18514 (2023). https://doi.org/10.48550/arXiv.2305.18514 [23] Cambyse Rouzé, Daniel Stilck França, and Álvaro M Alhambra, ``Efficient thermalization and universal quantum computing with quantum Gibbs samplers'' Proceedings of the 57th Annual ACM Symposium on Theory of Computing 1488–1495 (2025). https://doi.org/10.1145/3717823.3718268 [24] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang, ``High-temperature Gibbs states are unentangled and efficiently preparable'' 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS) 1027–1036 (2024). https://doi.org/10.1109/FOCS61266.2024.00068 [25] Allan Sly ``Computational transition at the uniqueness threshold'' 2010 IEEE 51st Annual Symposium on Foundations of Computer Science 287–296 (2010). https://doi.org/10.1109/FOCS.2010.34 [26] Isaac J Crosson, Dave Bacon, and Kenneth R Brown, ``Making classical ground-state spin computing fault-tolerant'' Physical Review E 82, 031106 (2010). https://doi.org/10.1103/PhysRevE.82.031106 [27] Allan Slyand Nike Sun ``The computational hardness of counting in two-spin models on d-regular graphs'' 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science 361–369 (2012). https://doi.org/10.1109/FOCS.2012.56 [28] Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan, ``Quantum Hamiltonian complexity in thermal equilibrium'' Nature Physics 18, 1367–1370 (2022). https://doi.org/10.1038/s41567-022-01742-5 [29] Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtěch Havlíček, and Guanyu Zhu, ``Quantum complexity of the Kronecker coefficients'' PRX Quantum 5, 010329 (2024). https://doi.org/10.1103/PRXQuantum.5.010329 [30] Fernando GSL Brandão ``Entanglement theory and the quantum simulation of many-body physics'' arXiv preprint arXiv:0810.0026 (2008). https://doi.org/10.48550/arXiv.0810.0026 [31] David Gamarnik, Bobak T. Kiani, and Alexander Zlokapa, ``Slow Mixing of Quantum Gibbs Samplers'' arXiv e-prints arXiv:2411.04300 (2024). https://doi.org/10.48550/arXiv.2411.04300 arXiv:2411.04300 [32] Joao Basso, Chi-Fang Chen, and Alexander M. Dalzell, ``Optimizing random local Hamiltonians by dissipation'' arXiv e-prints arXiv:2411.02578 (2024). https://doi.org/10.48550/arXiv.2411.02578 arXiv:2411.02578 [33] Chi-Fang Chen, Hsin-Yuan Huang, John Preskill, and Leo Zhou, ``Local minima in quantum systems'' Proceedings of the 56th Annual ACM Symposium on Theory of Computing 1323–1330 (2024). https://doi.org/10.1038/s41567-025-02781-4 [34] Štěpán Šmíd, Richard Meister, Mario Berta, and Roberto Bondesan, ``Rapid Mixing of Quantum Gibbs Samplers for Weakly-Interacting Quantum Systems'' arXiv e-prints arXiv:2510.04954 (2025). https://doi.org/10.48550/arXiv.2510.04954 arXiv:2510.04954 [35] Thiago Bergamaschiand Chi-Fang Chen ``Quantum Spin Chains Thermalize at All Temperatures'' arXiv e-prints arXiv:2510.08533 (2025). https://doi.org/10.48550/arXiv.2510.08533 arXiv:2510.08533 [36] Andrew M Childs, Tongyang Li, Jin-Peng Liu, Chunhao Wang, and Ruizhe Zhang, ``Quantum algorithms for sampling log-concave distributions and estimating normalizing constants'' Advances in Neural Information Processing Systems 35, 23205–23217 (2022). https://doi.org/10.5555/3600270.3601956 [37] Shouvanik Chakrabarti, Andrew M Childs, Shih-Han Hung, Tongyang Li, Chunhao Wang, and Xiaodi Wu, ``Quantum algorithm for estimating volumes of convex bodies'' ACM Transactions on Quantum Computing 4, 1–60 (2023). https://doi.org/10.1145/3588579 [38] Keisuke Fujiiand Shuhei Tamate ``Computational quantum-classical boundary of noisy commuting quantum circuits'' Scientific Reports 6, 25598 (2016). https://doi.org/10.1038/srep25598 [39] Michael J. Bremner, Ashley Montanaro, and Dan J. Shepherd, ``Achieving quantum supremacy with sparse and noisy commuting quantum computations'' Quantum 1, 8 (2017). https://doi.org/10.22331/q-2017-04-25-8 [40] Dominik Hangleiter, Juan Bermejo-Vega, Martin Schwarz, and Jens Eisert, ``Anticoncentration theorems for schemes showing a quantum speedup'' Quantum 2, 65 (2018). https://doi.org/10.22331/q-2018-05-22-65 [41] Michael J Bremner, Ashley Montanaro, and Dan J Shepherd, ``Average-case complexity versus approximate simulation of commuting quantum computations'' Physical review letters 117, 080501 (2016). https://doi.org/10.1103/PhysRevLett.117.080501 [42] Joel Rajakumar, James D Watson, and Yi-Kai Liu, ``Polynomial-time classical simulation of noisy iqp circuits with constant depth'' Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) 1037–1056 (2025). https://doi.org/10.1137/1.9781611978322.30 [43] Keisuke Fujii ``Quantum Computation with Topological Codes: from qubit to topological fault-tolerance'' Springer (2015). https://doi.org/10.1007/978-981-287-996-7 [44] Scott Aaronson ``Quantum computing, postselection, and probabilistic polynomial-time'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461, 3473–3482 (2005). https://doi.org/10.1098/rspa.2005.1546 [45] Dominik Hangleiter, Martin Kliesch, Jens Eisert, and Christian Gogolin, ``Sample complexity of device-independently certified “quantum supremacy”'' Physical review letters 122, 210502 (2019). https://doi.org/10.1103/PhysRevLett.122.210502 [46] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven, ``Characterizing quantum supremacy in near-term devices'' Nature Physics 14, 595–600 (2018). https://doi.org/10.1038/s41567-018-0124-x [47] Dominik Hangleiter, Marcin Kalinowski, Dolev Bluvstein, Madelyn Cain, Nishad Maskara, Xun Gao, Aleksander Kubica, Mikhail D Lukin, and Michael J Gullans, ``Fault-Tolerant Compiling of Classically Hard Instantaneous Quantum Polynomial Circuits on Hypercubes'' PRX Quantum 6, 020338 (2025). https://doi.org/10.1103/PRXQuantum.6.020338 [48] Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang, ``Learning quantum Hamiltonians at any temperature in polynomial time'' Proceedings of the 56th Annual ACM Symposium on Theory of Computing 1470–1477 (2024). https://doi.org/10.1145/3618260.3649619 [49] Fernando GSL Brandaoand Krysta M Svore ``Quantum speed-ups for solving semidefinite programs'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 415–426 (2017). https://doi.org/10.1109/FOCS.2017.45 [50] Marc Vuffray, Sidhant Misra, Andrey Lokhov, and Michael Chertkov, ``Interaction screening: Efficient and sample-optimal learning of Ising models'' Advances in neural information processing systems 29 (2016). https://doi.org/10.5555/3157382.3157389 [51] Adam Klivansand Raghu Meka ``Learning graphical models using multiplicative weights'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 343–354 (2017). https://doi.org/10.1109/FOCS.2017.39 [52] Daniel Gottesmanand Sandy Irani ``The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems'' 2009 50th Annual IEEE Symposium on Foundations of Computer Science 95–104 (2009). https://doi.org/10.1109/focs.2009.22 [53] Sevag Gharibian, Stephen Piddock, and Justin Yirka, ``Oracle Complexity Classes and Local Measurements on Physical Hamiltonians'' 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) 154, 20:1–20:37 (2020). https://doi.org/10.4230/LIPIcs.STACS.2020.20 [54] James D. Watson, Johannes Bausch, and Sevag Gharibian, ``The Complexity of Translationally Invariant Problems Beyond Ground State Energies'' 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 254, 54:1–54:21 (2023). https://doi.org/10.4230/LIPIcs.STACS.2023.54 [55] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, ``Sample-efficient learning of interacting quantum systems'' Nature Physics 17, 931–935 (2021). https://doi.org/10.1038/s41567-021-01232-0 [56] Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara, and Mehdi Soleimanifar, ``Efficient learning of commuting Hamiltonians on lattices'' Electronic notes (2021). [57] Jeongwan Haah, Robin Kothari, and Ewin Tang, ``Optimal learning of quantum Hamiltonians from high-temperature Gibbs states'' 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 135–146 (2022). https://doi.org/10.1109/FOCS54457.2022.00020 [58] Álvaro M Alhambra ``Quantum many-body systems in thermal equilibrium'' PRX Quantum 4, 040201 (2023). https://doi.org/10.1103/PRXQuantum.4.040201 [59] Cambyse Rouzé, Daniel Stilck França, Emilio Onorati, and James D Watson, ``Efficient learning of ground and thermal states within phases of matter'' Nature Communications 15, 7755 (2024). https://doi.org/10.1038/s41467-024-51439-x [60] Cambyse Rouzéand Daniel Stilck França ``Learning quantum many-body systems from a few copies'' Quantum 8, 1319 (2024). https://doi.org/10.22331/q-2024-04-30-1319 [61] Luis Pedro García-Pintos, Kishor Bharti, Jacob Bringewatt, Hossein Dehghani, Adam Ehrenberg, Nicole Yunger Halpern, and Alexey V Gorshkov, ``Estimation of Hamiltonian parameters from thermal states'' Physical Review Letters 133, 040802 (2024). https://doi.org/10.1103/PhysRevLett.133.040802 [62] Dominik Hangleiterand Jens Eisert ``Computational advantage of quantum random sampling'' Rev. Mod. Phys. 95, 035001 (2023). https://doi.org/10.1103/RevModPhys.95.035001 [63] Dan Shepherdand Michael J. Bremner ``Temporally unstructured quantum computation'' Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1413–1439 (2009). https://doi.org/10.1098/rspa.2008.0443 [64] Dan Shepherd ``Binary Matroids and Quantum Probability Distributions'' (2010). arXiv:1005.1744 [65] Daniel James Shepherd arXiv preprint arXiv:1005.1425 (2010). https://doi.org/10.48550/arXiv.10050 [66] David Grossand Dominik Hangleiter ``Secret extraction attacks against obfuscated IQP circuits'' (2023). https://doi.org/10.1103/PRXQuantum.6.020314Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-22 10:05:09: Could not fetch cited-by data for 10.22331/q-2026-01-22-1981 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-22 10:05:15: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.