| Abstract |
|
For any AND-OR formula of size N, there exists a bounded-error N^{1/2 + o(1)} -time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in {\rm O}(\sqrt N ) {\rm O}(\sqrt N ) (2 - o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
|
 Additional Information
|
Citation:
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,"
focs,
pp. 363-372,
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07),
2007
|
