@string(stoc="Proc. ACM STOC")
@string(focs="Proc. IEEE FOCS")
@string(ccc="Proc. IEEE Conference on Computational Complexity")
@string(soda="Proc. ACM-SIAM Symp. on Discrete Algorithms (SODA)")
@string(stacs="Proc. Intl. Symp. on Theoretical Aspects of Computer Science (STACS)")
@string(icalp="Proc. Intl. Colloquium on Automata, Languages, and Programming (ICALP)")
@string(prl="Phys. Rev. Lett.")
@string(pra="Phys. Rev. A")
@string(prd="Phys. Rev. D")
@string(qic="Quantum Information and Computation")
@string(sicomp="SIAM J. Comput.")
@string(jacm="J. ACM")
@string(jcss="J. Comput. Sys. Sci.")
@string(tcs="Theoretical Comput. Sci.")
@string(toc="Theory of Computing")
@string(prs="Proc. Roy. Soc. London")
@string(pnas="Proc. Nat. Acad. of Sciences (USA)")
@string(ipl="Inform. Proc. Lett.")
@string(lncs="Lecture Notes in Computer Science")
@string(springer="Springer-Verlag")
@string(jhep="J. High Energy Phys.")
@string(cqg="Classical and Quantum Gravity")

@inproceedings{aakv,
   author = {D. Aharonov and A. Ambainis and J. Kempe and U. Vazirani},
   title = {Quantum walks on graphs},
   booktitle = stoc,
   pages = {50-59},
   year = {2001},
   eprint = {stoc:380752.380758,arxiv:quant-ph/0012090}
}

@article{ambainis,
   author = {A. Ambainis},
   title = {Quantum lower bounds by quantum arguments},
   journal = jcss,
   volume = 64,
   pages = {750-767},
   year = 2002,
   eprint = {jcss:10.1006/jcss.2002.1826,stoc:335305.335394,arxiv:quant-ph/0002066},
}

@inproceedings{akr,
   author = {A. Ambainis and J. Kempe and A. Rivosh},
   title = {Coins make quantum walks faster},
   booktitle = soda,
   year = {2005},
   note = {To appear.},
   eprint = {arxiv:quant-ph/0402107}
}

@article{bbcmw,
   author = {R. Beals and H. Buhrman and R. Cleve and M. Mosca and Wolf, R. de},
   title = {Quantum lower bounds by polynomials},
   journal = jacm,
   volume = 48,
   number = 4,
   pages = {778-797},
   year = 2001,
   note = {Earlier version in IEEE FOCS 1998.},
   eprint = {jacm:502090.502097,focs:10.1109/SFCS.1998.743485,arxiv:quant-ph/9802049}
}

@article{bekenstein,
   author = {J. D. Bekenstein},
   title = {A universal upper bound on the entropy to energy ratio for bounded systems},
   journal = prd,
   volume = {23},
   number = {2},
   pages = {287-298},
   year = {1981},
   eprint = {prd:10.1103/PhysRevD.23.287}
}

@incollection{benioff:robot,
   author = {P. Benioff},
   title = {Space searches with a quantum robot},
   booktitle = {Quantum Computation and Information},
   series = {Contemporary Mathematics Series},
   publisher = {AMS},
   editor = {S. J. Lomonaco and H. E. Brandt},
   year = {2002},
   eprint = {arxiv:quant-ph/0003006}
}

@article{bbbv,
   author = {C. Bennett and E. Bernstein and G. Brassard and U. Vazirani},
   title = {Strengths and weaknesses of quantum computing},
   journal = sicomp,
   volume = {26},
   number = {5},
   pages = {1510-1523},
   year = {1997},
   eprint = {sicomp:30093,arxiv:quant-ph/9701001}
}

@article{bousso:vac,
   author = {R. Bousso},
   title = {Positive vacuum energy and the {N}-bound},
   journal = jhep,
   volume = {0011},
   number = {038},
   year = {2000},
   eprint = {arxiv:hep-th/0010252}
}

@article{bousso,
   author = {R. Bousso},
   title = {The holographic principle},
   journal = {Reviews of Modern Physics},
   volume = {74},
   number = {3},
   year = {2002},
   eprint = {arxiv:hep-th/0203101}
}

@article{bbht,
   author = {M. Boyer and G. Brassard and P. H{\o}yer and A. Tapp},
   title = {Tight bounds on quantum searching},
   journal = {Fortschritte Der Physik},
   volume = {46},
   number = {4-5},
   pages = {493-505},
   year = {1998},
   eprint = {arxiv:quant-ph/9605034}
}

@incollection{bhmt,
   author = {G. Brassard and P. H{\o}yer and M. Mosca and A. Tapp},
   title = {Quantum amplitude amplification and estimation},
   booktitle = {Quantum Computation and Information},
   series = {Contemporary Mathematics Series},
   publisher = {AMS},
   editor = {S. J. Lomonaco and H. E. Brandt},
   year = {2002},
   eprint = {arxiv:quant-ph/0005055}
}

@inproceedings{bcw,
   author = {H. Buhrman and R. Cleve and A. Wigderson},
   title = {Quantum vs. classical communication and computation},
   booktitle = stoc,
   pages = {63-68},
   year = {1998},
   eprint = {stoc:276698.276713,arxiv:quant-ph/9702040}
}

@inproceedings{ccdfgs,
   author = {A. M. Childs and R. Cleve and E. Deotto and E. Farhi and S. Gutmann and D. A. Spielman},
   title = {Exponential algorithmic speedup by quantum walk},
   booktitle = stoc,
   pages = {59-68},
   year = {2003},
   eprint = {stoc:780542.780552,arxiv:quant-ph/0209131}
}

