Uniform Circuit Families, Promise Problems, and Complexity

Let $\mathrm{\Pi }=(Y,N)$ be a promise problem: $Y,N\subseteq \{0,1{\}}^{\ast }$ are disjoint, and no answer is required outside $Y\cup N$ (Promise problem). For every input length $n\ge 0$, let $a(n)\in \mathbb{N}$ be the number of auxiliary qubits. The $n$ input wires are ordered with the first wire most significant: for $x=(x_0,\dots ,x_{n-1})$, $\mathrm{\mid }x⟩$ is the computational-basis vector indexed by ${\mathrm{enc}}_n(x)={\sum }_{k<n}{x}_k{2}^{n-1-k}$ (Finite registers and their ordered computational bases, Big-endian encoding of ordered bit strings). The auxiliary register has $a(n)$ wires and is initialized to $\mathrm{\mid }{0}^{a(n)}⟩$. When $n=0$ or $a(n)=0$, the corresponding zero-qubit register is the one-dimensional space $\mathbb{C}$, not the zero vector space.

For each $n$, a finite circuit $C_n$ acts on the ordered register of $n+a(n)$ wires and has the unitary denotation $U_{C_n}$ specified by Finite circuit syntax and ordered wire labels and Denotational semantics of a finite layered circuit. The circuit syntax designates an ordered tuple of distinct output-wire indices; an acceptance specification uses that same tuple $O_n$, whose indices lie in $\{0,\dots ,n+a(n)-1\}$. It consists of this tuple and a total predicate $A_n(x,z)\in \{0,1\}$ for $x\in \{0,1{\}}^n$ and $z\in \{0,1{\}}^{\mathrm{\mid }{O}_n\mathrm{\mid }}$. The tuple may be empty; then its measured output set contains only the empty word. Auxiliary wires are initialized to zero, but this definition does not require them to return to zero after the computation; that stronger clean-ancilla condition is defined in Clean and dirty ancillas.

A finite quantum promise computation is the data $(\mathrm{\Pi },(C_n{)}_{n\ge 0},a,O,A)$ with these registers and predicates. Its output is classical: measure only the named output wires in the computational basis and accept exactly when $A_n(x,z)=1$. No intermediate measurement is part of this base model. Unless a full-list uniformity condition is imposed separately, the family need not be generated uniformly. When uniformity or cost is claimed, $A$ is supplied by one fixed deterministic Turing machine with an explicit polynomial worst-case time bound in the encoded pair $(x,z)$ (Deterministic one-tape Turing machines with designated accept and reject states, Partial functions computed by a machine under fixed encodings, Worst-case time and space complexity of a machine). This is a mathematical finite-circuit model and makes no assertion about physical realization.

Fix the finite circuit syntax and its complete self-delimiting binary description (Finite circuit syntax and ordered wire labels, Effective binary encodings and total decoders). For a circuit $C$, let $L(C)$ be the number of bits in that complete description, $g(C)$ its number of gate occurrences, and $w(C)$ its total number of wires.

Each clean or dirty ancilla coordinate additionally requires a declared ordered partition of the circuit wires into data register $D$ and ancilla register $A$, and a declared target unitary $V$ on $D$. In that factor order, the complete circuit unitary must satisfy the corresponding exact contract of Clean and dirty ancillas. For such a supplied clean contract set $a_{\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}}(C)=\mathrm{\mid }A\mathrm{\mid }$, and for such a supplied dirty contract set $a_{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{t}\mathrm{y}}(C)=\mathrm{\mid }A\mathrm{\mid }$; the notation suppresses the declared interface, which is part of the cost instance and may differ between the two coordinates. If no corresponding contract is supplied, mark that coordinate not applicable. These are counts of declared contract registers, not maxima over possible partitions. Zero initialization alone supplies neither return contract. Every auxiliary wire remains counted in $w(C)$ (Finite circuit resource accounting).

