Search via quantum walk

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Search via quantum walk

Full text

Pdf (276 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing table of contents

San Diego, California, USA

SESSION: Session 11B table of contents

Pages: 575 - 584

Year of Publication: 2007

ISBN:978-1-59593-631-8

Authors

Frederic Magniez	Universite Paris-Sud: CNRS, Orsay, France
Ashwin Nayak	University of Waterloo: and Perimeter Institute, Waterloo, ON, Canada
Jeremie Roland	University of California - Berkeley, Berkeley, CA
Miklos Santha	Universite Paris-Sud: CNRS, Orsay, France

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 118, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTex EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1250790.1250874 What is a DOI?

ABSTRACT

We propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical Markovchain. The algorithm is based on a quantum walk à la Szegedy [25] that is defined in terms of the Markov chain. The main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. Thisoperatoris then used in an amplitude amplification scheme. As a result weconsiderably expand the scope of the previous approaches ofAmbainis [6] and Szegedy [25]. Our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of Markov chain. In addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Scott Aaronson , Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems, Journal of the ACM (JACM), v.51 n.4, p.595-605, July 2004 [doi>10.1145/1008731.1008735]
	2	S. Aaronson and A. Ambainis. Quantum search of spatial regions. Theory of Computing, 1:47--79, 2005.
	3	Dorit Aharonov , Andris Ambainis , Julia Kempe , Umesh Vazirani, Quantum walks on graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.50-59, July 2001, Hersonissos, Greece [doi>10.1145/380752.380758]
	4	D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. http://www.stat.berkeley.edu/~aldous/RWG/book.html. Monograph in preparation, August 2006 version.
	5	Andris Ambainis , Julia Kempe , Alexander Rivosh, Coins make quantum walks faster, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	6	Andris Ambainis, Quantum Walk Algorithm for Element Distinctness, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.22-31, October 17-19, 2004 [doi>10.1109/FOCS.2004.54]
	7	Andris Ambainis , Eric Bach , Ashwin Nayak , Ashvin Vishwanath , John Watrous, One-dimensional quantum walks, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.37-49, July 2001, Hersonissos, Greece [doi>10.1145/380752.380757]
	8	Charles H. Bennett , Ethan Bernstein , Gilles Brassard , Umesh Vazirani, Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing, v.26 n.5, p.1510-1523, Oct. 1997 [doi>10.1137/S0097539796300933]
	9	M. Boyer, G. Brassard, P. Hoyer, and A. Tapp. Tight bounds on quantum searching. Fortschritte Der Physik, 46(4-5):493--505, 1998.
	10	G. Brassard, P. Hoyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. In Jr. Samuel J. Lomonaco and Howard E. Brandt, editors, Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics Series. American Mathematical Society, 2002.
	11	A. Broder and A. Karlin. Bounds on the cover time. Journal of Theoretical Probability, 2(1):101--120, 1989.
	12	Harry Buhrman , Christoph Dürr, Quantum Algorithms for Element Distinctness, SIAM Journal on Computing, v.34 n.6, p.1324-1330, 2005 [doi>10.1137/S0097539702402780]
	13	Harry Buhrman , Robert Špalek, Quantum verification of matrix products, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.880-889, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109654]
	14	A. Childs and J. Goldstone. Spatial search and the Dirac equation. Physical Review A, 70, 2004. Article No. 42312.
	15	R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca. Quantum algorithms revisited. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 454(1969):339--354, 1998.
	16	Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.212-219, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237866]
	17	P. Hoyer, M. Mosca, and R. de Wolf. Quantum search on bounded-error inputs. In Verlag, editor, Proceedings of the 30th International Colloquium on Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 291--299. Verlag, 2003.
	18	A. Kitaev. Quantum measurements and the abelian stabilizer problem. Technical Report quant-ph/9511026, arXiv, 1995.
	19	F. Magniez and A. Nayak. Quantum complexity of testing group commutativity. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, volume 1770 of Lecture Notes in Computer Science, pages 1312--1324, 2005.
	20	Frédéric Magniez , Miklos Santha , Mario Szegedy, Quantum algorithms for the triangle problem, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	21	D. Meyer. From quantum cellular automata to quantum lattice gases. Journal of Statistical Physics, 85(5-6):551--574, 1996.
	22	Nayak Ashwin , Vishwanath Ashvin, Quantum Walk on the Line, Certer for Discrete Mathematics & Theoretical Computer Science, 2000
	23	P. Richter. Almost uniform sampling via quantum walks. New Journal of Physics, 2007. To appear.
	24	N. Shenvi, J. Kempe, and K.B. Whaley. Quantum random-walk search algorithm. Physical Review A, 67(052307), 2003.
	25	Mario Szegedy, Quantum Speed-Up of Markov Chain Based Algorithms, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.32-41, October 17-19, 2004 [doi>10.1109/FOCS.2004.53]
	26	U. Vazirani. On the power of quantum computation. Philosophical Transactions of the Royal Society of London, Series A, 356:1759--1768, 1998.
	27	John Watrous, Quantum simulations of classical random walks and undirected graph connectivity, Journal of Computer and System Sciences, v.62 n.2, p.376-391, March 2001 [doi>10.1006/jcss.2000.1732 ]