Nonadaptive quantum query algorithms for total functions
Ashley Montanaro · arXiv (Cornell University) · 2009
We show that any bounded-error quantum query algorithm that computes some total boolean function depending on n variables, and whose queries to the input do not depend on the result of previous queries, must make Omega(n) queries to the input in total. Thus, in this restricted setting, quantum algorithms can achieve at most a constant factor speed-up over classical query algorithms.