Finite marked-item search and its bit oracle

Fix an integer $n\ge 0$, put $N=2^n$, and let $D_n=\{0,\dots ,N-1\}$. The big-endian encoding ${\mathrm{enc}}_n:\{0,1{\}}^n\to D_n$ is a bijection by Big-endian bit-string indices are bijective, so identify each address word $w$ with its slot $x={\mathrm{enc}}_n(w)$. A search instance is a total Boolean function $f:D_n\to \{0,1\}$, equivalently the word-indexed function $w\mapsto f({\mathrm{enc}}_n(w))$. Its marked set is $M=\{x\in D_n:f(x)=1\}$ and its marked count is $t=\mathrm{\mid }M\mathrm{\mid }$. The standard bit query is the coherent XOR action $U_f\mathrm{\mid }x,b⟩=\mathrm{\mid }x,b\oplus f(x)⟩$; the associated phase query is $O_M\mathrm{\mid }x⟩=(-1{)}^{f(x)}\mathrm{\mid }x⟩$. One standard bit query implements this phase action with a response qubit prepared in $\mathrm{\mid }-⟩$, by One standard query implements one phase query. A measured candidate $x$ is verified by a separate standard bit query. Knowing $t$ is additional classical input; no count promise is made in the unknown-count version. A correct search output is a verified $x\in M$. The distinguished output none is used only by a procedure whose input includes the exact fact $t=0$; it is not a finite-time test for emptiness when $t$ is unknown.

The number $n$ may be zero, so $N=1$ and the address register then has its one-dimensional empty-word basis. The phase query is uncontrolled; no controlled-query capability is part of this definition.