Promise-preserving reduction composes with a query solver

For decision tasks, let $S=(Y_S,N_S)$ and $T=(Y_T,N_T)$ be promise problems and let $r$ be a promise-preserving total many-one reduction from $S$ to $T$ in the sense of Promise preserving reduction. For search tasks, let $(D_S,R_S)$ and $(D_T,R_T)$ be source and target search tasks, and suppose a total instance map $r:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ sends $D_S$ into $D_T$ and a total witness map $L:\{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$ satisfies $(r(z),w)\in R_T⟹(z,L(z,w))\in R_S(z\in D_S)\mathrm{.}$ In the search case, assume additionally that both $r$ and $L$ are computable; no time bound is required.

Let $T,s\in \mathbb{N}$ be fixed nonnegative integers. Let $A$ be a classical or quantum query solver for the target task that makes at most $T$ target-oracle calls on every branch and is exact or has bounded error at least $2\mathrm{/}3$ on every target-promised instance. Suppose that for every source-promised $z$, its access contract either directly supplies the target oracle selected by $r(z)$ at one source query per target invocation or supplies an exact simulation of each target query using at most $s$ source queries on every branch. If $A$ uses controlled oracle calls, that exact block operation must also be explicitly supplied and its charge included in the same cost bound (Controlled Unitary Access). An inverse call to the standard XOR oracle has the same action as one ordinary query by A total Boolean XOR oracle is unitary and involutive. In the quantum case, exact simulation means equality of the full query action on the query and algorithm workspace registers, with identity on unrelated registers.

Require, in addition, a fixed executable protocol under the source access interface that obtains the target public parameters (including target length), initializes the target solver exactly, and in the search case converts its returned witness $w$ to $L(z,w)$. For the bounds $T$ and $sT$ below, this initialization and output lifting use no source queries outside the target-query replacements. The protocol, including each replacement procedure, depends only on source public data and the available reply or measurement history, not on a freely readable hidden encoding. When the source instance is explicitly supplied as public input, computing $r$ and $L$ on that input is permitted, with the stated bit and preparation charges. Computability on the full encoding alone grants no extra hidden-input access.

Then the composed source solver has the same per-instance correctness guarantee as $A$. Its worst-case source query cost is at most $T$ in the direct-access case and at most $sT$ in the simulated-access case. Computing the reduction map, preparing the target solver's input, computing the search witness lift, and performing any simulation gates or classical work are charged separately under the declared bit and gate models. In the search case this theorem requires computability but claims no efficiency bound for either map. A promise-preserving map alone does not supply the target query oracle, its simulation, or an implementation of initialization and witness lifting under the source access interface. More generally, if an exact admissible initialization uses at most $u$ additional source queries and exact admissible output lifting uses at most $v$ on every branch, the same correctness guarantee holds with bounds $u+T+v$ and $u+sT+v$, respectively, for fixed nonnegative integers $u,v$.