{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,2]],"date-time":"2026-08-02T02:59:06Z","timestamp":1785639546969,"version":"3.56.0"},"reference-count":50,"publisher":"IEEE","license":[{"start":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T00:00:00Z","timestamp":1729987200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,10,27]],"date-time":"2024-10-27T00:00:00Z","timestamp":1729987200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2146752,2311733"],"award-info":[{"award-number":["2146752,2311733"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,10,27]]},"DOI":"10.1109\/focs61266.2024.00071","type":"proceedings-article","created":{"date-parts":[[2024,11,29]],"date-time":"2024-11-29T18:48:52Z","timestamp":1732906132000},"page":"1063-1085","source":"Crossref","is-referenced-by-count":13,"title":["Quantum Computational Advantage with Constant-Temperature Gibbs Sampling"],"prefix":"10.1109","author":[{"given":"Thiago","family":"Bergamaschi","sequence":"first","affiliation":[{"name":"University of California, Berkeley,Department of EECS,Berkeley,CA,USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chi-Fang","family":"Chen","sequence":"additional","affiliation":[{"name":"California Institute of Technology,Department of Physics,Pasadena,CA,USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yunchao","family":"Liu","sequence":"additional","affiliation":[{"name":"University of California, Berkeley,Department of EECS,Berkeley,CA,USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1007\/bf01608389"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-02-06-227"},{"key":"ref3","volume-title":"Gibbs sampling gives quantum advantage at constant temperatures with o(1)-local hamiltonians","author":"Rajakumar","year":"2024"},{"issue":"4","key":"ref4","doi-asserted-by":"crossref","first-page":"040502","DOI":"10.1103\/PhysRevLett.118.040502","article-title":"Quantum supremacy for simulating a translation-invariant ising spin model","volume":"118","author":"Gao","year":"2016","journal-title":"Physical review letters"},{"key":"ref5","article-title":"Architectures for quantum simulation showing a quantum speedup","volume-title":"arXiv: Quantum Physics","author":"Bermejo-Vega","year":"2017"},{"key":"ref6","author":"Yin","year":"2023","journal-title":"Polynomial-time classical sampling of high-temperature quantum gibbs states"},{"key":"ref7","author":"Bakshi","year":"2024","journal-title":"High-temperature gibbs states are unentangled and efficiently preparable"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539705447323"},{"key":"ref10","author":"Chen","year":"2023","journal-title":"Local minima in quantum systems"},{"key":"ref11","volume":"47","author":"Kitaev","year":"2002","journal-title":"Classical and Quantum Computation, ser. Graduate studies in mathematics"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.22331\/q-2023-10-10-1132"},{"key":"ref13","author":"Chen","year":"2023","journal-title":"Quantum thermal state preparation"},{"key":"ref14","volume-title":"An efficient and exact noncommutative quantum gibbs sampler","author":"Chen","year":"2023"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1063\/1.4804995"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1103\/physrevlett.130.060401"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-023-04869-5"},{"key":"ref18","author":"Capel","year":"2021","journal-title":"The modified logarithmic sobolev inequality for quantum spin systems: classical and commuting nearest neighbour interactions"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1103\/revmodphys.95.035001"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.22331\/q-2017-04-25-8"},{"key":"ref21","volume-title":"Polynomial-time classical simulation of noisy iqp circuits with constant depth","author":"Rajakumar","year":"2024"},{"key":"ref22","doi-asserted-by":"crossref","first-page":"033444","DOI":"10.1103\/PhysRevResearch.2.033444","article-title":"Fault-tolerant quantum speedup from constant depth quantum circuits","volume":"2","author":"Mezher","year":"2020","journal-title":"Phys. Rev. Res."},{"key":"ref23","doi-asserted-by":"crossref","first-page":"1337","DOI":"10.22331\/q-2024-05-06-1337","article-title":"Robust sparse IQP sampling in constant depth","volume":"8","author":"Paletta","year":"2024","journal-title":"Quantum"},{"issue":"4","key":"ref24","doi-asserted-by":"crossref","first-page":"1207","DOI":"10.1137\/S0097539799359385","article-title":"Fault-tolerant quantum computation with constant error rate","volume":"38","author":"Aharonov","year":"2008","journal-title":"SIAM Journal on Computing"},{"issue":"10","key":"ref25","doi-asserted-by":"crossref","first-page":"1040","DOI":"10.1038\/s41567-020-0948-z","article-title":"Quantum advantage with noisy shallow circuits","volume":"16","author":"Bravyi","year":"2020","journal-title":"Nature Physics"},{"issue":"1","key":"ref26","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00220-018-3150-8","article-title":"Finite correlation length implies efficient preparation of quantum thermal states","volume":"365","author":"Brandao","year":"2019","journal-title":"Communications in Mathematical Physics"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"022316","DOI":"10.1103\/PhysRevA.71.022316","article-title":"Universal quantum computation with ideal clifford gates and noisy ancillas","volume":"71","author":"Bravyi","year":"2005","journal-title":"Phys. Rev. A"},{"key":"ref28","first-page":"517","article-title":"Universal blind quantum computation","volume-title":"2009 50th Annual IEEE Symposium on Foundations of Computer Science","author":"Broadbent","year":"2008"},{"key":"ref29","doi-asserted-by":"crossref","first-page":"3201","DOI":"10.1007\/s00220-023-04797-4","article-title":"Szegedy walk unitaries for quantum maps","volume":"402","author":"Wocjan","year":"2021","journal-title":"Communications in Mathematical Physics"},{"key":"ref30","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1007\/s00220-017-2950-6","article-title":"Mixing properties of stochastic quantum hamiltonians","volume":"355","author":"Onorati","year":"2016","journal-title":"Communications in Mathematical Physics"},{"issue":"12","key":"ref31","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.107.120501","article-title":"Dissipative quantum church-turing theorem","volume":"107","author":"Kliesch","year":"2011","journal-title":"Physical Review Letters"},{"key":"ref32","first-page":"459","article-title":"Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy","volume-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences","volume":"467","author":"Bremner","year":"2010"},{"key":"ref33","article-title":"Anticoncentration theorems for schemes showing a quantum speedup","volume-title":"arXiv: Quantum Physics","author":"Hangleiter","year":"2017"},{"key":"ref34","doi-asserted-by":"crossref","first-page":"465","DOI":"10.22331\/q-2021-06-02-465","article-title":"Quantum advantage from energy measurements of many-body quantum systems","volume":"5","author":"Novo","year":"2019","journal-title":"Quantum"},{"key":"ref35","article-title":"The computational complexity of linear optics","volume":"abs\/1011.3245","author":"Aaronson","year":"2010","journal-title":"ArXiv"},{"issue":"8","key":"ref36","doi-asserted-by":"crossref","first-page":"080501","DOI":"10.1103\/PhysRevLett.117.080501","article-title":"Average-case complexity versus approximate simulation of commuting quantum computations","volume":"117","author":"Bremner","year":"2015","journal-title":"Physical review letters"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s00205-022-01785-1"},{"key":"ref38","doi-asserted-by":"crossref","DOI":"10.1063\/1.4941136","article-title":"Entropy production of doubly stochastic quantum channels","volume-title":"arXiv: Quantum Physics","author":"Muller-Hermes"},{"key":"ref39","article-title":"Relative entropy convergence for depolarizing channels","volume-title":"arXiv: Quantum Physics","author":"Muller-Hermes","year":"2015"},{"key":"ref40","doi-asserted-by":"crossref","DOI":"10.1088\/1751-8121\/aae4cf","article-title":"Quantum conditional relative entropy and quasi-factorization of the relative entropy","volume":"51","author":"Capel","year":"2018","journal-title":"Journal of Physics A: Mathematical and Theoretical"},{"key":"ref41","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1007\/s00220-020-03750-z","article-title":"Quantum reverse hypercontractivity: Its tensorization and application to strong converses","volume":"376","author":"Beigi","year":"2018","journal-title":"Communications in Mathematical Physics"},{"key":"ref42","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/BF02571350","article-title":"On certain properties of the relative entropy of states of operator algebras","volume":"206","author":"Petz","year":"1991","journal-title":"Mathematische Zeitschrift"},{"key":"ref43","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/s00220-015-2466-x","article-title":"Quantum conditional mutual information and approximate markov chains","volume":"340","author":"Fawzi","year":"2014","journal-title":"Communications in Mathematical Physics"},{"key":"ref44","article-title":"Universal recovery from a decrease of quantum relative entropy","volume":"abs\/1509.07127","author":"Junge","year":"2015","journal-title":"ArXiv"},{"key":"ref45","article-title":"Quantum markov networks and commuting hamiltonians","volume-title":"arXiv: Quantum Physics","author":"Brown","year":"2012"},{"key":"ref46","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/s00220-013-1762-6","article-title":"Stability of frustration-free hamiltonians","volume":"322","author":"Michalakis","year":"2011","journal-title":"Communications in Mathematical Physics"},{"key":"ref47","doi-asserted-by":"crossref","first-page":"201102","DOI":"10.1103\/PhysRevB.76.201102","article-title":"Quantum belief propagation: An algorithm for thermal quantum systems","volume":"76","author":"Hastings","year":"2007","journal-title":"Physical Review B"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.128.220502"},{"key":"ref50","first-page":"3473","article-title":"Quantum computing, postselection, and probabilistic polynomial-time","volume-title":"Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences","volume":"461","author":"Aaronson","year":"2004"}],"event":{"name":"2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)","location":"Chicago, IL, USA","start":{"date-parts":[[2024,10,27]]},"end":{"date-parts":[[2024,10,30]]}},"container-title":["2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)"],"original-title":[],"link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/xplorestaging.ieee.org\/ielx8\/10755992\/10756014\/10756075.pdf?arnumber=10756075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,30]],"date-time":"2024-11-30T05:52:13Z","timestamp":1732945933000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/ieeexplore.ieee.org\/document\/10756075\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,27]]},"references-count":50,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1109\/focs61266.2024.00071","relation":{},"subject":[],"published":{"date-parts":[[2024,10,27]]}}}