An Almost-Quadratic Lower Bound for Quantum Formula Size
<|reference_start|>An Almost-Quadratic Lower Bound for Quantum Formula Size: 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.<|reference_end|>
@article{roychowdhury1999an,
    title={An Almost-Quadratic Lower Bound for Quantum Formula Size},
    author={Vwani P. Roychowdhury and Farrokh Vatan},
    journal={arXiv preprint arXiv:quant-ph/9903042},
    year={1999},
    archivePrefix={arXiv},
    eprint={quant-ph/9903042},
    primaryClass={quant-ph cs.CC}
}