{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:12:30Z","timestamp":1764781950353,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,1,8]],"date-time":"2012-01-08T00:00:00Z","timestamp":1325980800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ARO\/NSA","award":["W911NF-09-1-0569"],"award-info":[{"award-number":["W911NF-09-1-0569"]}]},{"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,1,8]]},"DOI":"10.1145\/2090236.2090261","type":"proceedings-article","created":{"date-parts":[[2012,1,10]],"date-time":"2012-01-10T17:02:17Z","timestamp":1326214937000},"page":"290-308","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Quantum rejection sampling"],"prefix":"10.1145","author":[{"given":"Maris","family":"Ozols","sequence":"first","affiliation":[{"name":"University of Waterloo, IQC"}]},{"given":"Martin","family":"Roetteler","sequence":"additional","affiliation":[{"name":"NEC Laboratories America"}]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Libre de Bruxelles"}]}],"member":"320","published-online":{"date-parts":[[2012,1,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.42"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806710"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335394"},{"key":"e_1_3_2_1_6_1","volume-title":"Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arxiv:1010.4458","author":"Ambainis A.","year":"2010","unstructured":"A. Ambainis . Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arxiv:1010.4458 , 2010 . A. Ambainis. Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations. arxiv:1010.4458, 2010."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.24"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796300933"},{"issue":"2","key":"e_1_3_2_1_9_1","first-page":"9","article-title":"Efficient quantum algorithms for simulating sparse Hamiltonians","volume":"270","author":"Berry D. W.","year":"2005","unstructured":"D. W. Berry , G. Ahokas , R. Cleve , and B. C. Sanders . Efficient quantum algorithms for simulating sparse Hamiltonians . Communications in Mathematical Physics , 270 ( 2 ): 9 , 2005 . D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics, 270(2):9, 2005.","journal-title":"Communications in Mathematical Physics"},{"key":"e_1_3_2_1_10_1","volume-title":"Eigenpath traversal by phase randomization. Quantum Information and Computation, 9(9,10):833--855","author":"Boixo S.","year":"2009","unstructured":"S. Boixo , E. Knill , and R. D. Somma . Eigenpath traversal by phase randomization. Quantum Information and Computation, 9(9,10):833--855 , 2009 . S. Boixo, E. Knill, and R. D. Somma. Eigenpath traversal by phase randomization. Quantum Information and Computation, 9(9,10):833--855, 2009."},{"key":"e_1_3_2_1_11_1","volume-title":"H\u00f8 yer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4--5):493--505","author":"Boyer M.","year":"1998","unstructured":"M. Boyer , G. Brassard , P. H\u00f8 yer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4--5):493--505 , 1998 . M. Boyer, G. Brassard, P. H\u00f8 yer, and A. Tapp. Tight bounds on quantum searching. Fortschritte der Physik, 46(4--5):493--505, 1998."},{"key":"e_1_3_2_1_12_1","volume-title":"Quantum amplitude amplification and estimation. arxiv:quant-ph\/0005055","author":"Brassard G.","year":"2000","unstructured":"G. Brassard , P. H\u00f8yer , M. Mosca , and A. Tapp . Quantum amplitude amplification and estimation. arxiv:quant-ph\/0005055 , 2000 . G. Brassard, P. H\u00f8yer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. arxiv:quant-ph\/0005055, 2000."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00144-X"},{"issue":"2","key":"e_1_3_2_1_15_1","first-page":"22","article-title":"On the relationship between continuous-and discrete-time quantum walk","volume":"294","author":"Childs A. M.","year":"2008","unstructured":"A. M. Childs . On the relationship between continuous-and discrete-time quantum walk . Communications in Mathematical Physics , 294 ( 2 ): 22 , 2008 . A. M. Childs. On the relationship between continuous-and discrete-time quantum walk. Communications in Mathematical Physics, 294(2):22, 2008.","journal-title":"Communications in Mathematical Physics"},{"key":"e_1_3_2_1_16_1","series-title":"Lecture Notes in Computer Science","first-page":"11","volume-title":"Theory of Quantum Computation, Communication, and Cryptography (TQC","author":"Childs A. M.","year":"2010","unstructured":"A. M. Childs and R. Kothari . Simulating Sparse Hamiltonians with Star Decompositions . In Theory of Quantum Computation, Communication, and Cryptography (TQC 2010 ), volume 6519 of Lecture Notes in Computer Science , page 11 , Berlin, Heidelberg , 2011. Springer . A. M. Childs and R. Kothari. Simulating Sparse Hamiltonians with Star Decompositions. In Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), volume 6519 of Lecture Notes in Computer Science, page 11, Berlin, Heidelberg, 2011. Springer."},{"issue":"1969","key":"e_1_3_2_1_17_1","first-page":"18","article-title":"Quantum Algorithms Revisited. Proceedings of the Royal Society A: Mathematical","volume":"454","author":"Cleve R.","year":"1997","unstructured":"R. Cleve , A. Ekert , C. Macchiavello , and M. Mosca . Quantum Algorithms Revisited. Proceedings of the Royal Society A: Mathematical , Physical and Engineering Sciences , 454 ( 1969 ): 18 , 1997 . R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum Algorithms Revisited. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 454(1969):18, 1997.","journal-title":"Physical and Engineering Sciences"},{"key":"e_1_3_2_1_18_1","first-page":"489","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03)","author":"Dam W.","year":"2003","unstructured":"W. Dam , S. Hallgren , and L. Ip . Quantum algorithms for some hidden shift problems . In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03) , pages 489 -- 498 , 2003 . W. Dam, S. Hallgren, and L. Ip. Quantum algorithms for some hidden shift problems. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), pages 489--498, 2003."},{"key":"e_1_3_2_1_19_1","volume-title":"A brief introduction to Fourier analysis on the Boolean cube","author":"de Wolf R.","year":"2008","unstructured":"R. de Wolf . A brief introduction to Fourier analysis on the Boolean cube . Theory of Computing Library - - Graduate Surveys, 1:1--20, 2008 . R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing Library -- Graduate Surveys, 1:1--20, 2008."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8643-8"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090260"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780544"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.85.1334"},{"key":"e_1_3_2_1_25_1","volume-title":"Creating superpositions that correspond to efficiently integrable probability distributions. arxiv:0208112","author":"Grover L. K.","year":"2002","unstructured":"L. K. Grover and T. Rudolph . Creating superpositions that correspond to efficiently integrable probability distributions. arxiv:0208112 , 2002 . L. K. Grover and T. Rudolph. Creating superpositions that correspond to efficiently integrable probability distributions. arxiv:0208112, 2002."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250867"},{"key":"e_1_3_2_1_28_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/3-540-45061-0_25","volume-title":"Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP'03)","author":"H\u00f8yer P.","year":"2003","unstructured":"P. H\u00f8yer , M. Mosca , and R. de Wolf . Quantum search on bounded-error inputs . In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP'03) , volume 2719 of Lecture Notes in Computer Science , pages 291 -- 299 . Springer , 2003 . P. H\u00f8yer, M. Mosca, and R. de Wolf. Quantum search on bounded-error inputs. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP'03), volume 2719 of Lecture Notes in Computer Science, pages 291--299. Springer, 2003."},{"issue":"6","key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","first-page":"579","DOI":"10.26421\/QIC8.6-7-2","article-title":"On solving systems of random linear disequations","volume":"8","author":"Ivanyos G.","year":"2008","unstructured":"G. Ivanyos . On solving systems of random linear disequations . Quantum Information and Computation , 8 ( 6&7 ): 579 -- 594 , 2008 . G. Ivanyos. On solving systems of random linear disequations. Quantum Information and Computation, 8(6&7):579--594, 2008.","journal-title":"Quantum Information and Computation"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445226"},{"key":"e_1_3_2_1_31_1","volume-title":"arxiv:quant-ph\/9511026","author":"Kitaev A.","year":"1995","unstructured":"A. Kitaev . Quantum measurements and the Abelian Stabilizer Problem . arxiv:quant-ph\/9511026 , 1995 . A. Kitaev. Quantum measurements and the Abelian Stabilizer Problem. arxiv:quant-ph\/9511026, 1995."},{"key":"e_1_3_2_1_32_1","volume-title":"Wavefunction preparation and resampling using a quantum computer. arxiv:0801.0342","author":"Kitaev A.","year":"2008","unstructured":"A. Kitaev and W. A. Webb . Wavefunction preparation and resampling using a quantum computer. arxiv:0801.0342 , 2008 . A. Kitaev and W. A. Webb. Wavefunction preparation and resampling using a quantum computer. arxiv:0801.0342, 2008."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0333-9","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science","author":"K\u00f6bler J.","year":"1993","unstructured":"J. K\u00f6bler , U. Sch\u00f6ning , and J. Toran . The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science . Birkh\u00e4user Boston , 1993 . J. K\u00f6bler, U. Sch\u00f6ning, and J. Toran. The Graph Isomorphism Problem: Its Structural Complexity. Progress in Theoretical Computer Science. Birkh\u00e4user Boston, 1993."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.75"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176996400"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1699114"},{"issue":"11","key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.26421\/QIC9.11-12-8","article-title":"Fast amplification of QMA","volume":"9","author":"Nagaj D.","year":"2009","unstructured":"D. Nagaj , P. Wocjan , and Y. Zhang . Fast amplification of QMA . Quantum Information and Computation , 9 ( 11&12 ): 1053 -- 1068 , 2009 . D. Nagaj, P. Wocjan, and Y. Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11&12):1053--1068, 2009.","journal-title":"Quantum Information and Computation"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703440678"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.55"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133080"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873638"},{"key":"e_1_3_2_1_43_1","volume-title":"Contracting tensor networks and preparing PEPS on a quantum computer. arxiv:1104.1410","author":"Schwarz M.","year":"2011","unstructured":"M. Schwarz , K. Temme , and F. Verstraete . Contracting tensor networks and preparing PEPS on a quantum computer. arxiv:1104.1410 , 2011 . M. Schwarz, K. Temme, and F. Verstraete. Contracting tensor networks and preparing PEPS on a quantum computer. arxiv:1104.1410, 2011."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/42\/18\/185302"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.101.130504"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09770"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.1998.0247"},{"key":"e_1_3_2_1_49_1","first-page":"36","article-title":"Various techniques used in connection with random digits. National Bureau of Standards","volume":"12","author":"von Neumann J.","year":"1951","unstructured":"J. von Neumann . Various techniques used in connection with random digits. National Bureau of Standards , Applied Math Series , 12 : 36 -- 38 , 1951 . J. von Neumann. Various techniques used in connection with random digits. National Bureau of Standards, Applied Math Series, 12:36--38, 1951.","journal-title":"Applied Math Series"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796590"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380759"},{"key":"e_1_3_2_1_52_1","volume-title":"A quantum-quantum Metropolis algorithm. arxiv:1011.1468","author":"Yung M.-H.","year":"2010","unstructured":"M.-H. Yung and A. Aspuru-Guzik . A quantum-quantum Metropolis algorithm. arxiv:1011.1468 , 2010 . M.-H. Yung and A. Aspuru-Guzik. A quantum-quantum Metropolis algorithm. arxiv:1011.1468, 2010."}],"event":{"name":"ITCS '12: Innovations in Theoretical Computer Science","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Cambridge Massachusetts","acronym":"ITCS '12"},"container-title":["Proceedings of the 3rd Innovations in Theoretical Computer Science Conference"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090261","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2090236.2090261","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:46Z","timestamp":1750241206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2090236.2090261"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,8]]},"references-count":52,"alternative-id":["10.1145\/2090236.2090261","10.1145\/2090236"],"URL":"https:\/\/doi.org\/10.1145\/2090236.2090261","relation":{},"subject":[],"published":{"date-parts":[[2012,1,8]]},"assertion":[{"value":"2012-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}