An Almost-Quadratic Lower Bound for Quantum Formula Size

Abstract

We show that Nechiporuk's method for proving lower bound 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 (by Yao) states that the majority function does not have a linear-size quantum formula.

14 pages, 6 figures