{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:02:11Z","timestamp":1725562931820},"publisher-location":"Berlin, Heidelberg","reference-count":60,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_1","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"1-11","source":"Crossref","is-referenced-by-count":5,"title":["New Developments in Quantum Algorithms"],"prefix":"10.1007","author":[{"given":"Andris","family":"Ambainis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"1_CR1","unstructured":"Aaronson, S.: D-Wave Easter Spectacular. A blog post (April 7, 2007), http:\/\/scottaaronson.com\/blog\/?p=225"},{"key":"1_CR2","unstructured":"Altshuler, B., Krovi, H., Roland, J.: Anderson localization casts clouds over adiabatic quantum optimization, arxiv:0912.0746"},{"key":"1_CR3","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1006\/jcss.2002.1826","volume":"64","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A.: Quantum lower bounds by quantum arguments. Journal of Computer and System Sciences\u00a064, 750\u2013767 (2002), quant-ph\/0002066","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1142\/S0219749903000383","volume":"1","author":"A. Ambainis","year":"2003","unstructured":"Ambainis, A.: Quantum walks and their algorithmic applications. International Journal of Quantum Information\u00a01, 507\u2013518 (2003), quant-ph\/0403120","journal-title":"International Journal of Quantum Information"},{"issue":"1","key":"1_CR5","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A. Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM Journal on Computing\u00a037(1), 210\u2013239 (2007), FOCS 2004 and quant-ph\/0311001","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"1_CR6","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/992287.992296","volume":"35","author":"A. Ambainis","year":"2004","unstructured":"Ambainis, A.: Quantum search algorithms (a survey). SIGACT News\u00a035(2), 22\u201335 (2004), quant-ph\/0504012","journal-title":"SIGACT News"},{"issue":"2","key":"1_CR7","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.jcss.2005.06.006","volume":"72","author":"A. Ambainis","year":"2006","unstructured":"Ambainis, A.: Polynomial degree vs. quantum query complexity. Journal of Computer and System Sciences\u00a072(2), 220\u2013238 (2006), quant-ph\/0305028","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR8","unstructured":"Ambainis, A.: A nearly optimal discrete query quantum algorithm for evaluating NAND formulas, arxiv:0704.3628"},{"key":"1_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-77566-9_1","volume-title":"SOFSEM 2008: Theory and Practice of Computer Science","author":"A. Ambainis","year":"2008","unstructured":"Ambainis, A.: Quantum random walks - New method for designing quantum algorithms. In: Geffert, V., Karhum\u00e4ki, J., Bertoni, A., Preneel, B., N\u00e1vrat, P., Bielikov\u00e1, M. (eds.) SOFSEM 2008. LNCS, vol.\u00a04910, pp. 1\u20134. Springer, Heidelberg (2008)"},{"key":"1_CR10","unstructured":"Ambainis, A.: Quantum algorithms for formula evaluation. In: Proceedings of the NATO Advanced Research Workshop Quantum Cryptography and Computing: Theory and Implementations (to appear)"},{"key":"1_CR11","unstructured":"Ambainis, A.: Variable time amplitude amplification and a faster quantum algorithm for systems of linear equations (in preparation, 2010)"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Ambainis, A., Childs, A., Reichardt, B., Spalek, R., Zhang, S.: Any AND-OR formula of size N can be evaluated in time N 1\/2\u2009+\u2009o(1) on a quantum computer. In: Proceedings of FOCS 2007, pp. 363\u2013372 (2007)","DOI":"10.1109\/FOCS.2007.57"},{"key":"1_CR13","unstructured":"Ambainis, A., Kempe, J., Rivosh, A.: Coins make quantum walks faster. In: Proceedings of SODA 2005, pp. 1099\u20131108 (2005), quant-ph\/0402107"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/j.jcss.2004.02.002","volume":"69","author":"H. Barnum","year":"2004","unstructured":"Barnum, H., Saks, M.: A lower bound on the quantum complexity of read once functions. Journal of Computer and System Sciences\u00a069, 244\u2013258 (2004), quant-ph\/0201007","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Barnum, H., Saks, M.E., Szegedy, M.: Quantum query complexity and semi-definite programming. In: IEEE Conference on Computational Complexity 2003, pp. 179\u2013193 (2003)","DOI":"10.1109\/CCC.2003.1214419"},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","volume":"270","author":"D.W. Berry","year":"2007","unstructured":"Berry, D.W., Ahokas, G., Cleve, R., Sanders, B.C.: Efficient quantum algorithms for simulating sparse Hamiltonians. Communications in Mathematical Physics\u00a0270(2), 359\u2013371 (2007), quant-ph\/0508139","journal-title":"Communications in Mathematical Physics"},{"key":"1_CR17","unstructured":"Berry, D.W., Childs, A.: The quantum query complexity of implementing black-box unitary transformations, arxiv:0910.4157"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/3-540-44750-4_34","volume-title":"Advances in Cryptology - CRYPTO \u201995","author":"D. Boneh","year":"1995","unstructured":"Boneh, D., Lipton, R.: Quantum cryptanalysis of hidden linear functions (extended abstract). In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol.\u00a0963, pp. 424\u2013437. Springer, Heidelberg (1995)"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"Buhrman, H., \u0160palek, R.: Quantum verification of matrix products. In: Proceedings of SODA 2006, pp. 880\u2013889 (2006), quant-ph\/0409035","DOI":"10.1145\/1109557.1109654"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science\u00a0288, 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Brassard, G., H\u00f8yer, P., Mosca, M., Tapp, A.: Quantum amplitude amplification and estimation. In: Quantum Computation and Quantum Information Science. AMS Contemporary Mathematics Series, vol.\u00a0305, pp. 53\u201374 (2002), quant-ph\/0005055","DOI":"10.1090\/conm\/305\/05215"},{"key":"1_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/BFb0054319","volume-title":"LATIN\u201998: Theoretical Informatics","author":"G. Brassard","year":"1998","unstructured":"Brassard, G., H\u00f8yer, P., Tapp, A.: Quantum cryptanalysis of hash and claw-free functions. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol.\u00a01380, pp. 163\u2013169. Springer, Heidelberg (1998), quant-ph\/9705002"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/BFb0055105","volume-title":"Automata, Languages and Programming","author":"G. Brassard","year":"1998","unstructured":"Brassard, G., H\u00f8yer, P., Tapp, A.: Quantum counting. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 820\u2013831. Springer, Heidelberg (1998), quant-ph\/9805082"},{"key":"1_CR24","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"J.R. Bunch","year":"1974","unstructured":"Bunch, J.R., Hopcroft, J.E.: Triangular factorization and inversion by fast matrix multiplication. Mathematics of Computation\u00a028, 231\u2013236 (1974)","journal-title":"Mathematics of Computation"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/s00220-009-0930-1","volume":"294","author":"A. Childs","year":"2010","unstructured":"Childs, A.: On the relationship between continuous- and discrete-time quantum walk. Communications in Mathematical Physics\u00a0294, 581\u2013603 (2010), arXiv:0810.0312","journal-title":"Communications in Mathematical Physics"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"Childs, A.M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., Spielman, D.A.: Exponential algorithmic speedup by quantum walk. In: Proceedings of STOC 2003, pp. 59\u201368 (2003), quant-ph\/0209131","DOI":"10.1145\/780542.780552"},{"key":"1_CR27","unstructured":"Childs, A., Reichardt, B., \u0160palek, R., Zhang, S.: Every NAND formula on N variables can be evaluated in time O(N 1\/2\u2009+\u2009\u03b5 ), quant-ph\/0703015, version v1 (March 2, 2007)"},{"issue":"3","key":"1_CR28","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation\u00a09(3), 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"van Dam, W., Mosca, M., Vazirani, U.: How Powerful is Adiabatic Quantum Computation? In: Proceedings of FOCS 2001, pp. 279\u2013287 (2001)","DOI":"10.1109\/SFCS.2001.959902"},{"key":"1_CR30","unstructured":"D-Wave Systems, http:\/\/www.dwavesys.com"},{"key":"1_CR31","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1126\/science.1057726","volume":"292","author":"E. Farhi","year":"2001","unstructured":"Farhi, E., Goldstone, J., Gutman, S., Sipser, M.: A quantum adiabatic algorithm applied to random instances of an NP-complete problem. Science\u00a0292, 472\u2013476 (2001), quant-ph\/0104129","journal-title":"Science"},{"key":"1_CR32","doi-asserted-by":"publisher","first-page":"169","DOI":"10.4086\/toc.2008.v004a008","volume":"4","author":"E. Farhi","year":"2008","unstructured":"Farhi, E., Goldstone, J., Gutman, S.: A Quantum Algorithm for the Hamiltonian NAND Tree. Theory of Computing\u00a04, 169\u2013190 (2008), quant-ph\/0702144","journal-title":"Theory of Computing"},{"key":"1_CR33","volume-title":"Matrix Computations","author":"G. Golub","year":"1996","unstructured":"Golub, G., van Loan, C.: Matrix Computations, 3rd edn. John Hopkins University Press, Baltimore (1996)","edition":"3"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proceedings of STOC 1996, pp. 212\u2013219 (1996), quant-ph\/9605043","DOI":"10.1145\/237814.237866"},{"key":"1_CR35","doi-asserted-by":"crossref","unstructured":"Hallgren, S.: Polynomial-time quantum algorithms for Pell\u2019s equation and the principal ideal problem. Journal of the ACM\u00a054(1) (2007)","DOI":"10.1145\/1206035.1206039"},{"key":"1_CR36","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"A. Harrow","year":"2008","unstructured":"Harrow, A., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Physical Review Letters\u00a0103, 150502 (2008), arXiv:0907.3920","journal-title":"Physical Review Letters"},{"key":"1_CR37","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"R. Horn","year":"1985","unstructured":"Horn, R., Johnson, C.: Matrix Analysis. Cambridge University Press, Cambridge (1985)"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"H\u00f8yer, P., Lee, T., \u0160palek, R.: Negative weights make adversaries stronger. In: Proceedings of STOC 2007, pp. 526\u2013535 (2007), quant-ph\/0611054","DOI":"10.1145\/1250790.1250867"},{"key":"1_CR39","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/5992.909000","volume":"3","author":"R. Jozsa","year":"2001","unstructured":"Jozsa, R.: Quantum factoring, discrete logarithms, and the hidden subgroup problem. Computing in Science and Engineering\u00a03, 34\u201343 (2001), quant-ph\/0012084","journal-title":"Computing in Science and Engineering"},{"key":"1_CR40","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On Span Programs. In: Structure in Complexity Theory Conference 1993, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"issue":"4","key":"1_CR41","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1080\/00107151031000110776","volume":"44","author":"J. Kempe","year":"2003","unstructured":"Kempe, J.: Quantum random walks - an introductory overview. Contemporary Physics\u00a044(4), 307\u2013327 (2003), quant-ph\/0303081","journal-title":"Contemporary Physics"},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Krovi, H., Magniez, F., Ozols, M., Roland, J.: Finding is as easy as detecting for quantum walks. In: Proceedings of ICALP (to appear, 2010), arxiv:1002.2419","DOI":"10.1007\/978-3-642-14165-2_46"},{"issue":"1","key":"1_CR43","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1137\/050639090","volume":"38","author":"S. Laplante","year":"2008","unstructured":"Laplante, S., Magniez, F.: Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. SIAM Journal on Computing\u00a038(1), 46\u201362 (2008), Also CCC 2004 and quant-ph\/0311189","journal-title":"SIAM Journal on Computing"},{"key":"1_CR44","doi-asserted-by":"crossref","unstructured":"Magniez, F., Nayak, A., Roland, J., Santha, M.: Search via quantum walk. In: Proceedings of STOC 2007, pp. 575\u2013584 (2007), quant-ph\/0608026","DOI":"10.1145\/1250790.1250874"},{"issue":"2","key":"1_CR45","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/050643684","volume":"37","author":"F. Magniez","year":"2007","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM Journal on Computing\u00a037(2), 413\u2013424 (2007), quant-ph\/0310134","journal-title":"SIAM Journal on Computing"},{"key":"1_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-49208-9_15","volume-title":"Quantum Computing and Quantum Communications","author":"M. Mosca","year":"1999","unstructured":"Mosca, M., Ekert, A.: The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In: Williams, C.P. (ed.) QCQC 1998. LNCS, vol.\u00a01509, pp. 174\u2013188. Springer, Heidelberg (1999), quant-ph\/9903071"},{"key":"1_CR47","doi-asserted-by":"crossref","unstructured":"Nayak, A., Wu, F.: The quantum query complexity of approximating the median and related statistics. In: Proceedings of STOC 1999, pp. 384\u2013393 (1999), quant-ph\/9804066","DOI":"10.1145\/301250.301349"},{"key":"1_CR48","unstructured":"Reichardt, B.: Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function. In: Proceedings of FOCS (2009), arXiv:0904.2759"},{"key":"1_CR49","unstructured":"Reichardt, B.: Span-program-based quantum algorithm for evaluating unbalanced formulas, arXiv:09071622"},{"key":"1_CR50","unstructured":"Reichardt, B.: Faster quantum algorithm for evaluating game trees, arXiv:0907.1623"},{"key":"1_CR51","unstructured":"Reichardt, B.: Reflections for quantum query algorithms, arxiv:1005.1601"},{"key":"1_CR52","doi-asserted-by":"crossref","unstructured":"Reichardt, B., \u0160palek, R.: Span-program-based quantum algorithm for evaluating formulas. In: Proceedings of STOC 2008, pp. 103\u2013112 (2008), arXiv:0710.2630","DOI":"10.1145\/1374376.1374394"},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"Saks, M., Wigderson, A.: Probabilistic Boolean decision trees and the complexity of evaluating game trees. In: Proceedings of FOCS 1986, pp. 29\u201338 (1986)","DOI":"10.1109\/SFCS.1986.44"},{"key":"1_CR54","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-79228-4_3","volume-title":"Theory and Applications of Models of Computation","author":"M. Santha","year":"2008","unstructured":"Santha, M.: Quantum walk based search algorithms. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol.\u00a04978, pp. 31\u201346. Springer, Heidelberg (2008), arXiv:0808.0059"},{"key":"1_CR55","unstructured":"Shewchuk, J.: An introduction to the conjugate gradient method without the agonizing pain. Technical Report CMU-CS-94-125, School of Computer Science, Carnegie Mellon University (1994)"},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"Shor, P.: Algorithms for Quantum Computation: Discrete Logarithms and Factoring. In: Proceedings of FOCS 1994, pp. 124\u2013134 (1994), quant-ph\/9508027","DOI":"10.1109\/SFCS.1994.365700"},{"key":"1_CR57","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0304-3975(85)90210-5","volume":"38","author":"M. Snir","year":"1985","unstructured":"Snir, M.: Lower bounds on probabilistic linear decision trees. Theoretical Computer Science\u00a038, 69\u201382 (1985)","journal-title":"Theoretical Computer Science"},{"key":"1_CR58","doi-asserted-by":"crossref","unstructured":"Szegedy, M.: Quantum speed-up of Markov chain based algorithms. In: Proceedings of FOCS 2004, pp. 32\u201341 (2004)","DOI":"10.1109\/FOCS.2004.53"},{"key":"1_CR59","doi-asserted-by":"publisher","first-page":"12310","DOI":"10.1103\/PhysRevA.78.012310","volume":"78","author":"T.A. Tulsi","year":"2008","unstructured":"Tulsi, T.A.: Faster quantum walk algorithm for the two dimensional spatial search. Physical Review A\u00a078, 012310 (2008), arXiv:0801.0497","journal-title":"Physical Review A"},{"key":"1_CR60","doi-asserted-by":"crossref","unstructured":"Venegas-Andrade, S.E.: Quantum Walks for Computer Scientists. Morgan and Claypool (2008)","DOI":"10.2200\/S00144ED1V01Y200808QMC001"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:31Z","timestamp":1606186891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":60,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}