Quantum Lower Bound for Recursive Fourier Sampling
<|reference_start|>Quantum Lower Bound for Recursive Fourier Sampling: One of the earliest quantum algorithms was discovered by Bernstein and Vazirani, for a problem called Recursive Fourier Sampling. This paper shows that the Bernstein-Vazirani algorithm is not far from optimal. The moral is that the need to "uncompute" garbage can impose a fundamental limit on efficient quantum computation. The proof introduces a new parameter of Boolean functions called the "nonparity coefficient," which might be of independent interest.<|reference_end|>
@article{aaronson2002quantum,
    title={Quantum Lower Bound for Recursive Fourier Sampling},
    author={Scott Aaronson},
    journal={Quantum Information and Computation 3(2):165-174, 2003},
    year={2002},
    archivePrefix={arXiv},
    eprint={quant-ph/0209060},
    primaryClass={quant-ph cs.CC}
}