Computational Problems, Promises, and Cost Models

Fix a promised input $z$ and a sequential procedure whose elementary steps are deterministic transitions, finite random transitions, finite-outcome measurements, or a single oracle call. At every live history, the next transition has a specified probability law on a finite outcome set; a query step has one successor and issues one call. A halted history is extended by deterministic idle steps that issue no calls.

For $M\in \mathbb{N}$, let ${\mathrm{\Omega }}_M$ be the finite set of length-$M$ histories with the recursively assigned transition weights. Let $C_M:{\mathrm{\Omega }}_M\to \{0,\dots ,M\}$ count the oracle calls actually executed in those $M$ steps. Define the expected query cost on input $z$ by

where each expectation is taken on the finite probability space of the corresponding prefix. Define the pathwise total query count on an infinite history $\omega$ by $C(\omega ):={\sup }_M{C}_M(\omega )$. No probability measure or expectation of $C$ on an infinite history space is presumed by this definition.

If a procedure is organized into rounds of at most $K$ elementary steps for some fixed integer $K\ge 1$, each containing at most one query, pad each round with deterministic idle steps to exactly $K$ steps. In this padded procedure, its first $R$ rounds are the prefix of length $KR$. Hence the supremum of its finite-round expected query counts equals the displayed finite-step supremum. In particular, query-indexed rounds are valid when each round contains exactly one query, as in Simon sampling.

A decision task is a root promise pair $(Y,N)$ of disjoint subsets of $\{0,1{\}}^{\ast }$, as in Promise problem: its promise domain is $Y\cup N$, and the required output is yes on $Y$ and no on $N$. No correctness condition is imposed outside that promise.

A search task is a pair $(D,R)$ where $D\subseteq \{0,1{\}}^{\ast }$ is the promise domain and $R\subseteq \{0,1{\}}^{\ast }\times \{0,1{\}}^{\ast }$ is a witness relation. On each $z\in D$, a correct solver must output a binary string $w$ with $(z,w)\in R$. It has no output obligation for $z\mathrm{\notin }D$. Unlike a decision task, a search task need not divide its promise into yes and no sets.

For either task, an input encoding and input-length convention are specified separately; correctness is required only for encoded inputs in the declared promise.

An input encoding is an injective map $\mathrm{enc}$ from the declared instance set into $\{0,1{\}}^{\ast }$. The input size of an instance $z$ is $n:=\mathrm{\mid }\mathrm{enc}(z)\mathrm{\mid }$. If task instances are already binary strings, the default encoding is the identity. The encoding is part of the task specification, and any length or padding convention must be stated.

For a task family, let $P_n$ denote the encoded instances of length $n$ that lie in its promise domain, with the decision sides or search relation inherited from QA task and promise domain. A statement indexed by input length $n$ concerns only $P_n$.

Fix an encoded input $x$ and a finite rooted execution tree on the same declared finite register $H_n$ at every node. Its root state is the density operator of the standard input basis state with zero-initialized work registers. Every nonterminal node is either a unitary endomorphism $U:H_n\to H_n$ or a finite instrument $({\mathcal{I}}_a{)}_{a\in {\mathrm{\Omega }}_h}$ whose branch maps are from $\mathcal{L}(H_n)$ to $\mathcal{L}(H_n)$. The observed outcome label $a$ is retained for classical feed-forward, while a hidden Kraus label is not a branch. The tree has finite depth and finite outcome sets.

Assign the root weight $w(\mathrm{\varnothing })=1$. At a unitary edge set ${\rho }_{h^{\mathrm{\prime }}}=U{\rho }_h{U}^{†}$ and $w(h^{\mathrm{\prime }})=w(h)$. At an instrument node set $q_{h,a}=\mathrm{tr}({\mathcal{I}}_a({\rho }_h))$ and $w(ha)=w(h)q_{h,a}$. If $q_{h,a}>0$, set ${\rho }_{ha}={\mathcal{I}}_a({\rho }_h)\mathrm{/}{q}_{h,a}$; if $q_{h,a}=0$, that child and its descendants have weight zero and contribute no state or output weight. The instrument and conditional-state conventions are those of Finite instruments and conditional states.

At each positive-weight leaf $\mathrm{\ell }$, the ordered output wires have a fixed length $m$ and are disjoint from the remaining wires $W_{\mathrm{\ell }}$. For $z\in \{0,1{\}}^m$ and a bit string $v$ on $W_{\mathrm{\ell }}$, let $e_{\mathrm{\ell },z,v}$ be the full-register computational-basis vector with those bits in their declared wire positions. Define the leaf output weight and total output law by $q_{\mathrm{\ell }}(z):={\sum }_{v\in \{0,1{\}}^{\mathrm{\mid }{W}_{\mathrm{\ell }}\mathrm{\mid }}}⟨{\rho }_{\mathrm{\ell }}{e}_{\mathrm{\ell },z,v},e_{\mathrm{\ell },z,v}{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}},P(z\mid x):={\sum }_{\mathrm{\ell }\text{ positive-weight leaf}}w(\mathrm{\ell })q_{\mathrm{\ell }}(z)\mathrm{.}$ The classical output predicate $A_n(x,z)$ selects the acceptance event by summing $P(z\mid x)$ over the finite set of accepted strings. This definition extends the terminal-output convention of Finite quantum promise-computation model to finite instrument branches; the verification proves that $P(\cdot \mid x)$ is a normalized probability law and every acceptance probability lies in $[0,1]$.

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

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:

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).

