{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T23:00:09Z","timestamp":1774393209793,"version":"3.50.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Quantum Works"},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-09-1-0569"],"award-info":[{"award-number":["W911NF-09-1-0569"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ARO\/NSA","award":["W911NF-09-1-0569"],"award-info":[{"award-number":["W911NF-09-1-0569"]}]},{"name":"Belgian ARC project COPHYMA"},{"name":"Mandats de Retour of the Politique Scientifique F\u00e9d\u00e9rale Belge"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:p>Rejection sampling is a well-known method to sample from a target distribution, given the ability to sample from a given distribution. The method has been first formalized by von Neumann [1951] and has many applications in classical computing. We define a quantum analogue of rejection sampling: given a black box producing a coherent superposition of (possibly unknown) quantum states with some amplitudes, the problem is to prepare a coherent superposition of the same states, albeit with different target amplitudes. The main result of this article is a tight characterization of the query complexity of this quantum state generation problem. We exhibit an algorithm, which we call quantum rejection sampling, and analyze its cost using semidefinite programming. Our proof of a matching lower bound is based on the automorphism principle that allows to symmetrize any algorithm over the automorphism group of the problem. Our main technical innovation is an extension of the automorphism principle to continuous groups that arise for quantum state generation problems where the oracle encodes unknown quantum states, instead of just classical data. Furthermore, we illustrate how quantum rejection sampling may be used as a primitive in designing quantum algorithms, by providing three different applications. We first show that it was implicitly used in the quantum algorithm for linear systems of equations by Harrow et al. [2009]. Second we show that it can be used to speed up the main step in the quantum Metropolis sampling algorithm by Temme et al. [2011]. Finally, we derive a new quantum algorithm for the hidden shift problem of an arbitrary Boolean function and relate its query complexity to \u201cwater-filling\u201d of the Fourier spectrum.<\/jats:p>","DOI":"10.1145\/2493252.2493256","type":"journal-article","created":{"date-parts":[[2013,8,20]],"date-time":"2013-08-20T14:07:13Z","timestamp":1377007633000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":35,"title":["Quantum rejection sampling"],"prefix":"10.1145","volume":"5","author":[{"given":"Maris","family":"Ozols","sequence":"first","affiliation":[{"name":"NEC Laboratories America and IQC, University of Waterloo"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Roetteler","sequence":"additional","affiliation":[{"name":"NEC Laboratories America, Princeton, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[{"name":"NEC Laboratories America"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.42"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806710"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335394"},{"key":"e_1_2_1_6_1","unstructured":"Ambainis A. 2010. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arxiv:1010.4458.  Ambainis A. 2010. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arxiv:1010.4458."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.24"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"key":"e_1_2_1_9_1","first-page":"2","article-title":"Efficient quantum algorithms for simulating sparse","volume":"270","author":"Berry D. W.","year":"2005","journal-title":"Hamiltonians. Comm. Math. Phys."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Boixo S. Knill E. and Somma R. D. 2009. Eigenpath traversal by phase randomization. Quant. Inf. Comput. 9 9&10 833--855. http:\/\/www.rintonpress.com\/journals\/qiconline.html&num;&num;v9n910.   Boixo S. Knill E. and Somma R. D. 2009. Eigenpath traversal by phase randomization. Quant. Inf. Comput. 9 9&10 833--855. http:\/\/www.rintonpress.com\/journals\/qiconline.html&num;&num;v9n910.","DOI":"10.26421\/QIC9.9-10-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Brassard G. H\u00f8yer P. Mosca M. and Tapp A. 2002. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume 53--74.  Brassard G. H\u00f8yer P. Mosca M. and Tapp A. 2002. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume 53--74.","DOI":"10.1090\/conm\/305\/05215"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"key":"e_1_2_1_15_1","first-page":"2","article-title":"On the relationship between continuous- and discrete-time quantum walk","volume":"294","author":"Childs A. M.","year":"2008","journal-title":"Comm. Math. Phys."},{"key":"e_1_2_1_16_1","first-page":"3","volume-title":"Lecture Notes in Computer Science","volume":"6519","author":"Childs A. M.","year":"1807"},{"key":"e_1_2_1_17_1","first-page":"1969","article-title":"Quantum algorithms revisited","volume":"454","author":"Cleve R.","year":"1997","journal-title":"Proc. Roy. Soci. A. Math., Phys. Engi. Sci."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"de Wolf R. 2008. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing Library -- Graduate Surveys 1 1--20. DOI: http:\/\/dx.doi.org\/10.4086\/toc.gs.2008.001.  de Wolf R. 2008. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing Library -- Graduate Surveys 1 1--20. DOI: http:\/\/dx.doi.org\/10.4086\/toc.gs.2008.001.","DOI":"10.4086\/toc.gs.2008.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Devroye L. 1986. Non-Uniform Random Variate Generation. Springer New York.  Devroye L. 1986. Non-Uniform Random Variate Generation. Springer New York.","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090260"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780544"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.1334"},{"key":"e_1_2_1_24_1","unstructured":"Grover L. K. and Rudolph T. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph\/0208112.  Grover L. K. and Rudolph T. 2002. Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph\/0208112."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250867"},{"key":"e_1_2_1_27_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP'03)","author":"H\u00f8yer P."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Ivanyos G. 2008. On solving systems of random linear disequations. Quant. Inf. Comput. 8 6&7 579--594. DOI: http:\/\/www.rintonpress.com\/journals\/qiconline.html&num;&num;v8n67.   Ivanyos G. 2008. On solving systems of random linear disequations. Quant. Inf. Comput. 8 6&7 579--594. DOI: http:\/\/www.rintonpress.com\/journals\/qiconline.html&num;&num;v8n67.","DOI":"10.26421\/QIC8.6-7-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445226"},{"key":"e_1_2_1_30_1","unstructured":"Kitaev A. 1995. Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph\/9511026.  Kitaev A. 1995. Quantum measurements and the Abelian stabilizer problem. arXiv:quant-ph\/9511026."},{"key":"e_1_2_1_31_1","unstructured":"Kitaev A. and Webb W. A. 2008. Wavefunction preparation and resampling using a quantum computer. arXiv:0801.0342.  Kitaev A. and Webb W. A. 2008. Wavefunction preparation and resampling using a quantum computer. arXiv:0801.0342."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"K\u00f6bler J. Sch\u00f6ning U. and Toran J. 1993. The Graph Isomorphism Problem: Its Structural Complexity. Birkh\u00e4user Boston.   K\u00f6bler J. Sch\u00f6ning U. and Toran J. 1993. The Graph Isomorphism Problem: Its Structural Complexity. Birkh\u00e4user Boston.","DOI":"10.1007\/978-1-4612-0333-9"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.75"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996400"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Nagaj D. Wocjan P. and Zhang Y. 2009. Fast amplification of QMA. Quant. Inf. Computat. 9 11&12 1053--1068. DOI: http:\/\/www.rintonpress.com\/journals\/qiconline.html&num;&num;v9n1112.   Nagaj D. Wocjan P. and Zhang Y. 2009. Fast amplification of QMA. Quant. Inf. Computat. 9 11&12 1053--1068. DOI: http:\/\/www.rintonpress.com\/journals\/qiconline.html&num;&num;v9n1112.","DOI":"10.26421\/QIC9.11-12-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703440678"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.55"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133080"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873638"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.108.110502"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/18\/185302"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.101.130504"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Temme K. Osborne T. J. Vollbrecht K. G. H. Poulin D. and Verstraete F. 2011. Quantum metropolis sampling. Nature 471 7336 87--90. DOI: http:\/\/dx.doi.org\/10.1038\/nature09770.  Temme K. Osborne T. J. Vollbrecht K. G. H. Poulin D. and Verstraete F. 2011. Quantum metropolis sampling. Nature 471 7336 87--90. DOI: http:\/\/dx.doi.org\/10.1038\/nature09770.","DOI":"10.1038\/nature09770"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970343141X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1998.0247"},{"key":"e_1_2_1_49_1","first-page":"36","article-title":"Various techniques used in connection with random digits. Nati","volume":"12","author":"van Neumann J.","year":"1951","journal-title":"Bureau Stand. Applied Math Series"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796590"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380759"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1111758109"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493252.2493256","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2493252.2493256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:32Z","timestamp":1750231712000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2493252.2493256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2493252.2493256"],"URL":"https:\/\/doi.org\/10.1145\/2493252.2493256","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}