Quantum formulas: A lower bound and simulation

Citation
Vp. Roychowdhury et F. Vatan, Quantum formulas: A lower bound and simulation, SIAM J COMP, 31(2), 2001, pp. 460-476
Citations number
27
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
0097-5397 → ACNP
Volume
31
Issue
2
Year of publication
2001
Pages
460 - 476
Database
ISI
SICI code
0097-5397(20011011)31:2<460:QFALBA>2.0.ZU;2-D
Abstract
We show that Nechiporuk's method [I. Wegener, The Complexity of Boolean Fun ctions, Teubner-Wiley, New York, 1987] for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an Omega (n(2) /log(2)n) lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas [A. Yao, Proceedings of 34th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 352-361] states that t he majority function does not have a linear-size quantum formula. We also s how that quantum formulas can be simulated by Boolean circuits of almost th e same size.