The gate sequence and supports determine a finite dependency order: each earlier gate occurrence must precede every later occurrence that acts on a shared wire. A layering assigns a positive integer layer to each gate occurrence, strictly increasing along those shared-wire precedence relations. Gates in one layer therefore have pairwise disjoint supports. Define the depth $d(C)$ to be the least number of layers in such a layering; if $C$ has no gates, set $d(C)=0$. If layers are written $L_1,\dots ,L_d$ in chronological order, the denotation is $U_{L_d}\cdots U_{L_1}$, as in Denotational semantics of a finite layered circuit.

For a family $(C_n)$ with a specified full-list generator $G$, let $t_G(n)$ be the worst-case number of Turing-machine transitions used by $G$ on unary input $1^n$. For a total acceptance predicate $A_n(x,z)$, let $t_A(n)$ and $s_A(n)$ be its worst-case deterministic transition count and tape-space use over all valid length-$n$ inputs and measured outputs, using a fixed effective encoding of the pair $(x,z)$. Any effective input description, classical preprocessing, or threshold computation has its own bit length and time/space bounds; these costs are not included in $t_G$ or $t_A$ unless the same machine performs them. The machine conventions are those of Deterministic one-tape Turing machines with designated accept and reject states, Partial functions computed by a machine under fixed encodings, and Worst-case time and space complexity of a machine.

If the access model explicitly supplies a named oracle gate $\mathcal{O}$, let $q_{\mathcal{O}}(C)$ be the number of calls to it. With several named oracles, record a separate query coordinate for each. Ordinary finite-basis gates, oracle calls, circuit-description length, generator time, and classical bit costs remain separate; no oracle, controlled-oracle, inverse-oracle, or data-loading operation is assigned zero cost unless its interface explicitly says so.

For an approximate task with declared rational tolerance $0<ϵ<1$, let $\mathrm{\ell }(ϵ)$ be the bit length of that exact binary-rational encoding. Exact finite-gate computations have no precision field. The cost record consists of all applicable coordinates $(L(C_n),g(C_n),d(C_n),w(C_n),a_{\mathrm{c}\mathrm{l}\mathrm{e}\mathrm{a}\mathrm{n}}(C_n),a_{\mathrm{d}\mathrm{i}\mathrm{r}\mathrm{t}\mathrm{y}}(C_n),t_G(n),t_A(n),s_A(n),q_{\mathcal{O}}(C_n),ϵ,\mathrm{\ell }(ϵ))\mathrm{.}$ An inapplicable coordinate is marked not applicable, not silently charged as zero. This definition records the resource model; separate theorems establish polynomial bounds.

The minimum-layer quantity $d(C)$ above may also be denoted $d_{\min }(C)$. It differs from the declared depth $d_{\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{l}}(C)$ in Finite circuit resource accounting, which counts the layers actually written in the supplied circuit. Its written layering is one admissible layering of the same gate word, so $d_{\min }(C)\le d_{\mathrm{d}\mathrm{e}\mathrm{c}\mathrm{l}}(C)$. The inequality can be strict: two gates on disjoint wire sets written in two successive layers have declared depth $2$ and minimum-layer depth $1$. Empty written layers also contribute to declared depth, while a gate-free word has minimum-layer depth $0$. These are separate resource quantities; a cost statement must specify which one it bounds.

A full-list uniform quantum circuit family is a sequence $(C_n{)}_{n\ge 0}$ together with one fixed deterministic one-tape Turing machine $G$ and constants $c\ge 1$ and $k\in \mathbb{N}$ such that, on input the unary word $1^n$, $G$ halts within $c(n+1{)}^k$ transitions and its final tape is a valid self-delimiting binary description of the entire circuit $C_n$. The machine output convention is that of Deterministic one-tape Turing machines with designated accept and reject states and Partial functions computed by a machine under fixed encodings, and running time is as in Worst-case time and space complexity of a machine.

The following fixed-order code makes the full circuit and its designated input/output wires effective. A unary natural $r\in \mathbb{N}$ is written $1^{r}0$, including the one-symbol code $0$ for $r=0$. A self-delimiting binary natural $r$ is written $1^{\mathrm{\mid }\mathrm{bin}(r)\mathrm{\mid }}0\mathrm{bin}(r)$, where $\mathrm{bin}(r)$ is its ordinary binary numeral with no leading zeros and $\mathrm{bin}(0)=0$. The header gives the input-wire count $n$ and total wire count $m$ in unary, followed by the gate count $g$ as a self-delimiting natural; validity requires $m\ge n$.

