A nearly optimal discrete query quantum algorithm for evaluating NAND formulas
作者： Andris Ambainis
DOI:
关键词:
摘要: We present an O(\sqrt{N}) discrete query quantum algorithm for evaluating balanced binary NAND formulas and O(N^{{1/2}+O(\frac{1}{\sqrt{\log N}})}) arbitrary formulas.
arxiv.org
harvard.edu
arxiv-vanity.com参考文章(17)
M. Szegedy, Quantum speed-up of Markov chain based algorithms foundations of computer science. pp. 32- 41 ,(2004) , 10.1109/FOCS.2004.53
Peter Høyer, Michele Mosca, Ronald de Wolf, Quantum search on bounded-error inputs international colloquium on automata languages and programming. pp. 291- 299 ,(2003) , 10.1007/3-540-45061-0_25
Andris Ambainis, Quantum lower bounds by quantum arguments symposium on the theory of computing. ,vol. 64, pp. 636- 643 ,(2000) , 10.1145/335305.335394
Artur Ekert, Michele Mosca, Chiara Macchiavello, Richard Cleve, Lea Henderson, On quantum algorithms Complexity. ,vol. 4, pp. 33- 42 ,(1998) , 10.1002/(SICI)1099-0526(199809/10)4:1<33::AID-CPLX10>3.3.CO;2-L
Edward Farhi, Sam Gutmann, Analog analogue of a digital quantum computation Physical Review A. ,vol. 57, pp. 2403- 2406 ,(1998) , 10.1103/PHYSREVA.57.2403
Nader H. Bshouty, Richard Cleve, Wayne Eberly, Size-Depth Tradeoffs for Algebraic Formulas SIAM Journal on Computing. ,vol. 24, pp. 682- 705 ,(1995) , 10.1137/S0097539792232586
Miklos Santha, On the Monte Carlo Boolean decision tree complexity of read-once formulae Random Structures and Algorithms. ,vol. 6, pp. 75- 87 ,(1995) , 10.1002/RSA.3240060108
Andris Ambainis, Quantum Search with Variable Times symposium on theoretical aspects of computer science. ,vol. 47, pp. 786- 807 ,(2010) , 10.1007/S00224-009-9219-1
Harry Buhrman, Ronald de Wolf, Complexity measures and decision tree complexity: a survey Theoretical Computer Science. ,vol. 288, pp. 21- 43 ,(2002) , 10.1016/S0304-3975(01)00144-X
Marc Snir, Lower bounds on probabilistic linear decision trees Theoretical Computer Science. ,vol. 38, pp. 69- 82 ,(1985) , 10.1016/0304-3975(85)90210-5