{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T23:48:30Z","timestamp":1781912910632,"version":"3.54.5"},"reference-count":77,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T00:00:00Z","timestamp":1683504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Algorithms Teams program"},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"crossref","award":["W911NF-16-1-0349"],"award-info":[{"award-number":["W911NF-16-1-0349"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Canadian Institute for Advanced Research, and the National Science Foundation","award":["CCF-1813814"],"award-info":[{"award-number":["CCF-1813814"]}]},{"name":"U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Quantum Testbed Pathfinder program","award":["DE-SC0019040"],"award-info":[{"award-number":["DE-SC0019040"]}]},{"name":"IBM Ph.D. Fellowship and an NSF QISE-NET Triplet Award","award":["DMR-1747426"],"award-info":[{"award-number":["DMR-1747426"]}]},{"name":"Scott Aaronson\u2019s Vannevar Bush Faculty Fellowship from the U.S. Department of Defense"},{"name":"National Science Foundation","award":["CCF-1755800 and CCF-1816695"],"award-info":[{"award-number":["CCF-1755800 and CCF-1816695"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            Estimating the volume of a convex body is a central problem in convex geometry and can be viewed as a continuous version of counting. We present a quantum algorithm that estimates the volume of an\n            <jats:italic>n<\/jats:italic>\n            -dimensional convex body within multiplicative error \u03b5 using\n            <jats:italic>\n              O\u0303(n\n              <jats:sup>3<\/jats:sup>\n              + n\n              <jats:sup>2.5<\/jats:sup>\n              \/\u03b5\n            <\/jats:italic>\n            ) queries to a membership oracle and\n            <jats:italic>\n              O\u0303(n\n              <jats:sup>5<\/jats:sup>\n              +n\n              <jats:sup>4.5<\/jats:sup>\n              \/\u03b5)\n            <\/jats:italic>\n            additional arithmetic operations. For comparison, the best known classical algorithm uses\n            <jats:italic>\n              O\u0303(n\n              <jats:sup>3.5<\/jats:sup>\n              +n\n              <jats:sup>3<\/jats:sup>\n              \/\u03b5\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:italic>\n            queries and\n            <jats:italic>\n              O\u0303(n\n              <jats:sup>5.5<\/jats:sup>\n              +n\n              <jats:sup>5<\/jats:sup>\n              \/\u03b5\n              <jats:sup>2<\/jats:sup>\n              )\n            <\/jats:italic>\n            additional arithmetic operations. To the best of our knowledge, this is the first quantum speedup for volume estimation. Our algorithm is based on a refined framework for speeding up simulated annealing algorithms that might be of independent interest. This framework applies in the setting of \u201cChebyshev cooling,\u201d where the solution is expressed as a telescoping product of ratios, each having bounded variance. We develop several novel techniques when implementing our framework, including a theory of continuous-space quantum walks with rigorous bounds on discretization error. To complement our quantum algorithms, we also prove that volume estimation requires\n            <jats:italic>\u03a9 (\u221a n+1\/\u03b5)<\/jats:italic>\n            quantum membership queries, which rules out the possibility of exponential quantum speedup in\n            <jats:italic>n<\/jats:italic>\n            and shows optimality of our algorithm in 1\/\u03b5 up to poly-logarithmic factors.\n          <\/jats:p>","DOI":"10.1145\/3588579","type":"journal-article","created":{"date-parts":[[2023,5,8]],"date-time":"2023-05-08T09:03:12Z","timestamp":1683536592000},"page":"1-60","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Quantum Algorithm\u00a0for Estimating Volumes of Convex Bodies"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9159-4881","authenticated-orcid":false,"given":"Shouvanik","family":"Chakrabarti","sequence":"first","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9903-837X","authenticated-orcid":false,"given":"Andrew M.","family":"Childs","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3410-7466","authenticated-orcid":false,"given":"Shih-Han","family":"Hung","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0338-413X","authenticated-orcid":false,"given":"Tongyang","family":"Li","sequence":"additional","affiliation":[{"name":"Peking University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9983-5774","authenticated-orcid":false,"given":"Chunhao","family":"Wang","sequence":"additional","affiliation":[{"name":"Pennsylvania State University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8877-9802","authenticated-orcid":false,"given":"Xiaodi","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,8]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380758"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.72.062304"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380757"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-01-13-220"},{"key":"e_1_3_3_7_2","article-title":"Quantum fast-forwarding: Markov chains and graph property testing","author":"Apers Simon","year":"2019","unstructured":"Simon Apers and Alain Sarlette. 2019. Quantum fast-forwarding: Markov chains and graph property testing. Quant. Info. Comput. (2019). arXiv:1804.02321.","journal-title":"Quant. Info. Comput."},{"key":"e_1_3_3_8_2","first-page":"156","volume-title":"Proceedings of the 23nd Annual ACM Symposium on Theory of Computing","author":"Applegate David","year":"1991","unstructured":"David Applegate and Ravi Kannan. 1991. Sampling and integration of near log-concave functions. In Proceedings of the 23nd Annual ACM Symposium on Theory of Computing. 156\u2013163."},{"key":"e_1_3_3_9_2","first-page":"112","volume-title":"Proceedings of the IEEE International Conference on Quantum Computing and Engineering","author":"Arunachalam Srinivasan","year":"2021","unstructured":"Srinivasan Arunachalam, Vojtech Havlicek, Giacomo Nannicini, Kristan Temme, and Pawel Wocjan. 2021. Simpler (classical) and faster (quantum) algorithms for gibbs partition functions. In Proceedings of the IEEE International Conference on Quantum Computing and Engineering. IEEE, 112\u2013122. arXiv:2009.11270."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187886"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Sergio Boixo and Rolando D. Somma. 2015. Quantum algorithms for simulated annealing. Retrieved from https:\/\/arxiv.org\/abs\/1512.03806.","DOI":"10.1007\/978-3-642-27848-8_774-1"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/646252.686013"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-01-13-221"},{"issue":"2","key":"e_1_3_3_16_2","doi-asserted-by":"crossref","first-page":"022423","DOI":"10.1103\/PhysRevA.102.022423","article-title":"Analog quantum algorithms for the mixing of Markov chains","volume":"102","author":"Chakraborty Shantanav","year":"2020","unstructured":"Shantanav Chakraborty, Kyle Luh, and J\u00e9r\u00e9mie Roland. 2020. Analog quantum algorithms for the mixing of Markov chains. Phys. Rev. A 102, 2 (2020), 022423. arXiv:1904.11895.","journal-title":"Phys. Rev. A"},{"issue":"1","key":"e_1_3_3_17_2","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/s00039-021-00558-4","article-title":"An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture","volume":"31","author":"Chen Yuansi","year":"2021","unstructured":"Yuansi Chen. 2021. An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture. Geom. Funct. Anal. 31, 1 (2021), 34\u201361. arXiv:2011.13661.","journal-title":"Geom. Funct. Anal."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780552"},{"key":"e_1_3_3_19_2","unstructured":"Andrew M. Childs Tongyang Li Jin-Peng Liu Chunhao Wang and Ruizhe Zhang. 2022. Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants. Retrieved from https:\/\/arxiv.org\/abs\/2210.06539."},{"key":"e_1_3_3_20_2","unstructured":"Arjan Cornelissen and Yassine Hamoudi. 2022. A Sublinear-Time Quantum Algorithm for Approximating Partition Functions. Retrieved from https:\/\/arxiv.org\/abs\/2207.08643."},{"key":"e_1_3_3_21_2","first-page":"1215","volume-title":"Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Cousins Ben","year":"2014","unstructured":"Ben Cousins and Santosh Vempala. 2014. A cubic algorithm for computing gaussian volume. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. 1215\u20131228. arXiv:1306.5829."},{"key":"e_1_3_3_22_2","first-page":"539","volume-title":"Proceedings of the 47th Annual ACM Symposium on Theory of Computing","author":"Cousins Ben","year":"2015","unstructured":"Ben Cousins and Santosh Vempala. 2015. Bypassing KLS: Gaussian cooling and an \\(O^{*}(n^3)\\) volume algorithm. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing. 539\u2013548. arXiv:1409.6011."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011679.2011685"},{"key":"e_1_3_3_24_2","first-page":"123","article-title":"Computing the volume of convex bodies: A case where randomness provably helps","volume":"44","author":"Dyer Martin","year":"1991","unstructured":"Martin Dyer and Alan Frieze. 1991. Computing the volume of convex bodies: A case where randomness provably helps. Prob. Combinat. Appl. 44 (1991), 123\u2013170.","journal-title":"Prob. Combinat. Appl."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187701"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.58.915"},{"issue":"1","key":"e_1_3_3_29_2","first-page":"14","article-title":"Log-sobolev inequalities and sampling from log-concave distributions","volume":"9","author":"Frieze Alan","year":"1999","unstructured":"Alan Frieze and Ravi Kannan. 1999. Log-sobolev inequalities and sampling from log-concave distributions. Ann. Appl. Probabil. 9, 1 (1999), 14\u201326.","journal-title":"Ann. Appl. Probabil."},{"key":"e_1_3_3_30_2","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"Gr\u00f6tschel Martin","year":"2012","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 2012. Geometric Algorithms and Combinatorial Optimization. Vol. 2. Springer Science & Business Media."},{"key":"e_1_3_3_31_2","unstructured":"Lov Grover and Terry Rudolph. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. Retrieved from https:\/\/arxiv.org\/abs\/quant-ph\/0208112."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.79.325"},{"key":"e_1_3_3_33_2","unstructured":"Lov K. Grover. 2005. A different kind of quantum search. Retrieved from https:\/\/arxiv.org\/abs\/quant-ph\/0503205."},{"key":"e_1_3_3_34_2","first-page":"69:1\u201369:16","volume-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","author":"Hamoudi Yassine","year":"2019","unstructured":"Yassine Hamoudi and Fr\u00e9d\u00e9ric Magniez. 2019. Quantum chebyshev\u2019s inequality and applications. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming. 69:1\u201369:16. arXiv:1807.06456."},{"key":"e_1_3_3_35_2","first-page":"193","volume-title":"Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Harrow Aram W.","year":"2020","unstructured":"Aram W. Harrow and Annie Y. Wei. 2020. Adaptive quantum simulated annealing for bayesian inference and estimating partition functions. In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms. 193\u2013212. arXiv:1907.09965."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/QCE49297.2020.00030"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451018"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1060.0194"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/261619.261620"},{"key":"e_1_3_3_40_2","first-page":"216","article-title":"On the complexity of computing the volume of a polytope","volume":"3","author":"Khachiyan Leonid G.","year":"1988","unstructured":"Leonid G. Khachiyan. 1988. On the complexity of computing the volume of a polytope. Izvestia Akad. Nauk SSSR, Eng. Cybernet. 3 (1988), 216\u2013217.","journal-title":"Izvestia Akad. Nauk SSSR, Eng. Cybernet."},{"issue":"3","key":"e_1_3_3_41_2","first-page":"199","article-title":"The problem of computing the volume of polytopes is NP-hard","volume":"44","author":"Khachiyan Leonid G.","year":"1989","unstructured":"Leonid G. Khachiyan. 1989. The problem of computing the volume of polytopes is NP-hard. Uspekhi Mat. Nauk 44, 3 (1989), 199\u2013200.","journal-title":"Uspekhi Mat. Nauk"},{"key":"e_1_3_3_42_2","first-page":"1292","volume-title":"Proceedings of the 31st Conference on Learning Theory","author":"Lee Yin Tat","year":"2018","unstructured":"Yin Tat Lee, Aaron Sidford, and Santosh S. Vempala. 2018. Efficient convex optimization with membership oracles. In Proceedings of the 31st Conference on Learning Theory. 1292\u20131294. arXiv:1706.07357."},{"key":"e_1_3_3_43_2","first-page":"1049","volume-title":"Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science","author":"Lee Yin Tat","year":"2015","unstructured":"Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. 2015. A faster cutting plane method and its implications for combinatorial and convex optimization. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science. 1049\u20131065. arXiv:1508.04874."},{"key":"e_1_3_3_44_2","first-page":"998","volume-title":"Proceedings of the 58th Annual Symposium on Foundations of Computer Science","author":"Lee Yin Tat","year":"2017","unstructured":"Yin Tat Lee and Santosh S. Vempala. 2017. Eldan\u2019s stochastic localization and the KLS hyperplane conjecture: An improved lower bound for expansion. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science. 998\u20131007. arXiv:1612.01507."},{"issue":"1","key":"e_1_3_3_45_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4310\/CDM.2017.v2017.n1.a1","article-title":"The Kannan-Lov\u00e1sz-Simonovits conjecture","volume":"2017","author":"Lee Yin Tat","year":"2017","unstructured":"Yin Tat Lee and Santosh S. Vempala. 2017. The Kannan-Lov\u00e1sz-Simonovits conjecture. Curr. Dev. Math. 2017, 1 (2017), 1\u201336. arXiv:1807.03465.","journal-title":"Curr. Dev. Math."},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188774"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1090\/mbk\/107"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2883306"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050099"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89553"},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040402"},{"key":"e_1_3_3_52_2","first-page":"57","volume-title":"Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2006","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Santosh Vempala. 2006. Fast algorithms for logconcave functions: Sampling, rounding, integration and optimization. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science. 57\u201368."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970544727X"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.004"},{"issue":"3","key":"e_1_3_3_55_2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/rsa.20135","article-title":"The geometry of logconcave functions and sampling algorithms","volume":"30","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"2007","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz and Santosh Vempala. 2007. The geometry of logconcave functions and sampling algorithms. Random Struct. Algor. 30, 3 (2007), 307\u2013358.","journal-title":"Random Struct. Algor."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/090745854"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177692644"},{"issue":"2181","key":"e_1_3_3_58_2","doi-asserted-by":"crossref","first-page":"20150301","DOI":"10.1098\/rspa.2015.0301","article-title":"Quantum speedup of Monte Carlo methods","volume":"471","author":"Montanaro Ashley","year":"2015","unstructured":"Ashley Montanaro. 2015. Quantum speedup of Monte Carlo methods. Proc. Roy. Soc. A 471, 2181 (2015), 20150301. arXiv:1504.06987.","journal-title":"Proc. Roy. Soc. A"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/377939.377946"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301349"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2018-11-09-105"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.06.004"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/3\/072"},{"issue":"4","key":"e_1_3_3_64_2","doi-asserted-by":"crossref","first-page":"042306","DOI":"10.1103\/PhysRevA.76.042306","article-title":"Quantum speedup of classical mixing processes","volume":"76","author":"Richter Peter C.","year":"2007","unstructured":"Peter C. Richter. 2007. Quantum speedup of classical mixing processes. Phys. Rev. A 76, 4 (2007), 042306. arXiv:quant-ph\/0609204.","journal-title":"Phys. Rev. A"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1006\/jfan.1998.3384"},{"key":"e_1_3_3_66_2","volume-title":"Modern Quantum Mechanics","author":"Sakurai Jun John","year":"2014","unstructured":"Jun John Sakurai and Jim Napolitano. 2014. Modern Quantum Mechanics. Pearson Harlow."},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.6.1296"},{"key":"e_1_3_3_68_2","unstructured":"Rolando D. Somma Sergio Boixo and Howard Barnum. 2007. Quantum simulated annealing. Retrieved from https:\/\/arxiv.org\/abs\/0712.1008."},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.101.130504"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516520"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.53"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature09770"},{"key":"e_1_3_3_73_2","series-title":"Mathematical Sciences Research Institute Publications","first-page":"573","volume-title":"Combinatorial and Computational Geometry","author":"Vempala Santosh","year":"2005","unstructured":"Santosh Vempala. 2005. Geometric random walks: A survey. In Combinatorial and Computational Geometry. Mathematical Sciences Research Institute Publications, Vol. 52. MSRI, 573\u2013612."},{"key":"e_1_3_3_74_2","volume-title":"Computational Problems Related to Open Quantum Systems","author":"Wang Chunhao","year":"2018","unstructured":"Chunhao Wang. 2018. Computational Problems Related to Open Quantum Systems. Ph. D. Dissertation. University of Waterloo."},{"issue":"4","key":"e_1_3_3_75_2","doi-asserted-by":"crossref","first-page":"042336","DOI":"10.1103\/PhysRevA.78.042336","article-title":"Speedup via quantum sampling","volume":"78","author":"Wocjan Pawel","year":"2008","unstructured":"Pawel Wocjan and Anura Abeyesinghe. 2008. Speedup via quantum sampling. Phys. Rev. A 78, 4 (2008), 042336. arXiv:0804.4259.","journal-title":"Phys. Rev. A"},{"issue":"2","key":"e_1_3_3_76_2","doi-asserted-by":"crossref","first-page":"022340","DOI":"10.1103\/PhysRevA.80.022340","article-title":"Quantum algorithm for approximating partition functions","volume":"80","author":"Wocjan Pawel","year":"2009","unstructured":"Pawel Wocjan, Chen-Fu Chiang, Daniel Nagaj, and Anura Abeyesinghe. 2009. Quantum algorithm for approximating partition functions. Phys. Rev. A 80, 2 (2009), 022340. arXiv:0811.0596.","journal-title":"Phys. Rev. A"},{"key":"e_1_3_3_77_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.113.210501"},{"key":"e_1_3_3_78_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1111758109"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588579","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588579","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:13Z","timestamp":1750178833000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588579"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,8]]},"references-count":77,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3588579"],"URL":"https:\/\/doi.org\/10.1145\/3588579","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"value":"2643-6809","type":"print"},{"value":"2643-6817","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,8]]},"assertion":[{"value":"2022-04-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-08","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}