{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T02:08:12Z","timestamp":1780711692813,"version":"3.54.1"},"reference-count":96,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T00:00:00Z","timestamp":1665014400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000015","name":"Department of energy","doi-asserted-by":"crossref","award":["89233218CNA000001"],"award-info":[{"award-number":["89233218CNA000001"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Laboratory Directed Research and Development program of Los Alamos National Laboratory","award":["20190065DR"],"award-info":[{"award-number":["20190065DR"]}]},{"name":"Office of Advanced Scientific Computing Research","award":["89233218CNA000001"],"award-info":[{"award-number":["89233218CNA000001"]}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"Fluctuation theorems provide a correspondence between properties of quantum systems in thermal equilibrium and a work distribution arising in a non-equilibrium process that connects two quantum systems with HamiltoniansH<\/mml:mi>0<\/mml:mn><\/mml:msub><\/mml:math>andH<\/mml:mi>1<\/mml:mn><\/mml:msub>=<\/mml:mo>H<\/mml:mi>0<\/mml:mn><\/mml:msub>+<\/mml:mo>V<\/mml:mi><\/mml:math>. Building upon these theorems, we present a quantum algorithm to prepare a purification of the thermal state ofH<\/mml:mi>1<\/mml:mn><\/mml:msub><\/mml:math>at inverse temperature&#x03B2;<\/mml:mi>&#x2265;<\/mml:mo>0<\/mml:mn><\/mml:math>starting from a purification of the thermal state ofH<\/mml:mi>0<\/mml:mn><\/mml:msub><\/mml:math>. The complexity of the quantum algorithm, given by the number of uses of certain unitaries, isO<\/mml:mi>&#x007E;<\/mml:mo><\/mml:mover><\/mml:mrow>(<\/mml:mo>e<\/mml:mi>&#x03B2;<\/mml:mi>(<\/mml:mo>&#x0394;<\/mml:mi>A<\/mml:mi>&#x2212;<\/mml:mo>w<\/mml:mi>l<\/mml:mi><\/mml:msub>)<\/mml:mo>\/<\/mml:mo><\/mml:mrow>2<\/mml:mn><\/mml:mrow><\/mml:msup>)<\/mml:mo><\/mml:math>, where&#x0394;<\/mml:mi>A<\/mml:mi><\/mml:math>is the free-energy difference betweenH<\/mml:mi>1<\/mml:mn><\/mml:msub><\/mml:math>andH<\/mml:mi>0<\/mml:mn><\/mml:msub>,<\/mml:mo><\/mml:math>andw<\/mml:mi>l<\/mml:mi><\/mml:msub><\/mml:math>is a work cutoff that depends on the properties of the work distribution and the approximation error&#x03F5;<\/mml:mi>&#x003E;<\/mml:mo>0<\/mml:mn><\/mml:math>. If the non-equilibrium process is trivial, this complexity is exponential in&#x03B2;<\/mml:mi>&#x2016;<\/mml:mo>V<\/mml:mi>&#x2016;<\/mml:mo><\/mml:math>, where&#x2016;<\/mml:mo>V<\/mml:mi>&#x2016;<\/mml:mo><\/mml:math>is the spectral norm ofV<\/mml:mi><\/mml:math>. This represents a significant improvement of prior quantum algorithms that have complexity exponential in&#x03B2;<\/mml:mi>&#x2016;<\/mml:mo>H<\/mml:mi>1<\/mml:mn><\/mml:msub>&#x2016;<\/mml:mo><\/mml:math>in the regime where&#x2016;<\/mml:mo>V<\/mml:mi>&#x2016;<\/mml:mo>&#x226A;<\/mml:mo>&#x2016;<\/mml:mo>H<\/mml:mi>1<\/mml:mn><\/mml:msub>&#x2016;<\/mml:mo><\/mml:math>. The dependence of the complexity in&#x03F5;<\/mml:mi><\/mml:math>varies according to the structure of the quantum systems. It can be exponential in1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:math>in general, but we show it to be sublinear in1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:math>ifH<\/mml:mi>0<\/mml:mn><\/mml:msub><\/mml:math>andH<\/mml:mi>1<\/mml:mn><\/mml:msub><\/mml:math>commute, or polynomial in1<\/mml:mn>\/<\/mml:mo><\/mml:mrow>&#x03F5;<\/mml:mi><\/mml:math>ifH<\/mml:mi>0<\/mml:mn><\/mml:msub><\/mml:math>andH<\/mml:mi>1<\/mml:mn><\/mml:msub><\/mml:math>are local spin systems. The possibility of applying a unitary that drives the system out of equilibrium allows one to increase the value ofw<\/mml:mi>l<\/mml:mi><\/mml:msub><\/mml:math>and improve the complexity even further. To this end, we analyze the complexity for preparing the thermal state of the transverse field Ising model using different non-equilibrium unitary processes and see significant complexity improvements.<\/jats:p>","DOI":"10.22331\/q-2022-10-06-825","type":"journal-article","created":{"date-parts":[[2022,10,6]],"date-time":"2022-10-06T11:19:57Z","timestamp":1665055197000},"page":"825","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":30,"title":["Quantum algorithms from fluctuation theorems: Thermal-state preparation"],"prefix":"10.22331","volume":"6","author":[{"given":"Zoe","family":"Holmes","sequence":"first","affiliation":[{"name":"Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gopikrishnan","family":"Muraleedharan","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rolando D.","family":"Somma","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yigit","family":"Subasi","sequence":"additional","affiliation":[{"name":"Computer, Computational, and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Burak","family":"\u015eahino\u011flu","sequence":"additional","affiliation":[{"name":"Theoretical Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"9598","published-online":{"date-parts":[[2022,10,6]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller. Equations of state calculations by fast computing machines. Journal of Chemical Physics, 21:1087\u20131092, 1953. doi:10.1063\/1.1699114.","DOI":"10.1063\/1.1699114"},{"key":"1","unstructured":"L.D. Landau and E.M Lifshitz. Statistical physics: Part I. Butterworth-Heinemann, Oxford, 1951."},{"key":"2","doi-asserted-by":"publisher","unstructured":"M. Suzuki. Quantum Monte Carlo Methods in Equilibrium and Nonequilibrium Systems. Springer Ser. Solid-State Sci. 74, Springer, 1987. doi:10.1007\/978-3-642-83154-6.","DOI":"10.1007\/978-3-642-83154-6"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Daniel A. Lidar and Ofer Biham. Simulating ising spin glasses on a quantum computer. Phys. Rev. E, 56:3661, 1997. doi:10.1103\/PhysRevE.56.3661.","DOI":"10.1103\/PhysRevE.56.3661"},{"key":"4","doi-asserted-by":"publisher","unstructured":"B.M. Terhal and D.P. DiVincenzo. Problem of equilibration and the computation of correlation functions on a quantum computer. Phys. Rev. A, 61:022301, 2000. doi:10.1103\/PhysRevA.61.022301.","DOI":"10.1103\/PhysRevA.61.022301"},{"key":"5","doi-asserted-by":"publisher","unstructured":"R. D. Somma, S. Boixo, H. Barnum, and E. Knill. Quantum simulations of classical annealing processes. Phys. Rev. Lett., 101:130504, 2008. doi:10.1103\/PhysRevLett.101.130504.","DOI":"10.1103\/PhysRevLett.101.130504"},{"key":"6","doi-asserted-by":"publisher","unstructured":"K. Temme, T.J. Osborne, K. Vollbrecht, D. Poulin, and F. Verstraete. Quantum metropolis sampling. Nature, 471:87\u201390, 2011. doi:10.1038\/nature09770.","DOI":"10.1038\/nature09770"},{"key":"7","doi-asserted-by":"publisher","unstructured":"C. Chipot and A. Pohorille. Free energy calculations: Theory and applications in chemistry and biology. Springer Verlag, New York, 2007. doi:10.1007\/978-3-540-38448-9.","DOI":"10.1007\/978-3-540-38448-9"},{"key":"8","doi-asserted-by":"publisher","unstructured":"T.A. van der Straaten, G. Kathawala, A. Trellakis, R.S. Eisenberg, and U. Ravaioli. Biomoca\u2014 a boltzmann transport monte carlo model for ion channel simulation. Molecular Simulation, 31:151\u2013171, 2005. doi:10.1080\/08927020412331308700.","DOI":"10.1080\/08927020412331308700"},{"key":"9","doi-asserted-by":"publisher","unstructured":"D. P. Kroese and J. C. C. Chan. Statistical Modeling and Computation. Springer, New York, 2014. doi:10.1007\/978-1-4614-8775-3.","DOI":"10.1007\/978-1-4614-8775-3"},{"key":"10","doi-asserted-by":"publisher","unstructured":"S. Kirkpatrick, C.D. Gelatt Jr., and M.P. Vecchi. Optimization by simulated annealing. Science, 220:671\u2013680, 1983. doi:10.1126\/science.220.4598.671.","DOI":"10.1126\/science.220.4598.671"},{"key":"11","doi-asserted-by":"publisher","unstructured":"L. Lov\u00e1sz. Randomized algorithms in combinatorial optimization. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 20:153\u2013179, 1995. doi:10.1090\/dimacs\/020.","DOI":"10.1090\/dimacs\/020"},{"key":"12","doi-asserted-by":"crossref","unstructured":"M.E.J. Newman and G.T. Barkema. Monte Carlo Methods in Statistical Physics. Oxford University Press, Oxford, 1998.","DOI":"10.1093\/oso\/9780198517962.001.0001"},{"key":"13","doi-asserted-by":"crossref","unstructured":"M.P. Nightingale and C.J. Umrigar. Quantum Monte Carlo Methods in Physics and Chemistry. Springer, Netherlands, 1999.","DOI":"10.1007\/978-94-011-4792-7"},{"key":"14","doi-asserted-by":"publisher","unstructured":"E.Y. Loh, J.E. Gubernatis, R.T. Scalettar, S.R. White, D.J. Scalapino, and R.L. Sugar. Sign problem in the numerical simulation of many-electron systems. Phys. Rev. B, 41:9301\u20139307, 1990. doi:10.1103\/PhysRevB.41.9301.","DOI":"10.1103\/PhysRevB.41.9301"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Matthias Troyer and Uwe-Jens Wiese. Computational complexity and fundamental limitations to fermionic quantum monte carlo simulations. Phys. Rev. Lett., 94:170201, 2005. doi:10.1103\/PhysRevLett.94.170201.","DOI":"10.1103\/PhysRevLett.94.170201"},{"key":"16","doi-asserted-by":"publisher","unstructured":"David Poulin and Pawel Wocjan. Sampling from the thermal quantum gibbs state and evaluating partition functions with a quantum computer. Phys. Rev. Lett., 103:220502, 2009. doi:10.1103\/PhysRevLett.103.220502.","DOI":"10.1103\/PhysRevLett.103.220502"},{"key":"17","doi-asserted-by":"publisher","unstructured":"C.F. Chiang and P. Wocjan. Quantum algorithm for preparing thermal gibbs states-detailed analysis. In Quantum Cryptography and Computing, pages 138\u2013147, 2010. doi:10.48550\/arXiv.1001.1130.","DOI":"10.48550\/arXiv.1001.1130"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Ersen Bilgin and Sergio Boixo. Preparing thermal states of quantum systems by dimension reduction. Phys. Rev. Lett., 105:170405, 2010. doi:10.1103\/PhysRevLett.105.170405.","DOI":"10.1103\/PhysRevLett.105.170405"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Michael J. Kastoryano and Fernando G. S. L. Brand\u00e3o. Quantum gibbs samplers: the commuting case. Comm. Math. Phys., 344:915, 2016. doi:10.48550\/arXiv.1409.3435.","DOI":"10.48550\/arXiv.1409.3435"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Anirban Narayan Chowdhury and Rolando D. Somma. Quantum algorithms for gibbs sampling and hitting-time estimation. Quant. Inf. Comp., 17(1\u20132):41\u201364, 2017. doi:10.48550\/arXiv.1603.02940.","DOI":"10.48550\/arXiv.1603.02940"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Tomotaka Kuwahara, Kohtaro Kato, and Fernando G. S. L. Brand\u00e3o. Clustering of conditional mutual information for quantum gibbs states above a threshold temperature. Phys. Rev. Lett., 124:220601, 2020. doi:10.1103\/PhysRevLett.124.220601.","DOI":"10.1103\/PhysRevLett.124.220601"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Mario Szegedy. Quantum speed-up of markov chain based algorithms. In Proceedings of the 45th Annual IEEE Symposium on FOCS., pages 32\u201341. IEEE, 2004. doi:10.1109\/FOCS.2004.53.","DOI":"10.1109\/FOCS.2004.53"},{"key":"23","doi-asserted-by":"crossref","unstructured":"F. G. S. L. Brand\u00e3o and K. M. Svore. Quantum speed-ups for solving semidefinite programs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 415\u2013426, 2017.","DOI":"10.1109\/FOCS.2017.45"},{"key":"24","doi-asserted-by":"publisher","unstructured":"J. Van Apeldoorn, A. Gily\u00e9n, S. Gribling, and R. de Wolf. Quantum sdp-solvers: Better upper and lower bounds. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 403\u2013414, 2017. doi:10.48550\/arXiv.1609.05537.","DOI":"10.48550\/arXiv.1609.05537"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Seth Lloyd. Universal quantum simulators. Science, 273:1073\u20131078, 1996. doi:10.1126\/science.273.5278.1073.","DOI":"10.1126\/science.273.5278.1073"},{"key":"26","doi-asserted-by":"publisher","unstructured":"R. D. Somma, G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme. Simulating physical phenomena by quantum networks. Phys. Rev. A, 65:042323, 2002. doi:10.1103\/PhysRevA.65.042323.","DOI":"10.1103\/PhysRevA.65.042323"},{"key":"27","doi-asserted-by":"publisher","unstructured":"R. D. Somma, G. Ortiz, E. Knill, and J. E. Gubernatis. Quantum simulations of physics problems. Int. J. Quant. Inf., 1:189, 2003. doi:10.1117\/12.487249.","DOI":"10.1117\/12.487249"},{"key":"28","doi-asserted-by":"publisher","unstructured":"D.W. Berry, G. Ahokas, R. Cleve, and B.C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Comm. Math. Phys., 270:359, 2007. doi:10.1007\/s00220-006-0150-x.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"29","doi-asserted-by":"publisher","unstructured":"N. Wiebe, D. Berry, P. Hoyer, and B.C. Sanders. Higher order decompositions of ordered operator exponentials. J. Phys. A: Math. Theor., 43:065203, 2010. doi:10.1088\/1751-8113\/43\/6\/065203.","DOI":"10.1088\/1751-8113\/43\/6\/065203"},{"key":"30","doi-asserted-by":"publisher","unstructured":"A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Information and Computation, 12:901\u2013924, 2012. doi:10.48550\/arXiv.1202.5822.","DOI":"10.48550\/arXiv.1202.5822"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett., 114:090502, 2015. doi:10.1103\/PhysRevLett.114.090502.","DOI":"10.1103\/PhysRevLett.114.090502"},{"key":"32","doi-asserted-by":"publisher","unstructured":"G.H. Low and I.L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118:010501, 2017. doi:10.1103\/PhysRevLett.118.010501.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"33","doi-asserted-by":"publisher","unstructured":"U. Wolff. Critical slowing down. Nuclear Phys. B, 17:93\u2013102, 1990. doi:10.1016\/0920-5632(90)90224-I.","DOI":"10.1016\/0920-5632(90)90224-I"},{"key":"34","doi-asserted-by":"publisher","unstructured":"A.Y. Kitaev, A.H. Shen, and M.N Vyalyi. Classical and Quantum Computation. American Mathematical Society, 2002. URL: http:\/\/doi.org\/10.1090\/gsm\/047, doi:10.1090\/gsm\/047.","DOI":"10.1090\/gsm\/047"},{"key":"35","doi-asserted-by":"publisher","unstructured":"C. Jarzynski. Equilibrium free-energy differences from nonequilibrium measurements: A master-equation approach. Phys. Rev. E, 56:5018\u20135035, 1997. doi:10.1103\/PhysRevE.56.5018.","DOI":"10.1103\/PhysRevE.56.5018"},{"key":"36","doi-asserted-by":"publisher","unstructured":"C. Jarzynski. Nonequilibrium equality for free energy differences. Phys. Rev. Lett., 78:2690\u20132693, 1997. doi:10.1103\/PhysRevLett.78.2690.","DOI":"10.1103\/PhysRevLett.78.2690"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Christopher Jarzynski. Equalities and inequalities: Irreversibility and the second law of thermodynamics at the nanoscale. Annual Review of Condensed Matter Physics, 2(1):329\u2013351, 2011. arXiv:https:\/\/doi.org\/10.1146\/annurev-conmatphys-062910-140506, doi:10.1146\/annurev-conmatphys-062910-140506.","DOI":"10.1146\/annurev-conmatphys-062910-140506"},{"key":"38","doi-asserted-by":"publisher","unstructured":"Gavin E. Crooks. Entropy production fluctuation theorem and the nonequilibrium work relation for free energy differences. Phys. Rev. E, 60:2721\u20132726, 1999. doi:10.1103\/PhysRevE.60.2721.","DOI":"10.1103\/PhysRevE.60.2721"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Gavin E. Crooks. Path-ensemble averages in systems driven far from equilibrium. Phys. Rev. E, 61:2361\u20132366, 2000. doi:10.1103\/PhysRevE.61.2361.","DOI":"10.1103\/PhysRevE.61.2361"},{"key":"40","doi-asserted-by":"publisher","unstructured":"Augusto J. Roncaglia, Federico Cerisola, and Juan Pablo Paz. Work measurement as a generalized quantum measurement. Phys. Rev. Lett., 113:250601, 2014. doi:10.1103\/PhysRevLett.113.250601.","DOI":"10.1103\/PhysRevLett.113.250601"},{"key":"41","doi-asserted-by":"publisher","unstructured":"Lindsay Bassman, Katherine Klymko, Diyi Liu, Norman M Tubman, and Wibe A de Jong. Computing free energies with fluctuation relations on quantum computers. arXiv preprint arXiv:2103.09846, 2021. doi:10.48550\/arXiv.2103.09846.","DOI":"10.48550\/arXiv.2103.09846"},{"key":"42","doi-asserted-by":"crossref","unstructured":"S. Barnett. Quantum information, volume 16. Oxford University Press, 2009.","DOI":"10.1093\/oso\/9780198527626.003.0011"},{"key":"43","doi-asserted-by":"publisher","unstructured":"M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, Cambridge, 2001. doi:10.1017\/CBO9780511976667.","DOI":"10.1017\/CBO9780511976667"},{"key":"44","doi-asserted-by":"publisher","unstructured":"Emanuel Knill, Gerardo Ortiz, and Rolando D. Somma. Optimal quantum measurements of expectation values of observables. Phys. Rev. A, 75:012328, 2007. doi:10.1103\/PhysRevA.75.012328.","DOI":"10.1103\/PhysRevA.75.012328"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. doi:10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"46","doi-asserted-by":"publisher","unstructured":"Christopher Jarzynski. Rare events and the convergence of exponentially averaged work values. Phys. Rev. E, 73:046105, 2006. doi:10.1103\/PhysRevE.73.046105.","DOI":"10.1103\/PhysRevE.73.046105"},{"key":"47","doi-asserted-by":"publisher","unstructured":"Yu Tong, Dong An, Nathan Wiebe, and Lin Lin. Fast inversion, preconditioned quantum linear system solvers, fast green's-function computation, and fast evaluation of matrix functions. Phys. Rev. A, 104:032422, Sep 2021. doi:10.1103\/PhysRevA.104.032422.","DOI":"10.1103\/PhysRevA.104.032422"},{"key":"48","doi-asserted-by":"publisher","unstructured":"A. Kitaev. Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph\/9511026, 1995. doi:10.48550\/arXiv.quant-ph\/9511026.","DOI":"10.48550\/arXiv.quant-ph\/9511026"},{"key":"49","doi-asserted-by":"publisher","unstructured":"R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proc. R. Soc. Lond. A, 454:339\u2013354, 1998. doi:10.1098\/rspa.1998.0164.","DOI":"10.1098\/rspa.1998.0164"},{"key":"50","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter H\u00f8yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum computation and information, volume 305 of Contemporary Mathematics, pages 53\u201374. AMS, 2002. doi:10.1090\/conm\/305\/05215.","DOI":"10.1090\/conm\/305\/05215"},{"key":"51","doi-asserted-by":"publisher","unstructured":"Maris Ozols, Martin Roetteler, and J\u00e9r\u00e9mie Roland. Quantum rejection sampling. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, page 290\u2013308, New York, NY, USA, 2012. Association for Computing Machinery. doi:10.1145\/2090236.2090261.","DOI":"10.1145\/2090236.2090261"},{"key":"52","doi-asserted-by":"publisher","unstructured":"David Poulin and Pawel Wocjan. Preparing ground states of quantum many-body systems on a quantum computer. Phys. Rev. Lett., 102:130503, 2009. doi:10.1103\/PhysRevLett.102.130503.","DOI":"10.1103\/PhysRevLett.102.130503"},{"key":"53","doi-asserted-by":"publisher","unstructured":"S. Boixo, E. Knill, and R.D. Somma. Fast quantum algorithms for traversing paths of eigenstates. arXiv:1005.3034, 2010. doi:10.48550\/arXiv.1005.3034.","DOI":"10.48550\/arXiv.1005.3034"},{"key":"54","doi-asserted-by":"publisher","unstructured":"Yimin Ge, Jordi Tura, and J. Ignacio Cirac. Faster ground state preparation and high-precision ground energy estimation with fewer qubits. Journal of Mathematical Physics, 60(2):022202, 2019. arXiv:https:\/\/doi.org\/10.1063\/1.5027484, doi:10.1063\/1.5027484.","DOI":"10.1063\/1.5027484"},{"key":"55","doi-asserted-by":"publisher","unstructured":"Lin Lin and Yu Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3:010318, 2022. doi:10.1103\/PRXQuantum.3.010318.","DOI":"10.1103\/PRXQuantum.3.010318"},{"key":"56","doi-asserted-by":"publisher","unstructured":"Chi-Fang Chen and Fernando GSL Brand\u00e3o. Fast thermalization from the eigenstate thermalization hypothesis. arXiv preprint arXiv:2112.07646, 2021. doi:10.48550\/arXiv.2112.07646.","DOI":"10.48550\/arXiv.2112.07646"},{"key":"57","doi-asserted-by":"publisher","unstructured":"Oles Shtanko and Ramis Movassagh. Algorithms for gibbs state preparation on noiseless and noisy random quantum circuits. arXiv preprint arXiv:2112.14688, 2021. doi:10.48550\/arXiv.2112.14688.","DOI":"10.48550\/arXiv.2112.14688"},{"key":"58","doi-asserted-by":"publisher","unstructured":"Marcos Rigol, Vanja Dunjko, and Maxim Olshanii. Thermalization and its mechanism for generic isolated quantum systems. Nature, 452(7189):854\u2013858, 2008. doi:10.1038\/nature06838.","DOI":"10.1038\/nature06838"},{"key":"59","doi-asserted-by":"publisher","unstructured":"Mario Motta, Chong Sun, Adrian TK Tan, Matthew J O\u2019Rourke, Erika Ye, Austin J Minnich, Fernando GSL Brand\u00e3o, and Garnet Kin Chan. Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution. Nature Physics, 16(2):205\u2013210, 2020. doi:10.1038\/s41567-019-0704-4.","DOI":"10.1038\/s41567-019-0704-4"},{"key":"60","doi-asserted-by":"publisher","unstructured":"R Sagastizabal, SP Premaratne, BA Klaver, MA Rol, V Neg\u0131\u0302rneac, MS Moreira, X Zou, S Johri, N Muthusubramanian, M Beekman, et al. Variational preparation of finite-temperature states on a quantum computer. npj Quantum Information, 7(1):1\u20137, 2021. doi:10.1038\/s41534-021-00468-1.","DOI":"10.1038\/s41534-021-00468-1"},{"key":"61","doi-asserted-by":"publisher","unstructured":"John Martyn and Brian Swingle. Product spectrum ansatz and the simplicity of thermal states. Phys. Rev. A, 100(3):032107, 2019. doi:10.1103\/PhysRevA.100.032107.","DOI":"10.1103\/PhysRevA.100.032107"},{"key":"62","doi-asserted-by":"publisher","unstructured":"Guillaume Verdon, Jacob Marks, Sasha Nanda, Stefan Leichenauer, and Jack Hidary. Quantum hamiltonian-based models and the variational quantum thermalizer algorithm. arXiv preprint arXiv:1910.02071, 2019. doi:10.48550\/arXiv.1910.02071.","DOI":"10.48550\/arXiv.1910.02071"},{"key":"63","doi-asserted-by":"publisher","unstructured":"Anirban N Chowdhury, Guang Hao Low, and Nathan Wiebe. A variational quantum algorithm for preparing quantum gibbs states. arXiv preprint arXiv:2002.00055, 2020. doi:10.48550\/arXiv.2002.00055.","DOI":"10.48550\/arXiv.2002.00055"},{"key":"64","doi-asserted-by":"publisher","unstructured":"Youle Wang, Guangxi Li, and Xin Wang. Variational quantum gibbs state preparation with a truncated taylor series. Phys. Rev. Applied, 16:054035, 2021. doi:10.1103\/PhysRevApplied.16.054035.","DOI":"10.1103\/PhysRevApplied.16.054035"},{"key":"65","doi-asserted-by":"publisher","unstructured":"Jonathan Foldager, Arthur Pesah, and Lars Kai Hansen. Noise-assisted variational quantum thermalization. Scientific reports, 12(1):1\u201311, 2022. doi:10.1038\/s41598-022-07296-z.","DOI":"10.1038\/s41598-022-07296-z"},{"key":"66","doi-asserted-by":"publisher","unstructured":"Jarrod R McClean, Sergio Boixo, Vadim N Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature Communications, 9(1):1\u20136, 2018. doi:10.1038\/s41467-018-07090-4.","DOI":"10.1038\/s41467-018-07090-4"},{"key":"67","doi-asserted-by":"publisher","unstructured":"M Cerezo, Akira Sone, Tyler Volkoff, Lukasz Cincio, and Patrick J Coles. Cost function dependent barren plateaus in shallow parametrized quantum circuits. Nature communications, 12(1):1\u201312, 2021. URL: https:\/\/www.doi.org\/10.1038\/s41467-021-21728-w, doi:10.1038\/s41467-021-21728-w.","DOI":"10.1038\/s41467-021-21728-w"},{"key":"68","doi-asserted-by":"publisher","unstructured":"Zo\u00eb Holmes, Andrew Arrasmith, Bin Yan, Patrick J Coles, Andreas Albrecht, and Andrew T Sornborger. Barren plateaus preclude learning scramblers. Phys. Rev. Lett., 126(19):190501, 2021. doi:10.1103\/PhysRevLett.126.190501.","DOI":"10.1103\/PhysRevLett.126.190501"},{"key":"69","doi-asserted-by":"publisher","unstructured":"Zo\u00eb Holmes, Kunal Sharma, M. Cerezo, and Patrick J Coles. Connecting ansatz expressibility to gradient magnitudes and barren plateaus. Phys. Rev. X Quantum, 3:010313, 2022. doi:10.1103\/PRXQuantum.3.010313.","DOI":"10.1103\/PRXQuantum.3.010313"},{"key":"70","doi-asserted-by":"publisher","unstructured":"Carlos Ortiz Marrero, M\u00e1ria Kieferov\u00e1, and Nathan Wiebe. Entanglement-induced barren plateaus. PRX Quantum, 2:040316, Oct 2021. doi:10.1103\/PRXQuantum.2.040316.","DOI":"10.1103\/PRXQuantum.2.040316"},{"key":"71","doi-asserted-by":"publisher","unstructured":"Lennart Bittel and Martin Kliesch. Training variational quantum algorithms is np-hard. Phys. Rev. Lett., 127:120502, 2021. doi:10.1103\/PhysRevLett.127.120502.","DOI":"10.1103\/PhysRevLett.127.120502"},{"key":"72","doi-asserted-by":"publisher","unstructured":"Michele Campisi, Peter H\u00e4nggi, and Peter Talkner. Colloquium: Quantum fluctuation relations: Foundations and applications. Rev. Mod. Phys., 83:771\u2013791, 2011. doi:10.1103\/RevModPhys.83.771.","DOI":"10.1103\/RevModPhys.83.771"},{"key":"73","doi-asserted-by":"publisher","unstructured":"H. Tasaki. Jarzynski Relations for Quantum Systems and Some Applications. eprint arXiv:cond-mat\/0009244, 2000. arXiv:cond-mat\/0009244, doi:10.48550\/arXiv.cond-mat\/0009244.","DOI":"10.48550\/arXiv.cond-mat\/0009244"},{"key":"74","doi-asserted-by":"publisher","unstructured":"J. Kurchan. A Quantum Fluctuation Theorem. eprint arXiv:cond-mat\/0007360, 2000. arXiv:cond-mat\/0007360, doi:10.48550\/arXiv.cond-mat\/0007360.","DOI":"10.48550\/arXiv.cond-mat\/0007360"},{"key":"75","doi-asserted-by":"publisher","unstructured":"Peter Talkner and Peter H\u00e4nggi. The tasaki\u2013crooks quantum fluctuation theorem. Journal of Physics A: Mathematical and Theoretical, 40(26):F569, 2007. doi:10.1088\/1751-8113\/40\/26\/F08.","DOI":"10.1088\/1751-8113\/40\/26\/F08"},{"key":"76","doi-asserted-by":"publisher","unstructured":"A. Chowdhury, Y. Suba\u015fi, and R.D. Somma. Improved implementation of reflection operators. arXiv:1803.02466, 2018. doi:10.48550\/arXiv.1803.02466.","DOI":"10.48550\/arXiv.1803.02466"},{"key":"77","doi-asserted-by":"publisher","unstructured":"Andrea Solfanelli, Alessandro Santini, and Michele Campisi. Experimental verification of fluctuation relations with a quantum computer. PRX Quantum, 2:030353, 2021. doi:10.1103\/PRXQuantum.2.030353.","DOI":"10.1103\/PRXQuantum.2.030353"},{"key":"78","doi-asserted-by":"crossref","unstructured":"Phillip Kaye, Raymond Laflamme, and Michele Mosca. An introduction to quantum computing. Oxford University Press, 2007.","DOI":"10.1093\/oso\/9780198570004.001.0001"},{"key":"79","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proc. 46th ACM Symp. Theor. Comp., pages 283\u2013292, 2014. doi:10.1145\/2591796.2591854.","DOI":"10.1145\/2591796.2591854"},{"key":"80","doi-asserted-by":"publisher","unstructured":"Nandou Lu and David A. Kofke. Accuracy of free-energy perturbation calculations in molecular simulation. i. modeling. The Journal of Chemical Physics, 114(17):7303\u20137311, 2001. arXiv:https:\/\/doi.org\/10.1063\/1.1359181, doi:10.1063\/1.1359181.","DOI":"10.1063\/1.1359181"},{"key":"81","doi-asserted-by":"publisher","unstructured":"Nicole Yunger Halpern and Christopher Jarzynski. Number of trials required to estimate a free-energy difference, using fluctuation relations. Phys. Rev. E, 93:052144, 2016. doi:10.1103\/PhysRevE.93.052144.","DOI":"10.1103\/PhysRevE.93.052144"},{"key":"82","doi-asserted-by":"publisher","unstructured":"Anirban Narayan Chowdhury, Rolando D. Somma, and Yigit Subasi. Computing partition functions in the one-clean-qubit model. Phys. Rev. A, 103:032422, 2021. doi:10.1103\/PhysRevA.103.032422.","DOI":"10.1103\/PhysRevA.103.032422"},{"key":"83","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs, Robin Kothari, and Rolando D. Somma. Quantum linear systems algorithm with exponentially improved dependence on precision. SIAM J. Comp., 46:1920, 2017. doi:10.1137\/16M1087072.","DOI":"10.1137\/16M1087072"},{"key":"84","doi-asserted-by":"publisher","unstructured":"G.H. Low, T.J. Yoder, and I.L. Chuang. Methodology of resonant equiangular composite quantum gates. Phys. Rev. X, 6:041067, 2016. doi:10.1103\/PhysRevX.6.041067.","DOI":"10.1103\/PhysRevX.6.041067"},{"key":"85","doi-asserted-by":"publisher","unstructured":"Andr\u00e1s Gily\u00e9n, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics. In Proc. of the 51st Annual ACM SIGACT Symp. Theor. Comp., STOC 2019, page 193\u2013204, New York, NY, USA, 2019. Association for Computing Machinery. doi:10.1145\/3313276.3316366.","DOI":"10.1145\/3313276.3316366"},{"key":"86","doi-asserted-by":"publisher","unstructured":"Jeongwan Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. doi:10.22331\/q-2019-10-07-190.","DOI":"10.22331\/q-2019-10-07-190"},{"key":"87","doi-asserted-by":"publisher","unstructured":"Yulong Dong, Xiang Meng, K. Birgitta Whaley, and Lin Lin. Efficient phase-factor evaluation in quantum signal processing. Phys. Rev. A, 103:042419, 2021. doi:10.1103\/PhysRevA.103.042419.","DOI":"10.1103\/PhysRevA.103.042419"},{"key":"88","doi-asserted-by":"publisher","unstructured":"Andrew Pohorille, Christopher Jarzynski, and Christophe Chipot. Good practices in free-energy calculations. The Journal of Physical Chemistry B, 114(32):10235\u201310253, 2010. doi:10.1021\/jp102971x.","DOI":"10.1021\/jp102971x"},{"key":"89","doi-asserted-by":"publisher","unstructured":"E. Lieb, T. Schultz, and D. Mattis. Two soluble models of an antiferromagnetic chain. Ann. Phys., 16:406, 1961. doi:10.1016\/0003-4916(61)90115-4.","DOI":"10.1016\/0003-4916(61)90115-4"},{"key":"90","doi-asserted-by":"publisher","unstructured":"Pierre Pfeuty. The one dimensional ising model with a transverse field. Ann. Phys., 57:79\u201390, 1970. doi:10.1016\/0003-4916(70)90270-8.","DOI":"10.1016\/0003-4916(70)90270-8"},{"key":"91","doi-asserted-by":"publisher","unstructured":"Burak \u015eahino\u011flu and Rolando D. Somma. Hamiltonian simulation in the low energy subspace. npj Quant. Inf., 7:119, 2021. doi:10.1038\/s41534-021-00451-w.","DOI":"10.1038\/s41534-021-00451-w"},{"key":"92","doi-asserted-by":"publisher","unstructured":"Rolando D. Somma and Sergio Boixo. Spectral gap amplification. SIAM J. Comp, 42:593\u2013610, 2013. doi:10.1137\/120871997.","DOI":"10.1137\/120871997"},{"key":"93","doi-asserted-by":"publisher","unstructured":"J. Hubbard. Calculation of partition functions. Phys. Rev. Lett., 3:77, 1959. doi:10.1103\/PhysRevLett.3.77.","DOI":"10.1103\/PhysRevLett.3.77"},{"key":"94","unstructured":"A method to implement such unitaries that uses the technique of spectral gap amplification is described in Ref. SB13. It requires $H_0$ and $H_1$ to be presented in a particular form such as linear combination of unitaries or linear combinations of projectors."},{"key":"95","doi-asserted-by":"publisher","unstructured":"Itai Arad, Tomotaka Kuwahara, and Zeph Landau. Connecting global and local energy distributions in quantum spin models on a lattice. Journal of Statistical Mechanics: Theory and Experiment, 2016(3):033301, 2016. doi:10.1088\/1742-5468\/2016\/03\/033301.","DOI":"10.1088\/1742-5468\/2016\/03\/033301"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-10-06-825\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T14:35:42Z","timestamp":1701182142000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2022-10-06-825\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,6]]},"references-count":96,"URL":"https:\/\/doi.org\/10.22331\/q-2022-10-06-825","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,6]]},"article-number":"825"}}