A classical query algorithm is a finite decision procedure for a fixed encoded instance length $n$ and explicitly declared public data $p$, whose query actions are to the total function $f_z$ of Promise query instance and oracle family. The procedure is fixed independently of the hidden instance $z$ at fixed $(n,p)$. Its encoding in Input encoding and size for algorithmic tasks labels the instance and determines its size; it does not provide a readable copy of the hidden encoding. Each query chooses an address from $n,p$, earlier replies, and any random bits used so far; it receives the entire $b(n)$-bit reply $f_z(x)$ as one query answer. The address choices may be adaptive. Its terminal output is determined by the same public data, replies, and random tape.

In the ordinary oracle-only model, all dependence on the hidden instance is through these replies. Public parameters such as register widths, a supplied marked count, or an explicit arithmetic input may be used only when the task declares them. A lower bound in the oracle-only model fixes the declared public data across the hidden instances it compares. Additional input-access or preparation capabilities must be explicitly declared with their charges; they are extra resources, not supplied by the hidden instance encoding.

For a randomized algorithm, each branch is determined by the public data, oracle replies, and its finite random tape; the fair-bit tape convention for a bounded-time probabilistic machine is supplied by Probabilistic polynomial time machine interface. The query model itself imposes no polynomial bit-time bound. A query bound is a worst-case bound over promised inputs and every random branch; classical computation between queries is charged separately only when a bit-cost model is specified.

For each encoded instance length $n$ and explicitly declared public data $p$, a quantum query algorithm is a specified finite circuit protocol on its query and work registers, fixed independently of the hidden instance $z$ at fixed $(n,p)$. The hidden encoding labels the oracle instance; it is not supplied as a readable input register. A register is a finite-dimensional complex inner-product space with its ordered computational basis; an $r$-qubit register uses the lexicographic bit-string basis, with the first wire most significant (Finite registers and their ordered computational bases). The finite promise-computation model Finite quantum promise-computation model supplies the public-classical-input, zero-initialized ancillary-register, ordered-output-tuple, and final-predicate conventions. Its classical input and terminal predicate receive only the declared public data, not the hidden encoding. Circuit syntax fixes the ordered wires and finite gate list Finite circuit syntax and ordered wire labels, and its denotation fixes the chronological gate composition Denotational semantics of a finite layered circuit. The execution tree starts in the standard public-input basis state with all other registers zero. Any explicit preparation interface is executed as a specified finite prefix of unitary or instrument nodes of this tree, with its preparation calls and other resource costs charged under the declared access contract. Intermediate measurements and classical feed-forward are represented by finite trees of instrument outcomes and branch-specific unitary operations. In the ordinary oracle-only model, all preparation operations, nonoracle gates and instruments, branch-control rules, and terminal output rules are independent of the hidden instance at fixed $(n,p)$; later operations may depend on observed outcomes. For each instantiated oracle, Normalized output law for finite quantum query branches gives the normalized output law of this tree with its public classical input. The output is interpreted according to the decision bit or search relation in QA task and promise domain.

In the ordinary oracle-only model, hidden-instance dependence enters only through the designated oracle calls. Explicit public parameters and arithmetic inputs remain available when the task declares them. Any additional instance-dependent state preparation or data-access operation is a separately declared and charged resource. Oracle-only lower bounds compare instances with the same public data and without such additional input access; the hidden encoding itself supplies none.

A $T$-query algorithm has at most $T$ designated calls to the oracle $U_{f_z}$ of Promise query instance and oracle family and Coherent XOR function oracle on every execution branch for every promised $z\in P_n$. Calls count once each; gates in the circuit outside those designated calls are not query calls. Uniformity is asserted only when the family satisfies Full-list uniform quantum circuit family. A controlled call has the block action in Controlled Unitary Access and is available only when the access contract explicitly supplies and charges it. An inverse call to this XOR oracle has the same action as an ordinary call by A total Boolean XOR oracle is unitary and involutive; inverses of other unitaries use the separate availability and charge convention in Inverse Unitary Access.

The finite promise-computation model supplies the public-input and terminal-output conventions. The finite instrument tree extends it to intermediate measurements; its branch law is applied separately to each instantiated oracle, without granting the terminal predicate access to the hidden encoding. No uniformity claim is made unless the full-list condition is supplied.

