{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,4]],"date-time":"2026-05-04T22:19:59Z","timestamp":1777933199184,"version":"3.51.4"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>What quantum algorithms outperform classical computation and how do they do it?<\/jats:p>","DOI":"10.1145\/1646353.1646375","type":"journal-article","created":{"date-parts":[[2010,1,26]],"date-time":"2010-01-26T14:01:38Z","timestamp":1264514498000},"page":"84-93","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":73,"title":["Recent progress in quantum algorithms"],"prefix":"10.1145","volume":"53","author":[{"given":"Dave","family":"Bacon","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Wim","family":"van Dam","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}]}],"member":"320","published-online":{"date-parts":[[2010,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258579"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.48.1687"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447311"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 16th Annual ACM SIAM Symposium on Discrete Algorithms","author":"Ambainis A.","year":"2005","unstructured":"Ambainis , A. , Kempe , J. , Rivosh , A. Coins make quantum walks faster . In Proceedings of the 16th Annual ACM SIAM Symposium on Discrete Algorithms ( 2005 ), 1099. Ambainis, A., Kempe, J., Rivosh, A. Coins make quantum walks faster. In Proceedings of the 16th Annual ACM SIAM Symposium on Discrete Algorithms (2005), 1099."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1113479"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109654"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780552"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.58.915"},{"key":"e_1_2_1_10_1","volume-title":"A quantum algorithm for the Hamiltonian NAND tree. Eprint arXiv:quant-ph\/0702144","author":"Farhi E.","year":"2007","unstructured":"Farhi , E. , Goldstone , J. , Gutmann , S. A quantum algorithm for the Hamiltonian NAND tree. Eprint arXiv:quant-ph\/0702144 , 2007 . Farhi, E., Goldstone, J., Gutmann, S. A quantum algorithm for the Hamiltonian NAND tree. Eprint arXiv:quant-ph\/0702144, 2007."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04279"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510001"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0204-7"},{"key":"e_1_2_1_16_1","volume-title":"Quantum Communication","author":"Kitaev A.","year":"1997","unstructured":"Kitaev , A. Quantum error correction with imperfect gates . In Quantum Communication , Computing and Measurement (New York, 1997 ). Plenum , 181--188. Kitaev, A. Quantum error correction with imperfect gates. In Quantum Communication, Computing and Measurement (New York, 1997). Plenum, 181--188."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.279.5349.342"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1998.0166"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04251"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 16th Annual ACM SIAM Symposium on Discrete Algorithms","author":"Magniez F.","year":"2005","unstructured":"Magniez , F. , Santha , M. , Szegedy , M. Quantum algorithms for the triangle problem . In Proceedings of the 16th Annual ACM SIAM Symposium on Discrete Algorithms ( 2005 ), 1109. Magniez, F., Santha, M., Szegedy, M. Quantum algorithms for the triangle problem. In Proceedings of the 16th Annual ACM SIAM Symposium on Discrete Algorithms (2005), 1109."},{"key":"e_1_2_1_21_1","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M.A.","year":"2000","unstructured":"Nielsen , M.A. Chuang , I.L. Quantum Computation and Quantum Information . Cambridge University Press , New York , 2000 . Nielsen, M.A. Chuang, I.L. Quantum Computation and Quantum Information. Cambridge University Press, New York, 2000."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652155"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/359340.359342"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365700"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875509"},{"key":"e_1_2_1_26_1","volume-title":"Department of Physics, at the University of Washington","author":"Woehr J.","unstructured":"Woehr , J. Online interview \"A Conversation with Christos Papadimitriou\". Dr. Dobb's J. July Dave Bacon is an assistant research professor in the Department of Computer Science and Engineering , Department of Physics, at the University of Washington , Seattle . Woehr, J. Online interview \"A Conversation with Christos Papadimitriou\". Dr. Dobb's J. July Dave Bacon is an assistant research professor in the Department of Computer Science and Engineering, Department of Physics, at the University of Washington, Seattle."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1646353.1646375","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1646353.1646375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:40:56Z","timestamp":1750250456000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1646353.1646375"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1646353.1646375"],"URL":"https:\/\/doi.org\/10.1145\/1646353.1646375","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,2]]},"assertion":[{"value":"2010-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}