{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T14:06:22Z","timestamp":1780581982698,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540407706","type":"print"},{"value":"9783540451983","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45198-3_30","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:32:30Z","timestamp":1294439550000},"page":"354-369","source":"Crossref","is-referenced-by-count":66,"title":["Discrete Quantum Walks Hit Exponentially Faster"],"prefix":"10.1007","author":[{"given":"Julia","family":"Kempe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"30_CR1","first-page":"50","volume-title":"Proc. 33th STOC","author":"D. Aharonov","year":"2001","unstructured":"Aharonov, D., Ambainis, A., Kempe, J., Vazirani, U.: Quantum walks on graphs. In: Proc. 33th STOC, pp. 50\u201359. ACM Press, New York (2001)"},{"key":"30_CR2","first-page":"60","volume-title":"Proc. 33th STOC","author":"A. Ambainis","year":"2001","unstructured":"Ambainis, A., Bach, E., Nayak, A., Vishwanath, A., Watrous, J.: One-dimensional quantum walks. In: Proc. 33th STOC, pp. 60\u201369. ACM, New York (2001)"},{"key":"30_CR3","unstructured":"Aldous, D., Fill, J.: Reversible markov chains and random walks on graphs, Unpublished, preprint available at http:\/\/statwww.berkeley.edu\/users\/aldous\/RWG\/book.html (2001)"},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. Siam Journal on Computing\u00a026(1510) (1997)","DOI":"10.1137\/S0097539796300933"},{"key":"30_CR5","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: Proc. 35th STOC (2003) (to appear)","DOI":"10.1145\/780542.780552"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Childs, A., Farhi, E., Gutmann, S.: An example of the difference between quantum and classical random walks. Quantum Information Processing\u00a01(35) (2002)","DOI":"10.1023\/A:1019609420309"},{"issue":"1","key":"30_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/102782.102783","volume":"38","author":"M. Dyer","year":"1991","unstructured":"Dyer, M., Frieze, A., Kannan, R.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM\u00a038(1), 1\u201317 (1991)","journal-title":"Journal of the ACM"},{"key":"30_CR8","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1103\/PhysRevA.58.915","volume":"58","author":"E. Farhi","year":"1998","unstructured":"Farhi, E., Gutmann, S.: Quantum computation and decision trees. Phys. Rev. A.\u00a058, 915\u2013928 (1998)","journal-title":"Phys. Rev. A."},{"key":"30_CR9","first-page":"212","volume-title":"Proc. 28th STOC","author":"L. Grover","year":"1996","unstructured":"Grover, L.: A fast quantum mechanical algorithm for database search. In: Proc. 28th STOC, Philadelphia, Pennsylvania, pp. 212\u2013219. ACM, New York (1996)"},{"key":"30_CR10","first-page":"68","volume-title":"Proc. 33th STOC","author":"M. Grigni","year":"2001","unstructured":"Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.: Strengths and weaknesses of quantum computing. Siam Journal on Computing\u00a026(1510) (1997)"},{"key":"30_CR11","doi-asserted-by":"crossref","unstructured":"Hallgren, S., Russell, A., Ta-Shma, A.: Normal subgroup reconstruction and quantum computation using group representations. In: Proc. 32nd STOC, pp. 627\u2013635 (2000)","DOI":"10.1145\/335305.335392"},{"issue":"1","key":"30_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/0890-5401(89)90067-9","volume":"82","author":"M. Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation\u00a082(1), 93\u2013133 (1989)","journal-title":"Information and Computation"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1007\/BF02199356","volume":"85","author":"D. Meyer","year":"1996","unstructured":"Meyer, D.: From quantum cellular automata to quantum lattice gases. J. Stat. Phys.\u00a085, 551\u2013574 (1996)","journal-title":"J. Stat. Phys."},{"key":"30_CR14","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/3-540-45726-7_14","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"C. Moore","year":"2002","unstructured":"Moore, C., Russell, A.: Quantum walks on the hypercube. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 164\u2013178. Springer, Heidelberg (2002)"},{"key":"30_CR16","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000)"},{"key":"30_CR17","volume-title":"Computational Complexity.","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: RANDOM 2002. Addison Wesley, Reading (1994)"},{"key":"30_CR18","first-page":"410","volume-title":"Proc. 40th FOCS","author":"U. Sch\u00f6ning","year":"1999","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-SAT and constraint satisfaction problems. In: Proc. 40th FOCS, pp. 410\u2013414. IEEE, Los Alamitos (1999)"},{"issue":"5","key":"30_CR19","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comp.\u00a026(5), 1484\u20131509 (1997)","journal-title":"SIAM J. Comp."},{"issue":"5","key":"30_CR20","doi-asserted-by":"publisher","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"D. Simon","year":"1997","unstructured":"Simon, D.: On the power of quantum computation. SIAM J. Comp.\u00a026(5), 1474\u20131483 (1997)","journal-title":"SIAM J. Comp."},{"issue":"5","key":"30_CR21","doi-asserted-by":"publisher","first-page":"52307","DOI":"10.1103\/PhysRevA.67.052307","volume":"67","author":"N. Shenvi","year":"2003","unstructured":"Shenvi, N., Kempe, J., Whaley, K.B.: A quantum random walk search algorithm. Phys. Rev. A\u00a067(5), 52307 (2003)","journal-title":"Phys. Rev. A"},{"issue":"2","key":"30_CR22","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1006\/jcss.2000.1732","volume":"62","author":"J. Watrous","year":"2001","unstructured":"Watrous, J.: Quantum simulations of classical random walks and undirected graph connectivity. Journal of Computer and System Sciences\u00a062(2), 376\u2013391 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR23","unstructured":"Yamasaki, T.: personal communication (2001)"},{"key":"30_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/3-540-45833-6_26","volume-title":"Unconventional Models of Computation","author":"T. Yamasaki","year":"2002","unstructured":"Yamasaki, T., Kobayashi, H., Imai, H.: An analysis of absorbing times of quantum walks. In: Calude, C.S., Dinneen, M.J., Peper, F. (eds.) UMC 2002. LNCS, vol.\u00a02509, pp. 315\u2013330. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45198-3_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T14:05:19Z","timestamp":1559916319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45198-3_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540407706","9783540451983"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45198-3_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003]]}}}