Query complexity
= Query complexity
{title2=$Q(f)$}
The number of accesses to an unknown input needed to solve a specified task. The input might be a string with individually readable entries, or an implicitly supplied function. A complete statement specifies deterministic, randomized, or quantum access, the accepted error, and worst-case or expected cost. <Quantum query complexity> permits coherent input access through a <quantum oracle>.