Each gate record consists of a two-bit label ($00,01,10,11$ for $H,T,T^{†},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}$ respectively), followed by one self-delimiting wire index for $H,T,T^{†}$ and two ordered self-delimiting indices for CNOT. Every index is less than $m$; CNOT indices are distinct, with the first the control and the second the target. The list contains exactly $g$ records. After the gate list, an output-count self-delimiting natural is followed by that many ordered, pairwise distinct wire indices, each less than $m$. Parsing rejects every other label, malformed or out-of-range index, repeated output index, truncated field, or trailing bit. This defines a total decoder by returning a fixed malformed-code symbol on any invalid word; effective binary encodings and total decoders are as in Effective binary encodings and total decoders.

The gate labels and matrices are the fixed finite library $H,T,T^{†},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}$ of Clifford+T gate library and exact matrices, with entries in $\mathbb{Q}({\zeta }_8)=\mathbb{Q}(i,\sqrt{2})$; CNOT is control-first. The remaining $m-n$ wires are auxiliary wires; their initial states are determined when a family is used in a computation model. This family convention adopts full-list generation. It makes no equivalence claim with indexed-gate uniformity and, in particular, does not assert that an indexed-gate generator can be expanded to the full list in polynomial time.

When a family is used in a promise computation, its output predicate is supplied separately by that computation model; the predicate is not an uncharged quantum gate (Finite quantum promise-computation model).

Fix a length-$n$ finite promise computation from Finite quantum promise-computation model, with input $x\in \{0,1{\}}^n$, zero-initialized auxiliary register $\mathrm{\mid }{0}^{a(n)}⟩$, circuit unitary $U_{C_n}$, and ordered output-wire tuple $O_n$. Let $P_{O_n}$ be the tensor-factor permutation that moves $O_n$, in its declared order, to the front, and let $W_n$ be the ordered tuple of all remaining wires (Ordered tensor registers, their inner product, and wire permutations). Set ${\psi }_x:=U_{C_n}(\mathrm{\mid }x⟩\otimes \mathrm{\mid }{0}^{a(n)}⟩),v_x:=\mathrm{coord}(P_{O_n}{\psi }_x)\mathrm{.}$ Here coordinates are in the ordered computational basis. In this definition, $⟨\cdot ,\cdot {⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}:=⟨\cdot ,\cdot {⟩}_{\otimes }$ denotes the inner product on the reordered complete tensor register from Ordered tensor registers, their inner product, and wire permutations, linear in its first argument and conjugate-linear in its second (Real and complex inner-product spaces and their induced length). For $z\in \{0,1{\}}^{\mathrm{\mid }{O}_n\mathrm{\mid }}$ and $w\in \{0,1{\}}^{\mathrm{\mid }{W}_n\mathrm{\mid }}$, write $e_{z,w}$ for the corresponding product-basis vector and define $p_{C_n}(z\mid x):={\sum }_{w\in \{0,1{\}}^{\mathrm{\mid }{W}_n\mathrm{\mid }}}{\mid ⟨P_{O_n}{\psi }_x,e_{z,w}{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}\mid }^2\mathrm{.}$ The acceptance probability is $p_{C_n}(x):={\sum }_{\begin{array}{c}z\in \{0,1{\}}^{\mathrm{\mid }{O}_n\mathrm{\mid }}\\ A_n(x,z)=1\end{array}}{p}_{C_n}(z\mid x)\mathrm{.}$ Equivalently, if $E_{A,x}$ is the diagonal projection onto the basis vectors $(z,w)$ with $A_n(x,z)=1$, then $p_{C_n}(x)=\mathrm{Tr}(E_{A,x}{v}_x{v}_x^{†})$; the matrix adjoint is conjugate transpose in an orthonormal basis (The adjoint $T^{\ast }:W\to V$ is characterised by $⟨Tv,w{⟩}_W=⟨v,T^{\ast }w{⟩}_V$, Every finite-dimensional real or complex inner product space has an orthonormal basis).

