Quantum Search of Spatial Regions

by Scott Aaronson and Andris Ambainis

Theory of Computing, Volume 1(4), pp. 47-79, 2005

Bibliography with links to cited articles

[1]   D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani: Quantum walks on graphs. In Proc. ACM STOC, pp. 50–59, 2001. [STOC:380752.380758, arXiv:quant-ph/0012090].

[2]   A. Ambainis: Quantum lower bounds by quantum arguments. J. Comput. Sys. Sci., 64:750–767, 2002. [JCSS:10.1006/jcss.2002.1826, STOC:335305.335394, arXiv:quant-ph/0002066].

[3]   A. Ambainis, J. Kempe, and A. Rivosh: Coins make quantum walks faster. In Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2005. To appear. [arXiv:quant-ph/0402107].

[4]   R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf: Quantum lower bounds by polynomials. J. ACM, 48(4):778–797, 2001. Earlier version in IEEE FOCS 1998. [JACM:502090.502097, FOCS:10.1109/SFCS.1998.743485, arXiv:quant-ph/9802049].

[5]   J. D. Bekenstein: A universal upper bound on the entropy to energy ratio for bounded systems. Phys. Rev. D, 23(2):287–298, 1981. [PRD:10.1103/PhysRevD.23.287].

[6]   P. Benioff: Space searches with a quantum robot. In S. J. Lomonaco and H. E. Brandt, editors, Quantum Computation and Information, Contemporary Mathematics Series. AMS, 2002. [arXiv:quant-ph/0003006].

[7]    C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani: Strengths and weaknesses of quantum computing. SIAM J. Comput., 26(5):1510–1523, 1997. [SICOMP:30093, arXiv:quant-ph/9701001].

[8]   R. Bousso: Positive vacuum energy and the N-bound. J. High Energy Phys., 0011(038), 2000. [arXiv:hep-th/0010252].

[9]   R. Bousso: The holographic principle. Reviews of Modern Physics, 74(3), 2002. [arXiv:hep-th/0203101].

[10]   M. Boyer, G. Brassard, P. H°yer, and A. Tapp: Tight bounds on quantum searching. Fortschritte Der Physik, 46(4-5):493–505, 1998. [arXiv:quant-ph/9605034].

[11]   G. Brassard, P. H°yer, M. Mosca, and A. Tapp: Quantum amplitude amplification and estimation. In S. J. Lomonaco and H. E. Brandt, editors, Quantum Computation and Information, Contemporary Mathematics Series. AMS, 2002. [arXiv:quant-ph/0005055].

[12]   H. Buhrman, R. Cleve, and A. Wigderson: Quantum vs. classical communication and computation. In Proc. ACM STOC, pp. 63–68, 1998. [STOC:276698.276713, arXiv:quant-ph/9702040].

[13]   A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman: Exponential algorithmic speedup by quantum walk. In Proc. ACM STOC, pp. 59–68, 2003. [STOC:780542.780552, arXiv:quant-ph/0209131].

[14]   A. M. Childs, E. Farhi, and S. Gutmann: An example of the difference between quantum and classical random walks. Quantum Information and Computation, 1(1-2):35–43, 2002. [arXiv:quant-ph/0103020].

[15]   A. M. Childs and J. Goldstone: Spatial search and the Dirac equation. Phys. Rev. A, 70(042312), 2004. [PRA:10.1103/PhysRevA.70.042312, arXiv:quant-ph/0405120].

[16]   A. M. Childs and J. Goldstone: Spatial search by quantum walk. Phys. Rev. A, 70(022314), 2004. [PRA:10.1103/PhysRevA.70.022314, arXiv:quant-ph/0306054].

[17]   L. K. Grover: A fast quantum mechanical algorithm for database search. In Proc. ACM STOC, pp. 212–219, 1996. [STOC:237814.237866, arXiv:quant-ph/9605043].

[18]   L. K. Grover: Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett., 79(2):325–328, 1997. [PRL:10.1103/PhysRevLett.79.325, arXiv:quant-ph/9706033].

[19]   L. K. Grover: A framework for fast quantum mechanical algorithms. In Proc. ACM STOC, pp. 53–62, 1998. [STOC:276698.276712, arXiv:quant-ph/9711043].

[20]   P. H°yer and R. de Wolf: Improved quantum communication complexity bounds for disjointness and equality. In Proc. Intl. Symp. on Theoretical Aspects of Computer Science (STACS), pp. 299–310, 2002. [STACS:c22a2t8cewg784jh, arXiv:quant-ph/0109068].

[21]   S. Lloyd: Computational capacity of the universe. Phys. Rev. Lett., 88, 2002. [PRL:10.1103/PhysRevLett.88.237901, arXiv:quant-ph/0110141].

[22]   M. Nielsen and I. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[23]   A. A. Razborov: Quantum communication complexity of symmetric predicates. Izvestiya Math. (English version), 67(1):145–159, 2003. [arXiv:quant-ph/0204025].

[24]   T. Rudolph and L. Grover: Quantum searching a classical database (or how we learned to stop worrying and love the bomb). 2002. [arXiv:quant-ph/0206066].

[25]   B. S. Ryden: Introduction to Cosmology. Addison-Wesley, 2002.

[26]   S. Perlmutter and 32 others (Supernova Cosmology Project): Measurements of Ω and Λ from 42 high-redshift supernovae. Astrophysical Journal, 517(2):565–586, 1999. [arXiv:astro-ph/9812133].

[27]   A. Sahai and S. Vadhan: A complete promise problem for statistical zero-knowledge. J. ACM, 50(2):196–249, 2003. Earlier version in IEEE FOCS 1997. [JACM:636865.636868, FOCS:10.1109/SFCS.1997.646133, ECCC:TR00-084].

[28]   N. Shenvi, J. Kempe, and K. B. Whaley: A quantum random walk search algorithm. Phys. Rev. A, 67(5), 2003. [PRA:10.1103/PhysRevA.67.052307, arXiv:quant-ph/0210064].

[29]   P. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26(5):1484–1509, 1997. Earlier version in IEEE FOCS 1994. [SICOMP:29317, FOCS:10.1109/SFCS.1994.365700, arXiv:quant-ph/9508027].

[30]   V. Strassen: Gaussian elimination is not optimal. Numerische Mathematik, 14(13):354–356, 1969.

[31]   J. Watrous: On one-dimensional quantum cellular automata. In Proc. IEEE FOCS, pp. 528–537, 1995. [FOCS:10.1109/SFCS.1995.492583].

[32]   Ch. Zalka: Could Grover’s algorithm help in searching an actual database? 1999. [arXiv:quant-ph/9901068].