@article{cfg,
   author = {A. M. Childs and E. Farhi and S. Gutmann},
   title = {An example of the difference between quantum and classical random walks},
   journal = qic,
   volume = {1},
   number = {1-2},
   pages = {35-43},
   year = {2002},
   eprint = {arxiv:quant-ph/0103020}
}

@article{cg,
   author = {A. M. Childs and J. Goldstone},
   title = {Spatial search by quantum walk},
   journal = pra,
   volume = {70},
   number = {022314},
   year = {2004},
   eprint = {pra:10.1103/PhysRevA.70.022314,arxiv:quant-ph/0306054}
}

@article{cg2,
   author = {A. M. Childs and J. Goldstone},
   title = {Spatial search and the {D}irac equation},
   journal = pra,
   volume = {70},
   number = {042312},
   year = {2004},
   eprint = {pra:10.1103/PhysRevA.70.042312,arxiv:quant-ph/0405120}
}

@inproceedings{grover,
   author = {L. K. Grover},
   title = {A fast quantum mechanical algorithm for database search},
   booktitle = stoc,
   pages = {212-219},
   year = {1996},
   eprint = {stoc:237814.237866,arxiv:quant-ph/9605043}
}

@inproceedings{grover:framework,
   author = {L. K. Grover},
   title = {A framework for fast quantum mechanical algorithms},
   booktitle = stoc,
   pages = {53-62},
   year = {1998},
   eprint = {stoc:276698.276712,arxiv:quant-ph/9711043}
}

@article{grover:prl,
   author = {L. K. Grover},
   title = {Quantum mechanics helps in searching for a needle in a haystack},
   journal = prl,
   volume = {79},
   number = {2},
   pages = {325-328},
   year = {1997},
   eprint = {prl:10.1103/PhysRevLett.79.325,arxiv:quant-ph/9706033}
}

@inproceedings{hoyerdewolf,
   author = {P. H{\o}yer and Wolf, R. de},
   title = {Improved quantum communication complexity bounds for disjointness and equality},
   booktitle = stacs,
   pages = {299-310},
   year = {2002},
   eprint = {stacs:c22a2t8cewg784jh,arxiv:quant-ph/0109068}
}

@article{lloyd,
   author = {S. Lloyd},
   title = {Computational capacity of the universe},
   journal = prl,
   volume = {88},
   year = {2002},
   eprint = {prl:10.1103/PhysRevLett.88.237901,arxiv:quant-ph/0110141}
}

@book{nc,
   author = {M. Nielsen and I. Chuang},
   title = {Quantum Computation and Quantum Information},
   publisher = {Cambridge University Press},
   year = {2000}
}

@article{perlmutter,
   author = {{S. Perlmutter and 32 others (Supernova Cosmology Project)}},
   title = {Measurements of {$\Omega$} and {$\Lambda$} from 42 high-redshift supernovae},
   journal = {Astrophysical Journal},
   volume = {517},
   number = {2},
   pages = {565-586},
   year = {1999},
   eprint = {arxiv:astro-ph/9812133}
}

@article{razborov:cc,
   author = {A. A. Razborov},
   title = {Quantum communication complexity of symmetric predicates},
   journal = {Izvestiya Math. (English version)},
   volume = {67},
   number = {1},
   pages = {145-159},
   year = {2003},
   eprint = {arxiv:quant-ph/0204025}
}

@unpublished{rg,
   author = {T. Rudolph and L. Grover},
   title = {Quantum searching a classical database (or how we learned to stop worrying and love the bomb)},
   year = {2002},
   eprint = {arxiv:quant-ph/0206066}
}

@book{ryden,
   author = {B. S. Ryden},
   title = {Introduction to Cosmology},
   publisher = {Addison-Wesley},
   year = {2002}
}

@article{sv,
   author = {A. Sahai and S. Vadhan},
   title = {A complete promise problem for statistical zero-knowledge},
   journal = jacm,
   volume = {50},
   number = {2},
   pages = {196-249},
   year = {2003},
   note = {Earlier version in IEEE FOCS 1997},
   eprint = {jacm:636865.636868,focs:10.1109/SFCS.1997.646133,ECCC:TR00-084}
}

@article{skw,
   author = {N. Shenvi and J. Kempe and K. B. Whaley},
   title = {A quantum random walk search algorithm},
   journal = pra,
   volume = {67},
   number = {5},
   year = {2003},
   eprint = {pra:10.1103/PhysRevA.67.052307,arxiv:quant-ph/0210064}
}

@article{shor,
   author = {P. Shor},
   title = {Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer},
   journal = sicomp,
   volume = {26},
   number = {5},
   pages = {1484-1509},
   year = {1997},
   note = {Earlier version in IEEE FOCS 1994.},
   eprint = {sicomp:29317,focs:10.1109/SFCS.1994.365700,arxiv:quant-ph/9508027}
}

@article{strassen,
   author = {V. Strassen},
   title = {Gaussian elimination is not optimal},
   journal = {Numerische Mathematik},
   volume = {14},
   number = {13},
   pages = {354-356},
   year = {1969}
}

@inproceedings{watrous:ca,
   author = {J. Watrous},
   title = {On one-dimensional quantum cellular automata},
   booktitle = focs,
   pages = {528-537},
   year = 1995,
   eprint = {focs:10.1109/SFCS.1995.492583}
}

@unpublished{zalka,
   author = {Ch. Zalka},
   title = {Could {G}rover's algorithm help in searching an actual database?},
   year = {1999},
   eprint = {arxiv:quant-ph/9901068}
}