These are finite sums. The definition itself does not assert normalization, positivity of the resulting operator expression, or a probability bound; those consequences are the purpose of The partial-output acceptance law is a finite probability law. No Dirac bra convention is used here: every amplitude uses the root pairing displayed above.

For a finite promise computation, replacing its entire unconditional circuit unitary $U_C$ by $\lambda U_C$, where $\lambda \in \mathbb{C}$ and $\mathrm{\mid }\lambda \mathrm{\mid }=1$, leaves every output probability $p_C(z\mid x)$ and hence $p_C(x)$ unchanged. A scalar inserted only in the target block of a controlled operation need not preserve acceptance: there is an explicit two-qubit finite-circuit witness below.

A promise problem $\mathrm{\Pi }=(Y,N)$ belongs to BQP in the QC14 model when there exist a full-list uniform family $(C_n)$ and a polynomial-time acceptance predicate $A_n$ as in Full-list uniform quantum circuit family and Quantum acceptance probability for a finite promise computation such that, for every $x\in Y$, $p_{C_{\mathrm{\mid }x\mathrm{\mid }}}(x)\ge \frac{2}{3},$ and for every $x\in N$, $p_{C_{\mathrm{\mid }x\mathrm{\mid }}}(x)\le \frac{1}{3}\mathrm{.}$ By The partial-output acceptance law is a finite probability law, $p_{C_n}(x)$ is the probability of the specified acceptance event and lies in $[0,1]$. No condition is imposed for $x\mathrm{\notin }Y\cup N$ (Promise problem). The gate alphabet is exactly $H,T,T^{†},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}$; its matrix entries lie in $\mathbb{Q}({\zeta }_8)=\mathbb{Q}(i,\sqrt{2})$ as specified by Full-list uniform quantum circuit family. This definition does not assert a BQP-versus-classical separation, nor does it assert an unproved equivalence with another circuit-uniformity convention.

If the generator in Full-list uniform quantum circuit family halts on input $1^n$ within $T(n)\le c(n+1{)}^k$ transitions, then the generated description has length at most $n+T(n)+O(1)$. Consequently its number of gates and total number of wires are polynomial in $n$. This is a full-list size bound; it does not establish equivalence with indexed-gate uniformity.

An oracle-aware full-list family has an access specification and a deterministic polynomial-time full-list generator on unary input $1^n$, with the same machine, clock, and final-tape conventions as Full-list uniform quantum circuit family. The access specification gives, at each length $n$, finitely many named ports ${\mathcal{O}}_{n,j}$, each a unitary on a positive number $k_{n,j}$ of qubits. These are mathematical unitary data supplied by the access specification, not matrices computed by the generator. For a parametrized oracle instance, fix that instance throughout a computation and all its repetitions. The generator, printed descriptors, and final classical predicate are independent of the hidden instance: its influence enters only through the granted unitary ports. Any public parameters are fixed explicitly as part of the family specification; oracle comparisons hold them fixed. A port acts only on the wires in its occurrence; there is no persistent private oracle memory, stochastic resampling, or communication between disjoint occurrences through hidden registers.

Each port has a descriptor: a distinct nonempty binary name, its width $k_{n,j}$, and four grant bits for forward, inverse, controlled-forward, and controlled-inverse access. At least one variant is granted. A granted variant has an explicitly specified positive integer query charge $c_{n,j,v}$; an ungranted variant cannot occur. Forward and inverse have arity $k_{n,j}$; controlled variants have arity $k_{n,j}+1$, with the first wire the control and the remaining ordered wires the target. Their mathematical actions are respectively ${\mathcal{O}}_{n,j}$, ${\mathcal{O}}_{n,j}^{†}$, and the corresponding controlled unitary (identity on control $0$, the indicated unitary on control $1$). Mathematical existence of an inverse or controlled unitary grants no access to it. The descriptors printed by the generator must agree with the supplied access specification at every length; syntactic decoding alone does not decide this semantic condition.

