Oracle-only bit-query algorithm

Fix an integer $N\ge 0$ and a promise domain $D\subseteq \{0,1{\}}^N$ as in QA task and promise domain. For each full-cube input $x=(x_0,\dots ,x_{N-1})$, define the total address function $g_x:\{0,1{\}}^N\to \{0,1\}$ by $g_x(e_i)=x_i$ for the one-hot word $e_i$ ($0\le i<N$), and $g_x(a)=0$ for every other address. If $N=0$, the address set has only the empty word and $g_x$ is identically zero. A local bit-query algorithm is a finite rooted execution tree on one fixed finite ordered register, starting in the all-zero computational-basis state $\mathrm{\mid }{0}^m⟩$ for its fixed register length $m$. The tree topology and each node label are fixed independently of $x$. Each non-oracle node is either a fixed unitary or a fixed finite instrument, with its observed outcomes retained for later control; every such operation is independent of $x$. Each query node acts on a declared $N$-bit address register and a disjoint one-bit target register by the standard XOR oracle $U_{g_x}$ of Standard bit-flip query convention, tensored with the identity on all other wires. Every terminal node uses the same ordered output-wire tuple and the same fixed accepting subset $S\subseteq \{0,1{\}}^r$, independent of $x$; the output law sums over all unmeasured labels and all terminal branch histories as in Normalized output law for finite quantum query branches.

The query count of a branch is the number of query nodes on its root-to-terminal path. The algorithm makes at most $T$ queries when every such path contains at most $T$ query nodes. A local bit-query algorithm has no direct input access: there is no input register containing $x$, no $x$-dependent non-oracle operation or initial state, and no $x$-dependent terminal predicate. Thus $x$ enters only through the stated bit oracle. This is the oracle-only specialization used for the QA15 polynomial-method results.

The local model is the standard Boolean-oracle specialization of Quantum query algorithm with no additional public instance data or input-access capability. Its all-zero initial state, fixed non-oracle operations and fixed terminal predicate implement that model directly; no register containing the hidden string $x$ is supplied. The polynomial-method claims use this oracle-only interface throughout, so all compared instances share the same non-oracle protocol.