{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:29:48Z","timestamp":1756312188969,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":64,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540929093"},{"type":"electronic","value":"9783540929109"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-540-92910-9_43","type":"book-chapter","created":{"date-parts":[[2012,8,25]],"date-time":"2012-08-25T14:54:06Z","timestamp":1345906446000},"page":"1451-1492","source":"Crossref","is-referenced-by-count":8,"title":["Algorithms for Quantum Computers"],"prefix":"10.1007","author":[{"given":"Jamie","family":"Smith","sequence":"first","affiliation":[]},{"given":"Michele","family":"Mosca","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"43_CR00431","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S Aaronson","year":"2004","unstructured":"Aaronson S, Shi Y (2004) Quantum lower bounds for the collision and the element distinctness problems. J ACM 51(4):595\u2013605. doi: \n                  http:\/\/doi.acm.org\/10.1145\/1008731.1008735","journal-title":"J ACM"},{"key":"43_CR00433","doi-asserted-by":"crossref","unstructured":"Aharonov D, Ambainis A, Kempe J, Vazirani U (2001) Quantum walks on graphs. In: STOC\u201901: proceedings of the 33rd annual ACM symposium on theory of computing. ACM Press, New York, pp 50\u201359. doi: \n                  http:\/\/doi.acm.org\/10.1145\/380752.380758","DOI":"10.1145\/380752.380758"},{"key":"43_CR00432","unstructured":"Aharonov D, Arad I (2006) The BQP-hardness of approximating the Jones polynomial. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0605181"},{"key":"43_CR00434","unstructured":"Aharonov D, Arad I, Eban E, Landau Z (2007) Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0702008"},{"issue":"3","key":"43_CR00435","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s00453-008-9168-0","volume":"55","author":"D Aharonov","year":"2008","unstructured":"Aharonov D, Jones V, Landau Z (2008) A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica 55(3):395\u2013421","journal-title":"Algorithmica"},{"key":"43_CR00436","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1142\/S0219749903000383","volume":"1","author":"A Ambainis","year":"2003","unstructured":"Ambainis A (2003) Quantum walks and their algorithmic applications. Int J Quantum Inform 1:507\u2013518","journal-title":"Int J Quantum Inform"},{"key":"43_CR00437","doi-asserted-by":"crossref","unstructured":"Ambainis A (2004) Quantum walk algorithm for element distinctness. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science, pp 22\u201331. doi: 10.1109\/FOCS.2004.54","DOI":"10.1109\/FOCS.2004.54"},{"key":"43_CR00438","doi-asserted-by":"crossref","unstructured":"Ambainis A, Bach E, Nayak A, Vishwanath A, Watrous J (2001) One-dimensional quantum walks. In: STOC\u2019 01: proceedings of the 33rd annual ACM symposium on theory of computing. ACM Press, New York, pp 37\u201349. doi: \n                  http:\/\/doi.acm.org\/10.1145\/380752.380757","DOI":"10.1145\/380752.380757"},{"key":"43_CR00439","doi-asserted-by":"crossref","unstructured":"Ambainis A, Childs A, Reichardt B, Spalek R, Zhang S (2007) Any and-or formula of size n can be evaluated in time n\n                1 \u2215 2+o(1) on a quantum computer. In: Proceedings of the 48th annual IEEE symposium on foundations of computer science, pp 363\u2013372. doi: 10.1109\/FOCS.2007.57","DOI":"10.1109\/FOCS.2007.57"},{"key":"43_CR004310","unstructured":"Arad I, Landau Z (2008) Quantum computation and the evaluation of tensor networks. \n                  http:\/\/arxiv.org\/abs\/0805.0040"},{"key":"43_CR004311","unstructured":"Beaudin L, Ellis-Monaghan J, Pangborn G, Shrock R (2008) A little statistical mechanics for the graph theorist. \n                  http:\/\/arxiv.org\/abs\/0804.2468"},{"key":"43_CR004312","doi-asserted-by":"publisher","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"BK Bernstein","year":"1997","unstructured":"Bernstein BK, Vazirani U (1997) Quantum complexity theory. SIAM J Comput 26:1411\u20131473","journal-title":"SIAM J Comput"},{"key":"43_CR004313","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","volume":"270","author":"DW Berry","year":"2007","unstructured":"Berry DW, Ahokas G, Cleve R, Sanders BC (2007) Efficient quantum algorithms for simulating sparse Hamiltonians. Commun Math Phys 270:359","journal-title":"Commun Math Phys"},{"key":"43_CR004314","unstructured":"Boixo S, Knill E, Somma R (2009) Quantum state preparation by phase randomization. \n                  http:\/\/arxiv.org\/abs\/0903.1652"},{"key":"43_CR004315","unstructured":"Boneh D, Lipton R (1995) Quantum cryptanalysis of hidden linear functions (extended abstract). In: Proceedings of the 15th annual international cryptology conference on advances in cryptology. Lecture notes in computer science, vol. 963. Springer, London, UK, pp 424\u2013437"},{"issue":"5\u20135","key":"43_CR004316","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","volume":"56","author":"M Boyer","year":"1998","unstructured":"Boyer M, Brassard G, H\u00f8yer P, Tapp A (1998) Tight bounds on quantum searching. Fortschritte der Physik 56(5\u20135):493\u2013505","journal-title":"Fortschritte der Physik"},{"key":"43_CR004317","doi-asserted-by":"crossref","unstructured":"Brassard G, H\u00f8yer P (1997) An exact quantum polynomial-time algorithm for Simon's problem. In: Proceedings of the fifth Israeli symposium on theory of computing and systems (ISTCS\u201997). IEEE Press, Piscataway, pp 12\u201323","DOI":"10.1109\/ISTCS.1997.595153"},{"key":"43_CR004319","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume":"305","author":"G Brassard","year":"2002","unstructured":"Brassard G, H\u00f8yer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. Quantum Computation & Information, AMS Contemporary Math Series 305:53\u201374","journal-title":"Quantum Computation & Information, AMS Contemporary Math Series"},{"key":"43_CR004318","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/261342.261346","volume":"28","author":"G Brassard","year":"1997","unstructured":"Brassard G, H\u00f8yer P, Tapp A (1997) Cryptology column \u2014 quantum algorithm for the collision problem. ACM SIGACT News 28:14\u201319","journal-title":"ACM SIGACT News"},{"key":"43_CR004320","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74341-2","volume-title":"Distance-regular graphs","author":"AE Brouwer","year":"1989","unstructured":"Brouwer AE (1989) Distance-regular graphs. Springer, New York"},{"key":"43_CR004321","unstructured":"Childs A (2008) CO781 Topics in quantum information: quantum algorithms. Lecture notes on quantum algorithms. \n                  http:\/\/www.math.uwaterloo.ca\/~amchilds\/teaching\/w08\/co781.html"},{"key":"43_CR004323","doi-asserted-by":"crossref","unstructured":"Childs AM, Cleve R, Deotto E, Farhi E, Gutmann S, Spielman DA (2003) Exponential algorithmic speedup by a quantum walk. In: STOC \u201903: proceedings of the 35th annual ACM symposium on theory of computing. ACM Press, New York, pp 59\u201368. doi: \n                  http:\/\/doi.acm.org\/10.1145\/780542.780552","DOI":"10.1145\/780542.780552"},{"issue":"1","key":"43_CR004322","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1103\/RevModPhys.82.1","volume":"82","author":"A Childs","year":"2010","unstructured":"Childs A, van Dam W (2010) Quantum algorithms for algebraic problems. Rev Mod Phys 82(1):1\u201352","journal-title":"Rev Mod Phys"},{"key":"43_CR004324","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R Cleve","year":"1998","unstructured":"Cleve R, Ekert A, Macchiavello C, Mosca M (1998) Quantum algorithms revisited. Proc Roy Soc Lond A 454:339\u2013354","journal-title":"Proc Roy Soc Lond A"},{"issue":"9","key":"43_CR004333","first-page":"090","volume":"98","author":"GM D'Ariano","year":"2007","unstructured":"D'Ariano GM, van Dam W, Ekert E, Macchiavello C, Mosca M (2007) General optimized schemes for phase estimation. Phys Rev Lett 98(9):090,501","journal-title":"Phys Rev Lett"},{"key":"43_CR004326","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1103\/RevModPhys.80.1061","volume":"80","author":"A Das","year":"2008","unstructured":"Das A, Chakrabarti BK (2008) Quantum annealing and analog quantum computation. Rev Mod Phys 80:1061","journal-title":"Rev Mod Phys"},{"key":"43_CR004325","unstructured":"De las Cuevas G, D\u00fcr W, Van den Nest M, Briegel HJ (2008) Completeness of classical spin models and universal quantum computation. \n                  http:\/\/arxiv.org\/abs\/0812.2368"},{"key":"43_CR004327","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1098\/rspa.1985.0070","volume":"400","author":"D Deutsch","year":"1985","unstructured":"Deutsch D (1985) Quantum theory, the Church-Turing principle and the universal quantum computer. Proc Roy Soc Lond A 400:97\u2013117","journal-title":"Proc Roy Soc Lond A"},{"key":"43_CR004328","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1098\/rspa.1992.0167","volume":"439","author":"D Deutsch","year":"1992","unstructured":"Deutsch D, Jozsa R (1992) Rapid solutions of problems by quantum computation. Proc Roy Soc Lond, A 439:553\u2013558","journal-title":"Proc Roy Soc Lond A"},{"key":"43_CR004329","unstructured":"Farhi E, Goldstone J, Gutmann S (2007) A quantum algorithm for the Hamiltonian NAND tree. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0702144"},{"issue":"6,7","key":"43_CR004330","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"R Feynman","year":"1982","unstructured":"Feynman R (1982) Simulating physics with computers. Int J Theor Phys 21(6,7):467\u2013488","journal-title":"Int J Theor Phys"},{"key":"43_CR004332","unstructured":"Freedman MH, Kitaev A, Larsen MJ, Wang Z (2001) Topological quantum computation. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0101025"},{"key":"43_CR004331","unstructured":"Freedman MH, Kitaev A, Wang Z (2000) Simulation of topological field theories by quantum computers. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0001071"},{"key":"43_CR004334","unstructured":"Geraci J (2008) A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs. \n                  http:\/\/arxiv.org\/abs\/0801.4833"},{"issue":"3","key":"43_CR004335","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/s00220-008-0438-0","volume":"279","author":"J Geraci","year":"2008","unstructured":"Geraci J, Lidar DA (2008) On the exact evaluation of certain instances of the Potts partition function by quantum computers. Commun Math Phys 279(3):735\u2013768","journal-title":"Commun Math Phys"},{"key":"43_CR004336","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(96)00188-0","volume":"180","author":"D Grigoriev","year":"1997","unstructured":"Grigoriev D (1997) Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theor Comput Sci 180:217\u2013228","journal-title":"Theor Comput Sci"},{"key":"43_CR004337","first-page":"212","volume-title":"Proceedings of the 28th annual ACM symposium on the theory of computing (STOC, 96)","author":"L Grover","year":"1996","unstructured":"Grover L (1996) A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th annual ACM symposium on the theory of computing (STOC, 96). ACM Press, New York, pp 212\u2013219"},{"key":"43_CR004338","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/276698.276712","volume-title":"Proceedings of the 13th annual ACM symposium on theory of computing (STOC '98)","author":"L Grover","year":"1998","unstructured":"Grover L (1998) A framework for fast quantum mechanical algorithms. In: Proceedings of the 13th annual ACM symposium on theory of computing (STOC' 98). ACM Press, New York, pp 53\u201362"},{"key":"43_CR004339","doi-asserted-by":"crossref","unstructured":"Hirvensalo M (2001) Quantum computing. Series: Natural Computing Series. Springer","DOI":"10.1007\/978-3-662-04461-2"},{"key":"43_CR004340","unstructured":"H\u00fcbener R, Van den Nest M, D\u00fcr W, Briegel HJ (2008) Classical spin systems and the quantum stabilizer formalism: general mappings and applications. \n                  http:\/\/arxiv.org\/abs\/0812.2127"},{"key":"43_CR004341","volume-title":"Quantum computation beyond the circuit model","author":"S Jordan","year":"2008","unstructured":"Jordan S (2008) Quantum computation beyond the circuit model. PhD thesis, MIT University, Cambridge"},{"key":"43_CR004342","doi-asserted-by":"crossref","unstructured":"Karchmer M, Wigderson A (1993) On span programs. In: Proceedings of the 8th IEEE structures in complexity conference. IEEE Press, Piscataway, pp 102\u2013111","DOI":"10.1109\/SCT.1993.336536"},{"key":"43_CR004343","volume-title":"An introduction to quantum computation","author":"P Kaye","year":"2007","unstructured":"Kaye P, Laflamme R, Mosca M (2007) An introduction to quantum computation. Oxford University Press, Oxford, UK"},{"issue":"4","key":"43_CR004344","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1080\/00107151031000110776","volume":"44","author":"J Kempe","year":"2003","unstructured":"Kempe J (2003) Quantum random walks - an introductory overview. Contemp Phys 44(4):307\u2013327","journal-title":"Contemp Phys"},{"key":"43_CR004345","unstructured":"Kitaev AY (1995) Quantum measurements and the Abelian stabilizer problem. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/9511026"},{"key":"43_CR004346","volume-title":"Classical and quantum computation","author":"A Kitaev","year":"2002","unstructured":"Kitaev A, Shen A, Vyalvi M (2002) Classical and quantum computation. American Mathematical Society, Providence, RI"},{"key":"43_CR004347","doi-asserted-by":"crossref","unstructured":"Magniez F, Nayak A, Roland J, Santha M (2007) Search via quantum walk. In: STOC \u201907: proceedings of the 39th annual ACM symposium on theory of computing. ACM, New York, pp 575\u2013584. doi: \n                  http:\/\/doi.acm.org\/10.1145\/1250790.1250874","DOI":"10.1145\/1250790.1250874"},{"key":"43_CR004348","doi-asserted-by":"publisher","DOI":"10.1201\/9781439821916","volume-title":"Handbook of applied cryptography","author":"A Menezes","year":"1996","unstructured":"Menezes A, van Oorschot P, Vanstone S (1996) Handbook of applied cryptography. CRC Press, Boca Raton"},{"key":"43_CR004349","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813870","volume-title":"Quantum computer science: an introduction","author":"ND Mermin","year":"2007","unstructured":"Mermin ND (2007) Quantum computer science: an introduction. Cambridge University Press, Cambridge"},{"key":"43_CR004350","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0304-3975(00)00217-6","volume":"264","author":"M Mosca","year":"2001","unstructured":"Mosca M (2001) Counting by quantum eigenvalue estimation. Theor Comput Sci 264:139\u2013153","journal-title":"Theor Comput Sci"},{"key":"43_CR004351","doi-asserted-by":"crossref","unstructured":"Mosca M (2008) Abelian hidden subgroup problem. In: Kao M-Y (ed) Encyclopedia of algorithms. Springer, Berlin","DOI":"10.1007\/978-0-387-30162-4_1"},{"key":"43_CR004352","doi-asserted-by":"crossref","unstructured":"Mosca M (2009) Quantum algorithms. In: Meyers R (ed) Encyclopedia of complexity and systems science. Springer","DOI":"10.1007\/978-0-387-30440-3_423"},{"key":"43_CR004353","unstructured":"Nayak A, Vishwanath A (2000) Quantum walk on the line. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0010117"},{"key":"43_CR004354","volume-title":"Quantum computation and quantum information","author":"M Nielsen","year":"2000","unstructured":"Nielsen M, Chuang I (2000) Quantum computation and quantum information. Cambridge University Press, Cambridge, UK"},{"key":"43_CR004355","unstructured":"Reichardt BW, Spalek R (2008) Span-program-based quantum algorithm for evaluating formulas. In: STOC \u201908: proceedings of the 40th annual ACM symposium on theory of computing. ACM Press, New York, pp 103\u2013112. doi: \n                  http:\/\/doi.acm.org\/10.1145\/1374376.1374394"},{"key":"43_CR004356","doi-asserted-by":"crossref","unstructured":"Santha M (2008) Quantum walk based search algorithms. In: Agrawal M, Du D-Z, Duan Z, Li A (eds) Theory and applications of models of computation. Lecture notes in computer science, vol 4978. Springer, Berlin, Heidelberg, pp 31\u201346. doi: 10.1007\/978-3-540-79228-4_3","DOI":"10.1007\/978-3-540-79228-4_3"},{"key":"43_CR004357","doi-asserted-by":"crossref","unstructured":"Shor P (1994) Algorithms for quantum computation: Discrete logarithms and factoring. In: Proceedings of the 35th annual symposium on foundations of computer science. IEEE Computer Society, Washington, DC, pp 124\u2013134","DOI":"10.1109\/SFCS.1994.365700"},{"key":"43_CR004358","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P Shor","year":"1997","unstructured":"Shor P (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26:1484\u20131509","journal-title":"SIAM J Comput"},{"key":"43_CR004359","doi-asserted-by":"crossref","unstructured":"Simon D (1994) On the power of quantum computation. In: Proceedings of the 35th IEEE symposium on the foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 116\u2013123","DOI":"10.1109\/SFCS.1994.365701"},{"key":"43_CR004360","doi-asserted-by":"crossref","unstructured":"Szegedy M (2004) Quantum speed-up of Markov chain based algorithms. In: Proceedings of the 45th annual IEEE symposium on foundations of computer science (FOCS). IEEE Computer Society, Washington, DC, pp 32\u201341. doi: \n                  http:\/\/dx.doi.org\/10.1109\/FOCS.2004.53","DOI":"10.1109\/FOCS.2004.53"},{"issue":"6","key":"43_CR004361","first-page":"483","volume":"6","author":"T Tulsi","year":"2006","unstructured":"Tulsi T, Grover L, Patel A (2006) A new algorithm for fixed point quantum search. Quant Inform Comput 6(6):483\u2013494","journal-title":"Quant Inform Comput"},{"key":"43_CR004362","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: knots, colourings and countings","author":"D Welsh","year":"1993","unstructured":"Welsh D (1993) Complexity: knots, colourings and countings. Cambridge University Press, Cambridge, UK"},{"key":"43_CR004363","unstructured":"Wiebe N, Berry DW, H\u00f8yer P, Sanders BC (2008) Higher order decompositions of ordered operator exponentials. \n                  http:\/\/arxiv.org\/abs\/0812.0562"},{"key":"43_CR004364","unstructured":"Wocjan P, Yard J (2006) The Jones polynomial: quantum algorithms and applications in quantum complexity theory. \n                  http:\/\/arxiv.org\/abs\/quant-ph\/0603069"}],"container-title":["Handbook of Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-92910-9_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T12:17:08Z","timestamp":1619525828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-92910-9_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783540929093","9783540929109"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-92910-9_43","relation":{},"subject":[],"published":{"date-parts":[[2012]]}}}