loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer
Providence, Rhode Island
October 21-October 23
ISBN: 0-7695-3010-9
ASCII Text
x 
 
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," Foundations of Computer Science, IEEE Annual Symposium on, pp. 363-372, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2007.57,
author = {Andris Ambainis and Andrew M. Childs and Ben W. Reichardt and Robert Spalek and Shengyu Zhang},
title = {Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2007},
issn = {0272-5428},
pages = {363-372},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.57},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer
SN - 0272-5428
SP363
EP372
A1 - Andris Ambainis,
A1 - Andrew M. Childs,
A1 - Ben W. Reichardt,
A1 - Robert Spalek,
A1 - Shengyu Zhang,
PY - 2007
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
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.
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
Usage of this product signifies your acceptance of the Terms of Use.