Efficient discrete-time simulations of continuous-time quantum query algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficient discrete-time simulations of continuous-time quantum query algorithms

Full text

Pdf (503 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

SESSION: Quantum table of contents

Pages 409-416

Year of Publication: 2009

ISBN:978-1-60558-506-2

Authors

Richard Cleve	University of Waterloo and Perimeter Institute, Waterloo, ON, Canada
Daniel Gottesman	Perimeter Institute, Waterloo, ON, Canada
Michele Mosca	University of Waterloo and Perimeter Institute, Waterloo, ON, Canada
Rolando D. Somma	Perimeter Institute, Waterloo, ON, Canada
David Yonge-Mallo	University of Waterloo, Waterloo, ON, Canada

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 48, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/1536414.1536471 What is a DOI?

ABSTRACT

The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuously in time. We show that any quantum algorithm in this model whose total query time is T can be simulated by a quantum algorithm in the discrete-time query model that makes O(T log T / loglog T) subset O~(T) queries. This is the first such upper bound that is independent of the driving operations (i.e., it holds even if the norm of the driving Hamiltonian is very large). A corollary is that any lower bound of T queries for a problem in the discrete-time query model immediately carries over to a lower bound of Omega(T loglog T / log T) subset Omega~(T) in the continuous-time query model.

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	Andris Ambainis, Quantum Walk Algorithm for Element Distinctness, SIAM Journal on Computing, v.37 n.1, p.210-239, April 2007 [doi>10.1137/S0097539705447311]
	2	Andris Ambainis , Andrew M. Childs , Ben W. Reichardt , Robert Spalek , Shengyu Zhang, Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.363-372, October 21-23, 2007 [doi>10.1109/FOCS.2007.10]
	3	D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics, 270:359--371 (2007).
	4	G. Brassard, P. Hoyer, and A. Tapp, Quantum algorithm for the collision problem, ACM SIGACT News (Cryptology Column), 28:14--19 (1997).
	5	Andrew Macgregor Childs , Edward H. Farhi, Quantum information processing in continuous time, Massachusetts Institute of Technology, 2004
	6	A. M. Childs, On the relationship between continuous- and discrete-time quantum walk, arXiv:0810.0312 (2008).
	7	Andrew M. Childs , Richard Cleve , Enrico Deotto , Edward Farhi , Sam Gutmann , Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780552]
	8	A. M. Childs, R. Cleve, S. P. Jordan, and D. Yeung, Discrete query quantum algorithm for NAND trees, arXiv:0702160 (2007).
	9	Wim van Dam, Quantum Oracle Interrogation: Getting All Information for Almost Half the Price, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.362, November 08-11, 1998
	10	E. Farhi, J. Goldstone, and S. Gutmann, A quantum algorithm for the Hamiltonian NAND tree, Theory of Computing, 4(8):169--190 (2008).
	11	E. Farhi and S. Gutmann, Analog analogue of a digital quantum computation, Physical Review A, 57:2403--2406 (1998).
	12	E. Farhi and S. Gutmann, Quantum computation and decision trees, Physical Review A, 58:915--928 (1998).
	13	L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack, Physical Review Letters, 79:325--328 (1997).
	14	J. Huyghebaert and H. De Raedt, Product formula methods for time-dependent Schroedinger problems, J. Physics A: Mathematical and General, 23:5777--5793 (1990).
	15	Phillip Kaye , Raymond Laflamme , Michele Mosca, An Introduction to Quantum Computing, Oxford University Press, Inc., New York, NY, 2007
	16	C. Mochon, Hamiltonian oracles, Physical Review A, 75:042313 {15 pages} (2007).
	17	L. Sheridan, D. Maslov, and M. Mosca, Approximating fractional time quantum evolution, arXiv:0810.3843 (2008).
	18	Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
	19	M. Suzuki, Quantum Monte Carlo Methods in Condensed-Matter Physics (World Scientific, Singapore, 1993).