2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/89427We 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 ComputingQuantum PhysicsComputational Complexitytext