Local bounded-error bit-query complexity

Let $f:D\to \{0,1\}$ be a promise function and $0\le ϵ<1\mathrm{/}2$. Its local bounded-error bit-query complexity is $Q_{ϵ}^{\mathrm{b}\mathrm{i}\mathrm{t}}(f;D):=\min \{T\in {\mathbb{N}}_0:\text{some local bit-query algorithm making at most }T\text{ queries has }\mathrm{\mid }\mathrm{Pr}[A\text{ accepts }x]-f(x)\mathrm{\mid }\le ϵ\text{ for every }x\in D\}\mathrm{.}$ The feasible set is nonempty. Query the one-hot addresses $e_0,\dots ,e_{N-1}$ in order, measuring each target bit and copying its result to a fresh, initially zero output wire by a fixed outcome-controlled bit flip; the outcomes are deterministically $x_0,\dots ,x_{N-1}$. Fixed branch operations reset the target between calls and set the next one-hot address, so the terminal output tuple is exactly the recorded $N$-bit word. The fixed terminal accepting subset $\{y\in D:f(y)=1\}$ then accepts exactly on yes-inputs in $D$, so this is an exact $N$-query algorithm (for $N=0$, the fixed output predicate suffices without a query). Thus the minimum is finite and at most $N$; it exists because the feasible counts below this one form a nonempty finite set of naturals, which has a least element by Every nonempty finite set of reals has a maximum and a minimum applied to their negatives. The query count is the minimum worst-branch query count and does not charge non-oracle operations. “Local” refers exactly to the oracle-only interface in Oracle-only bit-query algorithm. If $D=\mathrm{\varnothing }$, a zero-query algorithm is feasible and the minimum is $0$.

The coordinate in Quantum query complexity counts calls of one specified algorithm. The function-level quantity here minimizes that worst-branch coordinate over the oracle-only algorithms of Oracle-only bit-query algorithm that meet the stated success condition. It does not minimize over the broader class with direct encoded-input access. No uniformity, gate-cost, or classical bit-time bound is part of this minimum.