A quantum or classical solver in Quantum query algorithm and Classical query algorithm for a decision task $(Y,N)$ of QA task and promise domain has bounded error (with the QA convention) if its normalized output law assigns probability at least $2\mathrm{/}3$ to the correct answer for every encoded promised instance. A search solver has bounded error if, for every encoded $z$ in its domain $D$, its output law assigns probability at least $2\mathrm{/}3$ to outputs $w$ satisfying $(z,w)\in R$. The guarantee is worst-case per instance, not averaged over an input distribution. The constant $2\mathrm{/}3$ is a convention; amplification and its query/access cost are separate results.

For quantum algorithms the success event is evaluated from the normalized finite-branch output law of Normalized output law for finite quantum query branches. Its normalization follows from the finite instrument and unitary branches in that definition; the success threshold remains a per-instance condition.

For a classical query algorithm Classical query algorithm, bit-operation cost is the number of transitions of a declared multitape Turing machine over a fixed finite alphabet; the $k$-tape transition reads and writes one symbol on each of its $k\ge 1$ tapes and moves each head once per transition (Multitape and nondeterministic Turing machine variants). It includes random-bit generation, any encoding work actually performed by that machine on declared public data or received replies, address formation, reading and writing every bit of an oracle reply, comparison/postprocessing, and writing the classical output. The abstract instance encoding in Input encoding and size for algorithmic tasks fixes the size parameter; it supplies neither a readable hidden input nor an encoding procedure to execute. The fair-bit machine convention is supplied by Probabilistic polynomial time machine interface. The oracle invocation itself is one separately counted query action; its returned bits are not free to process.

For a query with an $a(n)$-bit address and a $b(n)$-bit reply, the machine's charged work includes forming the address and processing the $b(n)$ reply symbols. A claimed time bound also specifies whether it is worst-case over promised inputs and random tapes, as in Probabilistic polynomial time machine interface. Query, nonoracle quantum gate, measurement, and classical bit costs remain distinct.

For a decision task $(Y,N)$ from QA task and promise domain, a solver is exact if its normalized output law assigns probability one to yes on every encoded $z\in Y$ and probability one to no on every encoded $z\in N$. For a search task $(D,R)$ from the same definition, it is exact if, for every encoded $z\in D$, its normalized output law assigns probability one to outputs $w$ satisfying $(z,w)\in R$. These are per-instance requirements; no correctness is asserted outside the promise.

The solver is one of the quantum algorithms in Quantum query algorithm or classical algorithms in Classical query algorithm. For a quantum solver, its output weights are the normalized finite-branch law of Normalized output law for finite quantum query branches. For a randomized classical solver, they are the probabilities induced by its declared finite random-tape law. Exactness does not follow merely from a circuit or algorithm description; it is a condition on its output law.

Given the circuit-family model and cost record in Circuit-family and computation cost model and elementary gate alphabet in Finite circuit resource accounting, a query circuit Quantum query algorithm has nonoracle gate cost equal to the maximum number of elementary gates outside designated black-box query calls on any branch. It counts preparation gates, ancilla operations, inverse gates, and every other stated nonoracle gate, including identity operations if the declared syntax counts them. It does not count a black-box query as an elementary gate; if the oracle is implemented from a supplied circuit, that implementation's gates are charged under the declared resource model.

Non-input registers start in $\mathrm{\mid }0⟩$. Any nonzero initial state or data-access resource must name its preparation/access model and charge that cost. Measurements, classical feed-forward, circuit-description length, and classical bit operations are reported in the selected QC resource convention rather than silently assigned zero cost. Query count and gate count are separate coordinates.

For a classical query algorithm Classical query algorithm at input length $n$, its worst-case classical query cost is the maximum number of oracle calls over every promised instance and every random tape. When there are no promised instances of length $n$, define this cost to be $0$. If those counts are not uniformly bounded, the cost is infinite. One query returns the full value $f_z(x)$, regardless of its bit width. Expected-query bounds are reported separately using Expected query cost from finite execution prefixes.

For a bounded-error classical solver, the query cost is still worst-case over inputs and random tapes; the success requirement is the per-instance probability in Worst-case bounded-error correctness. Distributional input averages and expected query counts are different quantities.

For a $T$-query quantum algorithm Quantum query algorithm at input length $n$, its worst-case quantum query cost is the maximum number of designated oracle calls over all promised instances in $P_n$ and all measurement branches. When $P_n$ is empty, define this cost to be $0$. For nonempty $P_n$, a finite circuit and finite branch sets ensure that this maximum exists; a solver whose branch counts are not uniformly bounded has infinite worst-case query cost. An expected-query bound is the separate quantity defined by Expected query cost from finite execution prefixes.

In the pure query model, ordinary gates outside the oracle calls are uncharged by the query coordinate. If a task also reports gate, preparation, measurement, or classical costs, those are separate coordinates. Bounded-error query cost uses the same worst-case maximum; its success threshold is the per-instance condition in Worst-case bounded-error correctness, not an average over oracle inputs.

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$.