The following is a separate binary format; the original two-bit Clifford+T format of Full-list uniform quantum circuit family remains unchanged. Use its unary and self-delimiting natural codes. The header gives $n,m$ in unary with $m\ge n$, then the total number $g$ of operation occurrences and the number of port descriptors as self-delimiting naturals. Each descriptor gives the name length as a self-delimiting natural followed by exactly that many name bits, the positive port width in unary, four grant bits in the order above, and one positive self-delimiting charge for each granted variant in that order. Descriptor order fixes port indices starting at zero.

The header and descriptors are followed by exactly $g$ operation records. A three-bit label $000,001,010,011$ denotes respectively ordinary $H,T,T^{†},\mathrm{C}\mathrm{N}\mathrm{O}\mathrm{T}$ and is followed by the same ordered wire-index fields as in the original format. Label $100$ denotes an oracle slot: a self-delimiting port index, a two-bit variant index in the descriptor order, and exactly the variant's arity many ordered self-delimiting wire indices. Every index is below $m$, and wires within each record are distinct. The final output-count and ordered distinct output-wire list use the original format. All other labels, duplicate names, ungranted variants, invalid fields, truncations, and trailing bits are rejected. As in the original code, the decoder is total by returning a malformed-code symbol on rejection. The generator prints this entire description, including every descriptor and every slot, within its explicit polynomial clock. The port count, widths, names, and charges must therefore fit in that printed description; neither an exponentially long list nor an implicit operation subroutine counts as full-list output.

For a fixed length and oracle instance, instantiating the slots gives an ordinary finite unitary circuit with a finite enlarged gate alphabet in the sense underlying Full-list uniform quantum circuit family. Use the ordered wire embedding and chronological composition of that item. Zero auxiliary initialization, final output measurement, and a separately supplied total polynomial-time classical predicate are exactly those of Finite quantum promise-computation model; acceptance is the finite coordinate sum in Quantum acceptance probability for a finite promise computation. No oracle call is performed by the classical generator or predicate unless a separate classical access interface is declared; here neither is granted one.

In the cost convention of Circuit-family and computation cost model, $g(C)$ counts all operation occurrences. Write $g_{\mathrm{o}\mathrm{r}\mathrm{d}}(C)$ for the number of ordinary records and $N_{j,v}(C)$ for the number of slots for port $j$, variant $v$. Thus $g(C)=g_{\mathrm{o}\mathrm{r}\mathrm{d}}(C)+{\sum }_{j,v}{N}_{j,v}(C)$. Record the raw call count $q_j(C)={\sum }_v{N}_{j,v}(C)$ and, separately, the declared charged query cost $Q_j(C)={\sum }_v{c}_{n,j,v}{N}_{j,v}(C)$. A polynomial bound on the binary description length does not imply a polynomial bound on $Q_j$ if charges have large binary values. Ordinary CNOT records incur ordinary gate cost and no query, even if a named port happens to have the same matrix. Oracle records remain query records even when their matrices admit an ordinary implementation; substituting such an implementation is a separate construction and cost claim.

The ordinary mode instead uses the exact original full-list code with no ports or query slots. In particular the oracle-aware format does not enlarge the gate library or alter the exact arithmetic convention of the QC14 BQP definition.

Inputs. In ordinary mode, a full-list uniform family generator $G$ in the exact fixed-library format of Full-list uniform quantum circuit family; or, in oracle mode, an oracle-aware full-list generator and its granted access specification as in Oracle-aware full-list quantum circuit family. In either mode supply a total deterministic acceptance-predicate machine $A$ and explicit polynomial clock bounds, with zero auxiliary initialization, output tuples, and acceptance as in Finite quantum promise-computation model and Quantum acceptance probability for a finite promise computation; machines that output exact binary rationals $\alpha (n),\beta (n),\delta (n)$ with explicit polynomial clock bounds; and a fixed positive integer-valued polynomial $s(n)$ with an exact rational-coefficient representation. The machine descriptions and clock bounds are fixed parts of the input data, and each rational output has polynomial bit length. Valid inputs satisfy, for every $n$, $0\le \beta (n)<\alpha (n)\le 1,\alpha (n)-\beta (n)\ge \frac{1}{s(n)},0<\delta (n)\le \frac{1}{2}\mathrm{.}$ The procedure checks the clock and syntax at each requested length and returns INVALID if a run exceeds its supplied clock, a code is malformed, or any displayed inequality fails. Its domain consists of descriptions whose stated polynomial bounds and inequalities hold for all $n$; the procedure does not decide that global validity property for arbitrary machine descriptions.

