Query Complexity

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 .