Quantum Formulas: a Lower Bound and Simulation
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
We show that Nechiporuk's method for proving lower bounds for Boolean formulas can be extended to the quantum case. This leads to an $Ω(n^2 / \log^2 n)$ lower bound for quantum formulas computing an explicit function. The only known previous explicit lower bound for quantum formulas states that the majority function does not have a linear-size quantum formula. We also show that quantum formulas can be simulated by Boolean circuits of almost the same size.
22 pages, LaTeX, 6 figures. Final and extended version of quant-ph/9903042. To appear in SIAM Journal on Computing
22 pages, LaTeX, 6 figures. Final and extended version of quant-ph/9903042. To appear in SIAM Journal on Computing