Finite Boolean query problem and error model for adversary bounds

Fix an integer N≥1, a nonempty finite set D⊆{0,1}^N, and a Boolean function f:D→{0,1}. A Boolean query problem is the tuple (N,D,f) with input x∈D and standard XOR oracle $O_x\mathrm{\mid }i,b,w⟩=\mathrm{\mid }i,b\oplus x_i,w⟩(i\in [N],b\in \{0,1\})\mathrm{.}$ The local address register is ${\mathbb{C}}^N$ with ordered basis $\mathrm{\mid }i⟩=e_{i-1}$, $i\in [N]$. For its qubit realization, set $a=\lceil {\log }_{2}N\rceil$ and encode $i$ by the $a$-bit binary word for $i-1$. Define the total bit function $\tilde{x}$ on all $a$-bit words by $\tilde{x}(j)=x_{j+1}$ for $0\le j<N$ and $\tilde{x}(j)=0$ for $N\le j<2^a$. The standard bit-flip query for $\tilde{x}$ restricts to $O_x$ on the encoded local register and acts as the identity on unused address codewords. Algorithms in the local model use the $N$-address register at query calls.

For 0≤ε<1/2, Q_ε(f) is the least worst-case number of these oracle calls of an algorithm outputting f(x) with probability at least 1−ε for every x∈D. The input promise does not restrict the oracle address. Only query calls are counted here; no gate-efficiency assertion is part of this definition.