Query complexity counts oracle accesses required to compute a function, with other computation excluded from the cost. For a total Boolean function , randomized and quantum query complexities and usually permit error at most on every input and count worst-case bit queries. A randomized algorithm queries individual input bits, while a quantum algorithm may query them coherently in superposition. For example, a nonconstant function depending on one bit has .

The Aaronson-Ambainis conjecture concerns approximation of quantum acceptance probabilities on most inputs, a different error criterion from worst-case computation of a Boolean function.

See also

Boolean Function, Computational Complexity, Oracle, Quantum Circuit, Randomized Algorithm

Explore with Wolfram|Alpha

References

Aaronson, S. "Open Problems Related to Quantum Query Complexity." ACM Trans. Quantum Comput. 2, Article 14, 2021. https://doi.org/10.1145/3488559.

Cite this as:

Weisstein, Eric W. "Query Complexity." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/QueryComplexity.html

Subject classifications