Quantum Formulas: a Lower Bound and Simulation
<|reference_start|>Quantum Formulas: a Lower Bound and Simulation: We show that Nechiporuk's method 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 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.<|reference_end|>
@article{roychowdhury2001quantum,
    title={Quantum Formulas: a Lower Bound and Simulation},
    author={Vwani P. Roychowdhury and Farrokh Vatan},
    journal={arXiv preprint arXiv:quant-ph/0104053},
    year={2001},
    archivePrefix={arXiv},
    eprint={quant-ph/0104053},
    primaryClass={quant-ph cs.CC}
}