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].