Instructions at length $n$.

1. Run the supplied machines within their polynomial clocks to obtain the full description of $C_n$, $\alpha =\alpha (n)$, $\beta =\beta (n)$, and $\delta =u\mathrm{/}v$ with positive integers $u,v$. In oracle mode, also compare the printed port descriptors with the supplied access specification at length $n$; on any mismatch return INVALID. Evaluate $s(n)$ exactly from its fixed rational-coefficient polynomial. Check that it is a positive integer, check exact rational syntax, and check the validity inequalities by integer arithmetic; on failure return INVALID.
2. Let $\mathrm{\ell }(v)$ be the number of binary digits of $v$ and set $r:=2s^2(\mathrm{\ell }(v)+1)\mathrm{.}$ This is a positive integer. No logarithm or irrational ceiling is evaluated.
3. Allocate $r$ disjoint copies of the entire $C_n$ wire register in block order, with block $1$ first. Put the classical-basis input $\mathrm{\mid }x⟩$ on the first block's first $n$ wires; initialize every other wire to zero. For $j=2,\dots ,r$ in increasing order, and then $i=0,\dots ,n-1$ in increasing order, append a CNOT from wire $i$ of block $1$ to wire $i$ of block $j$, with the first wire as control. These operations map $\mathrm{\mid }x⟩\mathrm{\mid }{0}^n{⟩}^{\otimes (r-1)}$ to $\mathrm{\mid }x{⟩}^{\otimes r}$ and do not clone arbitrary superpositions. Then, for blocks $j=1,\dots ,r$ in order, append the records of $C_n$ in their supplied chronological order, shifting each wire index by $(j-1)w(C_n)$. This serializes each base circuit's records; gates listed in a common layer have disjoint supports, so serialization preserves its denotation. Keep the first block's $n$ input wires first in the output wire order and encode input count $n$; every other wire is auxiliary. In oracle mode, retain each slot's port and granted variant, shift only its ordered wire indices by the block offset, and copy the access descriptors once. The added CNOTs are ordinary records, never query slots. The repeated circuit has $rw(C_n)$ wires and $rg(C_n)+n(r-1)$ operation occurrences; in oracle mode its ordinary count is $r{g}_{\mathrm{o}\mathrm{r}\mathrm{d}}(C_n)+n(r-1)$.
4. Concatenate the $r$ copies of the declared output tuple in copy order and measure that tuple at the final readout. For measured strings $z_1,\dots ,z_r$, compute $S=\mathrm{\#}\{i:A_n(x,z_i)=1\}$. The single total output predicate returns YES exactly when $2S\ge r(\alpha +\beta )$, evaluated exactly: if $\alpha =A\mathrm{/}B$ and $\beta =C\mathrm{/}D$ with positive denominators, compare $2SBD$ with $r(AD+CB)$. Return NO otherwise.

The output is one full-list repeated circuit in the input mode's format and its total classical predicate. Ordinary mode uses only the original fixed library. In oracle mode every base port/variant occurrence is repeated $r$ times: $N_{j,v}$, raw call counts $q_j$, and charged query costs $Q_j$ all scale by $r$, with unchanged grants and per-call charges (Oracle-aware full-list quantum circuit family). Query costs remain separate from ordinary gates and classical bit costs (Circuit-family and computation cost model). The endpoint comparison is classical postprocessing, not an intermediate measurement or coherent amplitude-amplification step. Correctness, uniformity, and resource bounds are separate claims proved by Bounded-error repetition amplification is correct and uniform.

For every finite promise computation, every length $n$, and every classical input $x\in \{0,1{\}}^n$, the output weights $p_{C_n}(z\mid x)$ from Quantum acceptance probability for a finite promise computation are nonnegative and sum to one over $z\in \{0,1{\}}^{\mathrm{\mid }{O}_n\mathrm{\mid }}$. The acceptance probability is the probability of the event $\{z:A_n(x,z)=1\}$, lies in $[0,1]$, and agrees with the finite computational-basis POVM outcome law on the named output register.

Assume the input family, rational threshold functions, gap polynomial, and clocks satisfy the valid-input conditions of Bounded-error repetition amplification. Assume also that the base acceptance satisfies $p_{C_n}(x)\ge \alpha (n)$ for every length-$n$ YES input and $p_{C_n}(x)\le \beta (n)$ for every length-$n$ NO input, where $0\le \beta (n)<\alpha (n)\le 1$ and $\alpha (n)-\beta (n)\ge 1\mathrm{/}s(n)$. On every input in the YES promise set, the amplified acceptance probability is at least $1-\delta (n)$; on every input in the NO promise set, it is at most $\delta (n)$. If $g(C_n)$ and $w(C_n)$ are the base gate count and total wire count, the repeated family has gate count $r(n)g(C_n)+n(r(n)-1)$ and width $r(n)w(C_n)$. Its depth, complete-description length, generator time, and classical predicate time and space are polynomial in $n$. Ordinary mode retains the exact original fixed gate library and full-list code. In oracle mode its ordinary gate count is $r(n)g_{\mathrm{o}\mathrm{r}\mathrm{d}}(C_n)+n(r(n)-1)$, every port/variant count satisfies $N_{j,v}(C_n^{\mathrm{r}\mathrm{e}\mathrm{p}})=r(n)N_{j,v}(C_n)$, and both raw query counts $q_j$ and charged query costs $Q_j$ are multiplied by $r(n)$ with the same granted access. Raw query counts are polynomial; charged query costs are polynomial whenever the base charged costs are polynomial. For a base clean or dirty interface whose declared ancillary register is disjoint from the first $n$ input wires, the input-copy stage acts only on data, and the corresponding exact contract is preserved with its declared register count multiplied by $r(n)$; the extra input-copy wires remain in total width and are not counted as returned clean ancillas.

Let $q:\mathbb{N}\to \mathbb{N}$ be computable in deterministic polynomial time and polynomially bounded, with $q(n)\ge 2$ for all sufficiently large $n$. For every promise problem, the following are equivalent in the QC14 full-list model:

1. it has a uniformly generated family and polynomial-time acceptance predicate with acceptance at least $2\mathrm{/}3$ on YES and at most $1\mathrm{/}3$ on NO;
2. it has a uniformly generated family and polynomial-time acceptance predicate with acceptance at least $1-2^{-q(n)}$ on YES and at most $2^{-q(n)}$ on NO.

More generally, suppose a uniformly generated family with a polynomial-time acceptance predicate satisfies $p_{C_n}(x)\ge \alpha (n)$ on length-$n$ YES inputs and $p_{C_n}(x)\le \beta (n)$ on length-$n$ NO inputs, where $\alpha (n),\beta (n)$ are polynomial-time computable rationals and there is a positive integer-valued polynomial $s(n)$ such that $0\le \beta (n)<\alpha (n)\le 1$ and $\alpha (n)-\beta (n)\ge 1\mathrm{/}s(n)$ for all sufficiently large $n$. It can be modified to achieve the same exponentially small target error $2^{-q(n)}$. This result does not assert the gap-only implication $\mathrm{B}\mathrm{Q}\mathrm{P}(\alpha ,\beta )=\mathrm{B}\mathrm{Q}\mathrm{P}$ for arbitrary endpoint thresholds.

Watrous, Proposition 3, as printed in Section IV.2 (PDF p. 13), states the broader equality $\mathrm{B}\mathrm{Q}\mathrm{P}(a,b)=\mathrm{B}\mathrm{Q}\mathrm{P}$ from an inverse-polynomial gap alone. The proof here uses only amplification for the standard BQP thresholds and a finite-table treatment of exceptional lengths. It does not use that printed gap-only equality for arbitrary $a,b$.