Bounded-error repetition amplification is correct and uniform

Fix a promised input $x$. For each input bit $x_i\in \{0,1\}$, the basis action of CNOT maps $\mathrm{\mid }{x}_i⟩\mathrm{\mid }0{⟩}^{\otimes (r-1)}$ to $\mathrm{\mid }{x}_i{⟩}^{\otimes r}$; applying this independently to each position produces $r$ exact copies of $\mathrm{\mid }x⟩$. This uses only a computational-basis input and asserts no cloning of arbitrary superpositions. By [F7], CNOT has the required basis action. The $r$ base circuits then act on disjoint full wire blocks, so by [A1] the prepared joint state is ${\psi }_x^{\otimes r}$, where ${\psi }_x$ is the single-run output state. For any output strings $z_1,\dots ,z_r$, its joint probability is ${\sum }_{w_1,\dots ,w_r}{\prod }_{i=1}^r\mathrm{\mid }⟨P_O{\psi }_x,e_{z_i,w_i}{⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}{\mathrm{\mid }}^2={\prod }_{i=1}^r{p}_C(z_i\mid x),$ by finite distributivity and [F4]. Hence the measured output strings are mutually independent with the single-run law, and $X_i={\mathbf{1}}_{\{A_n(x,z_i)=1\}}$ are independent Bernoulli variables with common parameter $p=p_C(x)$.

In ordinary mode [F6] bounds the base description length, operation count, and width polynomially. In oracle mode the same bounds follow directly from the explicit code: a machine started on $n$ input cells and run for $T(n)$ transitions can print at most $n+T(n)+1$ bits, each record occupies at least one bit, and the width is unary. The clocks and bit lengths of $\alpha ,\beta ,\delta ,s$ are polynomial, so $r$ is polynomial. In either mode the repeated circuit uses exactly $rg(C_n)+n(r-1)$ operations and $rw(C_n)$ wires. Copying a record changes each wire index by a block offset with $O(\log (rw(C_n)+2))$ bits; the unary total-wire header has length $rw(C_n)$, and the extra CNOT list has $n(r-1)$ records. In oracle mode each original record's explicit list of wires is copied in full, its port/variant identifier is unchanged, and the entire descriptor table is copied once. Hence the complete repeated description has polynomial length and is produced in polynomial time by running the supplied machines, scanning and copying the base list, and adding offsets by binary arithmetic. These are polynomially many operations on polynomially many bits, implementable by repeated scans on the one-tape machine. A serial layering gives depth at most the total operation count.

Put $S={\sum }_{i=1}^r{X}_i$ and $\mu =rp$. The output predicate accepts exactly when $S\ge r(\alpha +\beta )\mathrm{/}2$. If $x$ is YES, then $p\ge \alpha$ and $\mu -r(\alpha +\beta )\mathrm{/}2=r(p-\alpha )+r(\alpha -\beta )\mathrm{/}2\ge r\mathrm{/}(2s)\mathrm{.}$ Thus a false rejection is contained in $\{\mathrm{\mid }S-\mu \mathrm{\mid }\ge r\mathrm{/}(2s)\}$.

If $x$ is NO, then $p\le \beta$ and $r(\alpha +\beta )\mathrm{/}2-\mu =r(\alpha -\beta )\mathrm{/}2+r(\beta -p)\ge r\mathrm{/}(2s)\mathrm{.}$ Thus a false acceptance is contained in the same two-sided deviation event $\{\mathrm{\mid }S-\mu \mathrm{\mid }\ge r\mathrm{/}(2s)\}$.

In oracle mode no added CNOT record is a query slot, while each original slot occurs exactly once per block. Therefore $g_{\mathrm{o}\mathrm{r}\mathrm{d}}(C_n^{\mathrm{r}\mathrm{e}\mathrm{p}})=r{g}_{\mathrm{o}\mathrm{r}\mathrm{d}}(C_n)+n(r-1)$ and $N_{j,v}(C_n^{\mathrm{r}\mathrm{e}\mathrm{p}})=r{N}_{j,v}(C_n)$. Summing over variants gives $q_j(C_n^{\mathrm{r}\mathrm{e}\mathrm{p}})=r{q}_j(C_n)$; multiplying each variant count by its unchanged declared charge and summing gives $Q_j(C_n^{\mathrm{r}\mathrm{e}\mathrm{p}})=r{Q}_j(C_n)$. Raw call counts are at most the total operation count; large binary-encoded charges do not justify an unconditional polynomial charged-cost bound. The construction uses no new inverse or controlled access. The same instantiated unitary ports act independently on the disjoint blocks, so the factorization in step 1.1 remains valid, and [F4] applies to each instantiated finite unitary circuit. Ordinary mode contains no oracle slots and remains a circuit over exactly the original library.

Finite event probabilities are sums of nonnegative weights by [F2], so containment makes the probability of either error event in step 2.1 and step 2.2 at most that of the deviation event. Apply [F3] with $t=r\mathrm{/}(2s)$; its probability is at most $2\exp (-r\mathrm{/}(2s^2))$. Since $\delta =u\mathrm{/}v$ with $u\ge 1$, $\delta \ge 1\mathrm{/}v$ and $v\ge 2$. Therefore $\ln (2\mathrm{/}\delta )\le \ln (2v)=\ln 2+\ln v<1+\mathrm{\ell }(v),$ because $\ln 2<1$ and $\ln v=(\ln 2){\log }_{2}v<{\log }_{2}v<\mathrm{\ell }(v)$. Substituting $r=2s^2(\mathrm{\ell }(v)+1)$ gives $2\exp (-r\mathrm{/}(2s^2))<2\exp (-\ln (2\mathrm{/}\delta ))=\delta$. This proves both promised error bounds without evaluating an irrational logarithm.

For the declared interfaces covered by the Statement, the input-copy CNOTs act only on the repeated data registers. On the declared ancillary registers the copy unitary is the identity; composing it with the $r$ blockwise exact contracts therefore preserves the clean or dirty return condition, with data target equal to the product of the base targets composed after that copy unitary. Their declared counts are multiplied by $r$; the $n(r-1)$ additional zero-start input-copy wires remain included in total width, with no claim that they return clean. The output predicate runs $A_n$ on each of the $r$ strings, counts successes, computes the rational threshold by exact integer additions and multiplications, and compares the two integers. These operations use polynomial time and space in the polynomially many input bits. Together with step 1.2 and step 2.3, this proves the claimed separate resource bounds and exact query scaling.