Promise query instance and oracle family

For each encoded promised instance $z\in P_n$ of length $n$ (with $P_n$ as in Input encoding and size for algorithmic tasks and its task promise as in QA task and promise domain), a query instance specifies nonnegative integer widths $a(n),b(n)$ and a total function

$$f_z:\{0,1{\}}^{a(n)}\to \{0,1{\}}^{b(n)}\mathrm{.}$$

The promise restricts which $z$ are legal; it does not restrict the address domain of $f_z$. Bit strings label the big-endian computational basis: for a word $x=(x_0,\dots ,x_{r-1})$, its slot is ${\sum }_{k<r}{x}_k{2}^{r-1-k}$, with the empty word in slot $0$ (Big-endian encoding of ordered bit strings). Ket and bra notation uses the root convention $⟨x\mathrm{\mid }y{⟩}_D=⟨y,x{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}$ (Dirac Notation Conversion). Its standard quantum query is the coherent XOR oracle from Coherent XOR function oracle, acting on those ordered register bases:

$$U_{f_z}\mathrm{\mid }x⟩\mathrm{\mid }y⟩=\mathrm{\mid }x⟩\mathrm{\mid }y\oplus f_z(x)⟩,$$

where $\oplus$ is coordinatewise addition modulo two, $x$ is an $a(n)$-bit address, and $y$ is a $b(n)$-bit target. One invocation is one query, regardless of the output width. A supplied matrix or a classical description of $f_z$ does not itself supply a circuit decomposition, state preparation, or controlled access at zero cost.

The access contract must specify whether controlled calls are supplied: a controlled call is the explicitly granted block operation $\mathrm{diag}(I,U)$ (Controlled Unitary Access) and does not follow from an ordinary black-box call. For this standard XOR oracle, $U_{f_z}^{†}=U_{f_z}$ by A total Boolean XOR oracle is unitary and involutive, so an inverse query is the same operation as one ordinary query. Inverse access to any other unitary operation has its own explicitly declared availability and charge (Inverse Unitary Access). An explicit matrix or classical description supplies no free circuit implementation, preparation, or data loading; those costs are recorded under the declared circuit and gate resource coordinates (Circuit-family and computation cost model, Finite circuit resource accounting).