Boolean oracle query model for search lower bounds

Let $N\ge 1$, let the input be a bit string $x=(x_1,\dots ,x_N)\in \{0,1{\}}^N$, and let the address register have ordered orthonormal basis $\mathrm{\mid }0⟩,\dots ,\mathrm{\mid }N-1⟩$ in the finite-dimensional register of Finite registers and their ordered computational bases. A standard Boolean query acts on address, response bit, and work register by $O_x\mathrm{\mid }j,b,w⟩=\mathrm{\mid }j,b\oplus x_{j+1},w⟩,0\le j<N\mathrm{.}$ The response register is one qubit and the work register is any declared finite tensor product. For $N=2^n$, this is the standard bit query of Standard bit-flip query convention under the big-endian address encoding; for general $N$, it is the same XOR basis action on the $N$-level address register.

A $T$-query algorithm is a finite circuit whose only input-dependent operations are at most $T$ invocations of $O_x$ on every execution branch. By Coherent normal form for finite quantum query algorithms, it may be analyzed as a pure initial unit vector, input-independent unitaries between exactly $T$ ordinary queries, and one final measurement. The query coordinate counts these oracle invocations under Quantum query complexity; response preparation, verification queries, gates, and classical work are stated separately. No controlled access to $O_x$ follows from an ordinary query.

For a decision task, bounded error means the correct answer has probability at least $2\mathrm{/}3$ on every promised input, as in Worst-case bounded-error correctness. For a finding task, the same threshold applies to producing a valid witness on each promised input. The normal-form construction is finite for each input length; this definition makes no claim about its additional gate cost or preservation of a particular uniform generator.