Algorithm Composition, Precision Budgets, and Dequantization

Let $A:{\mathbb{R}}^n\to {\mathbb{R}}^m$ have a singular value decomposition $A=U\mathrm{\Sigma }{V}^T$ as in Every linear map between finite-dimensional real or complex inner product spaces admits a singular value decomposition, let $\sigma >0$, and let $0<\eta \le 1$. Write $P_{>}$ for the orthogonal projection onto the span of right singular vectors whose singular values are at least $\sigma (1+\eta )$, and $E$ for the span of right singular vectors whose singular values lie in $[\sigma (1-\eta ),\sigma (1+\eta ))$. For any orthogonal projection $P_E$ with range contained in $E$, a threshold-band target is $A_{\sigma ,\eta }:=A(P_{>}+P_E)\mathrm{.}$

The choice inside the threshold band is allowed to vary; all singular directions above the band are retained and all directions below it are discarded. The definition is independent of the choice of orthonormal bases within singular subspaces because it is stated using their subspaces. If a singular value equals the upper endpoint it belongs to $P_{>}$; equality at the lower endpoint belongs to $E$. A range contained in $\ker A$ contributes zero to $A_{\sigma ,\eta }$. However, an allowed $P_E$ can mix nullspace directions with nonzero singular directions when both lie in $E$, so changing that projection can change the target.

Let $A\in {\mathbb{R}}^{m\times n}$ have singular values ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge 0$, padded by zeros to $\min (m,n)$. For an integer $0\le k\le \min (m,n)$ let $A_k$ be the truncation to the first $k$ singular terms of an SVD of $A$. Then $\mathrm{rank}(A_k)\le k$, and for every matrix $B$ with $\mathrm{rank}(B)\le k$, $\mathrm{\parallel }A-A_k{\mathrm{\parallel }}_F^2={\sum }_{j>k}{\sigma }_j^2\le \mathrm{\parallel }A-B{\mathrm{\parallel }}_F^2\mathrm{.}$

For a positive integer $L$ and density operators ${\rho }_j,{\sigma }_j$ on finite-dimensional $H_j$, $j=1,\dots ,L$, $D({⨂}_{j=1}^L{\rho }_j,{⨂}_{j=1}^L{\sigma }_j)\le {\sum }_{j=1}^{L}D({\rho }_j,{\sigma }_j)\mathrm{.}$ Consequently every finite POVM on the product output changes its outcome law by at most this sum.

A finite $L$-stage composition contract consists of nonzero finite-dimensional complex Hilbert spaces $H_0,\dots ,H_L$ and, for each $j=1,\dots ,L$, an ideal channel ${\mathrm{\Phi }}_j:\mathcal{L}(H_{j-1})\to \mathcal{L}(H_j)$ and an implemented channel ${\tilde{\mathrm{\Phi }}}_j$ with the same domain and codomain. Channels are completely positive and trace-preserving on the full operator space, as in Finite-dimensional quantum channel. Products act right to left, so ${\mathrm{\Phi }}_L\cdots {\mathrm{\Phi }}_1$ applies stage $1$ first, following Denotational semantics of a finite layered circuit.

For channels on the same nonzero finite-dimensional complex Hilbert input and output spaces define the normalized diamond distance $d_{\diamond }(\mathrm{\Psi },\mathrm{\Phi }):=\frac{1}{2}\mathrm{\parallel }\mathrm{\Psi }-\mathrm{\Phi }{\mathrm{\parallel }}_{\diamond },$ where $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_{\diamond }$ is the unhalved supremum of induced trace norms over all finite reference spaces, as in Diamond Norm. For density operators $\rho ,\sigma$ define $D(\rho ,\sigma )=\frac{1}{2}\mathrm{\parallel }\rho -\sigma {\mathrm{\parallel }}_1$, as in Trace Distance. For probability distributions $p,q$ on a common finite output alphabet define $d_{\mathrm{T}\mathrm{V}}(p,q)=\frac{1}{2}{\sum }_a\mathrm{\mid }p(a)-q(a)\mathrm{\mid }$.

The local channel error at stage $j$ is $d_{\diamond }({\tilde{\mathrm{\Phi }}}_j,{\mathrm{\Phi }}_j)$. The final channel error is $d_{\diamond }({\tilde{\mathrm{\Phi }}}_L\cdots {\tilde{\mathrm{\Phi }}}_1,{\mathrm{\Phi }}_L\cdots {\mathrm{\Phi }}_1)$. A final output-distribution error is total variation distance between the finite laws obtained by applying a declared final POVM to the two output states. A failure probability is the probability of a declared failure event in the finite execution history. These four quantities have different definitions and must be reported separately.

When an input is entangled with a finite reference register, include that reference in the density operator of Density operator and retain it through the channel call; the diamond distance already takes the supremum over such references. Channel, state, and classical output contracts are distinct. Cost coordinates for input description and preprocessing, state preparation, gates, queries including controlled and inverse access, workspace, measurement, postprocessing, and classical output are specified separately by Classical output, quantum-state output, and access costs and Circuit-family and computation cost model.

Let $L\ge 1$, let $H_0,\dots ,H_L$ be nonzero finite-dimensional complex Hilbert spaces, and let ${\mathrm{\Phi }}_j,{\tilde{\mathrm{\Phi }}}_j:\mathcal{L}(H_{j-1})\to \mathcal{L}(H_j)$ be channels for $j=1,\dots ,L$. Then $d_{\diamond }({\tilde{\mathrm{\Phi }}}_L\cdots {\tilde{\mathrm{\Phi }}}_1,{\mathrm{\Phi }}_L\cdots {\mathrm{\Phi }}_1)\le {\sum }_{j=1}^L{d}_{\diamond }({\tilde{\mathrm{\Phi }}}_j,{\mathrm{\Phi }}_j),$ where $d_{\diamond }$ is the normalized distance in End-to-end channel and output error contract. For any finite reference space $R$, input density operator $\rho$ on $H_0\otimes R$, and finite final POVM on $H_L\otimes R$, the total variation distance between the two final outcome laws is at most the same sum. The claim is uniform over the reference dimension; no product-input assumption is made.

For a positive integer $L$ and a finite family of matching channel pairs ${\mathrm{\Phi }}_j,{\mathrm{\Psi }}_j:\mathcal{L}(H_j)\to \mathcal{L}(K_j)$, $j=1,\dots ,L$, on nonzero finite-dimensional complex Hilbert spaces, $d_{\diamond }({⨂}_{j=1}^L{\mathrm{\Phi }}_j,{⨂}_{j=1}^L{\mathrm{\Psi }}_j)\le {\sum }_{j=1}^L{d}_{\diamond }({\mathrm{\Phi }}_j,{\mathrm{\Psi }}_j)\mathrm{.}$ For every nonzero finite-dimensional reference space $R$, every density operator $\rho$ on $({⨂}_{j=1}^L{H}_j)\otimes R$, and every finite POVM on $({⨂}_{j=1}^L{K}_j)\otimes R$, the total variation distance between the outcome laws after applying $({⨂}_j{\mathrm{\Phi }}_j)\otimes {\mathrm{id}}_R$ and $({⨂}_j{\mathrm{\Psi }}_j)\otimes {\mathrm{id}}_R$ to $\rho$ is at most the same sum. No product-input assumption is made; $\rho$ may be entangled across the component inputs and reference.

Inputs: a finite list of $L$ stage compilers $C_1,\dots ,C_L$, each accepting a rational local precision and, when it uses randomized verification, a rational local failure budget; rational targets $0<\epsilon ,\delta <1$; and declared stage input/output interfaces $T_0,\dots ,T_L$, including encodings or register spaces. Stage $j$ must accept $T_{j-1}$ and return $T_j$ at every admissible budget, so adjacent interfaces match. For a channel pipeline these are the matching spaces and channel interfaces of End-to-end channel and output error contract. Each compiler is assumed to terminate with an implemented stage, its output type, and its actual cost record under Classical output, quantum-state output, and access costs. The sequential pipeline is run under the same declared cost-accounting model.

Output: a pipeline from $T_0$ to $T_L$, together with the budget lists and cost records below. If $L=0$, a single interface $T_0$ is supplied; return its identity procedure, empty budget lists, no stage records, and an auxiliary record charging any identity-interface and allocator work. If $L\ge 1$, set ${\epsilon }_j=\epsilon \mathrm{/}L$ and ${\delta }_j=\delta \mathrm{/}L$ for each $j$. For $j=1,\dots ,L$ in order, invoke $C_j({\epsilon }_j,{\delta }_j)$ once when stage $j$ uses randomized verification, and otherwise invoke $C_j({\epsilon }_j)$ once and mark its failure coordinate not applicable. Retain each returned implementation, output type, and actual stage cost record, then compose the stages chronologically. Record shared input/preprocessing, allocation arithmetic, and any interstage wiring, control, postprocessing, or final-output costs in a separate auxiliary record, counting each operation once. Return the composed implementation, local budget lists, per-stage records, and auxiliary record. The correctness theorem gives an additive resource bound from these records under its explicit accounting assumptions; a requested precision alone does not determine an implementation or its cost.

The correctness claim is separate: Allocated local errors meet the global budget proves the global channel and failure bounds and composes the recorded cost coordinates under explicit stage and pipeline accounting assumptions. This algorithm does not create implementations or amplify a compiler's error; each compiler's correctness method and cost remain part of its own guarantee.

An algorithm result contract declares exactly one output type:

• Classical string: a finite bit string in a stated encoding. Its cost includes every output bit written and any required formatting.
• Classical sample: an element of a stated finite set, with the output law and the cost of writing the sample encoding.
• Quantum state: a density operator, as in Density operator, on an explicitly named finite register, produced by a declared state-preparation procedure. This does not mean that its amplitude list or a classical description of the state is output.

The accompanying cost record keeps separate: input encoding length and preprocessing; each data-structure or oracle operation; state preparation and its inverse or controlled forms; ordinary gates, controlled gates, and inverse gates; register width and clean/dirty/other workspace; measurement and classical postprocessing; finite-gate approximation precision; and classical output bits. A coordinate that the model does not use is marked not applicable. No state-preparation oracle, QRAM, controlled access, inverse access, or full classical state description is assigned zero cost without an explicit interface.

For the exact continuous-rotation table model, QC24 State Preparation Cost Model and QC24 State Preparation specify the table input and circuit procedure; QC24 Explicit State-Preparation Cost Guarantee gives the corresponding $D=2^n$ gate/ancilla upper bound. That bound uses exact continuous rotations and gives no finite-gate or uniform bit-time claim. For a fixed finite gate set, Solovay–Kitaev Unitary Compiler for SU(2) and Solovay–Kitaev Error and Resource Bound supply a separate approximation and resource contract. The circuit-family coordinates are those of Circuit-family and computation cost model.

A heralded procedure has an explicit finite outcome set containing success and failure, a success probability $p_s$, and a declared output type. For an input density operator $\rho$ as in Density operator, its success branch is the subnormalized state ${\mathcal{I}}_s(\rho )$ of the instrument Finite instruments and conditional states, with $p_s=\mathrm{tr}({\mathcal{I}}_s(\rho ))$. If $p_s>0$, its conditional output state is ${\rho }_s={\mathcal{I}}_s(\rho )\mathrm{/}{p}_s$; if $p_s=0$, no normalized conditional state is assigned and the branch is denoted $\mathrm{\perp }$. The outcome law is specified by the instrument and the POVM conventions of Finite POVMs and their outcome law.

The contract states separately (i) the success probability, (ii) the guarantee conditional on success, (iii) any unconditional guarantee including failure, and (iv) the cost of verification and of outputting or recording the success flag. An acceptance probability from Quantum acceptance probability for a finite promise computation is not itself a conditional-state guarantee. A claim about a quantum state output uses the type and cost distinctions in Classical output, quantum-state output, and access costs.

For a finite complex vector $v=(v_1,\dots ,v_n)\in {\mathbb{C}}^n$, put $\mathrm{\parallel }v{\mathrm{\parallel }}_2=({\sum }_{i=1}^n\mathrm{\mid }{v}_i{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$, where $\mathrm{\mid }\cdot \mathrm{\mid }$ is the complex modulus of Real and imaginary parts, complex conjugation, and modulus. Its squared-entry distribution is $D_v(i)=\mathrm{\mid }{v}_i{\mathrm{\mid }}^2\mathrm{/}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$ on $[n]$ when $\mathrm{\parallel }v{\mathrm{\parallel }}_2>0$. A vector has ℓ2 sample/query access when the interface supplies: (a) an entry query returning $v_i$; (b) its norm $\mathrm{\parallel }v{\mathrm{\parallel }}_2$; and (c) a sample distributed according to $D_v$. For any finite adaptive sequence of sample calls, conditioned on the preceding history and the current requested sampler, each returned index has the declared law and uses fresh randomness independent of that history; in particular, repeated calls to a fixed sampler are mutually independent in the sense of Pairwise and mutual independence of finite-valued random variables. Every draw is charged. The interface states the cost and precision of every query, norm computation, and sample, and any preprocessing or storage cost. If $v=0$, $D_v$ is undefined and the sampler returns the explicit status ZERO; it does not return a fictitious normalized sample.

For a finite real matrix $A\in {\mathbb{R}}^{m\times n}$, put $\mathrm{\parallel }A{\mathrm{\parallel }}_F=({\sum }_{i=1}^m{\sum }_{j=1}^n{A}_{ij}^2{)}^{1\mathrm{/}2}$, the Frobenius norm of The Frobenius norm $\parallel A{\parallel }_F=({\sum }_{i,j}\mathrm{\mid }{a}_{ij}{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$ on real or complex matrices. Row and column ℓ2 access supplies entry queries, row and column norms, and samplers for each nonzero row and column according to its squared-entry distribution. These real rows and columns are instances of the vector interface above. It also declares preprocessing, storage, and whether their costs are amortized. The common row sampler $i\sim D_A$ has law $\mathbb{P}(i)=\mathrm{\parallel }{A}_{i,\ast }{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$ for $A\mathrm{\ne }0$, and the column sampler $j\sim D_{A^T}$ has law $\mathbb{P}(j)=\mathrm{\parallel }{A}_{\ast ,j}{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }A{\mathrm{\parallel }}_F^2$; zero rows and columns have probability zero. An all-zero matrix returns ZERO for a request for a norm-normalized sample. All row-vector, column-vector, matrix-level row, and matrix-level column samplers obey the same conditional fresh-randomness rule; every draw is charged. Access to entries alone does not imply either sampler. The access and output costs are recorded separately under Classical output, quantum-state output, and access costs, and the distributions are finite probability laws as in Finite probability spaces, outcome weights, events, and event probabilities.

This is an input-data structure assumption. It is not a quantum circuit, state-preparation oracle, QRAM, or an assertion that the preprocessing needed to implement it is sublinear. The Tang matrix algorithms on this page specialize to real matrices; no complex-matrix extension of those algorithms is asserted.

In an output-interface model with $N$ designated output positions, where one bit operation can write at most one position and every output position must be written, emitting an $N$-bit classical string costs at least $N$ bit operations. This lower bound concerns the output interface; it is not a lower bound on preparing a quantum state or on producing a succinct circuit description.

Inputs: a nonzero real matrix $A\in {\mathbb{R}}^{m\times n}$ with the exact row/column ℓ2 sample/query interface of ℓ2 sample/query access to vectors and matrices, a threshold $0<\sigma \le \mathrm{\parallel }A{\mathrm{\parallel }}_F$, tolerances $0<ϵ\le 1$ and $0<\eta \le 1$, and an integer sample count $q\ge 1$. The procedure returns a compact description; it does not write all $mn$ entries of the output matrix.

1. Sample $i_1,\dots ,i_q$ independently from the row distribution $D_A$. Form the conceptual matrix $S\in {\mathbb{R}}^{q\times n}$ whose $r$th row is $A_{i_r,\ast }\mathrm{/}\sqrt{q{D}_A(i_r)}$. The entries of $S$ can be queried through the stored row indices; no zero-probability row is selected.
2. Define a column distribution $F$ by choosing $r$ uniformly in $[q]$ and then sampling a column from $D_{S_{r,\ast }}$. Draw $j_1,\dots ,j_q$ independently from $F$. Form $W\in {\mathbb{R}}^{q\times q}$ with $W_{r,c}=S_{r,j_c}\mathrm{/}\sqrt{qF(j_c)}$. A sampled column has $F(j_c)>0$; otherwise return INVALID.
3. Compute a singular value decomposition of $W$. Retain the left singular vectors $u^{(1)},\dots ,u^{(k)}$ whose singular values ${\widehat{\sigma }}_1,\dots ,{\widehat{\sigma }}_k$ are strictly greater than $\sigma$, and set $\widehat{U}=[u^{(1)}\cdots u^{(k)}]$ and $\widehat{\mathrm{\Sigma }}=\mathrm{diag}({\widehat{\sigma }}_1,\dots ,{\widehat{\sigma }}_k)$. If $k=0$, return the zero matrix description. Otherwise return the row indices and the matrices needed to evaluate $D:=A{S}^T\widehat{U}{\widehat{\mathrm{\Sigma }}}^{-2}{\widehat{U}}^{T}S\mathrm{.}$

The sample count $q$, matrix-entry and norm queries, sample operations, arithmetic, SVD, storage, and any finite-precision implementation are charged in the declared access model. Correctness, success probability, approximation error, and the parameter-dependent choice of $q$ are separate claims of ModFKV low-rank approximation supplier.

Inputs: an integer $k\ge 1$, vectors $v_1,\dots ,v_k\in {\mathbb{R}}^n$ with ℓ2 sample/query access, real coefficients $w_1,\dots ,w_k$, and a positive integer cap $R$. Set $x={\sum }_{j=1}^k{w}_j{v}_j$ and $S={\sum }_{j=1}^k\mathrm{\parallel }{w}_j{v}_j{\mathrm{\parallel }}_2^2$. Output: an index $i\in [n]$ or FAIL.

If $S=0$, return FAIL. Otherwise, for each of at most $R$ trials:

1. Using fresh randomness, choose $j$ with probability $\mathrm{\parallel }{w}_j{v}_j{\mathrm{\parallel }}_2^2\mathrm{/}S$, then sample $i$ from $D_{v_j}$. A zero-weight term is never chosen, so every requested vector distribution is defined.
2. Query all $v_{h,i}$ and set $a_i:=\{\begin{array}{ll}{\displaystyle \frac{(\sum _{h=1}^k{w}_h{v}_{h,i}{)}^2}{k\sum _{h=1}^k(w_h{v}_{h,i}{)}^2}},& {\sum }_h(w_h{v}_{h,i}{)}^2>0,\\ 0,& {\sum }_h(w_h{v}_{h,i}{)}^2=0.\end{array}$ By Cauchy--Schwarz, $0\le a_i\le 1$, so this is a valid acceptance probability.
3. With a fresh independent acceptance coin, accept index $i$ with probability $a_i$ and return $i$ upon acceptance.

If all $R$ trials reject, return FAIL. When $x=0$ but $S>0$, every defined acceptance probability is zero and the cap still forces a finite FAIL output. No normalized target distribution is assigned when $x=0$. All samples, entry queries, random bits, cap, and output writing are charged. Correctness and cost of the linear-combination sampler ↗ proves the target law on the accepted branch and the failure and query bounds under its separate hypotheses on $x$, the cancellation ratio, and $R$.

Let $M\in {\mathbb{R}}^{a\times b}$ be nonzero, let $q_1,\dots ,q_a$ be a probability distribution satisfying $q_i\ge \alpha \mathrm{\parallel }{M}_{i,\ast }{\mathrm{\parallel }}_2^2\mathrm{/}\mathrm{\parallel }M{\mathrm{\parallel }}_F^2$ for some $0<\alpha \le 1$, and let $p$ be a positive integer. Draw $p$ independent row indices $I_1,\dots ,I_p$ from this distribution and form $N\in {\mathbb{R}}^{p\times b}$ with row $t$ equal to $M_{I_t,\ast }\mathrm{/}\sqrt{p{q}_{I_t}}$; a zero row with $q_i=0$ is never sampled. Then $\mathbb{E}\mathrm{\parallel }{M}^{T}M-N^{T}N{\mathrm{\parallel }}_F^2\le \frac{\mathrm{\parallel }M{\mathrm{\parallel }}_F^4}{\alpha p},$ and for every $\theta >0$, $\mathbb{P}(\mathrm{\parallel }{M}^{T}M-N^{T}N{\mathrm{\parallel }}_F\ge \theta \mathrm{\parallel }M{\mathrm{\parallel }}_F^2)\le \frac{1}{\alpha p{\theta }^2}\mathrm{.}$ For column sampling, assume the analogous probability lower bound on columns and apply the result to $M^T$.

In particular, let $A\in {\mathbb{R}}^{m\times n}$ be nonzero with $F=\mathrm{\parallel }A{\mathrm{\parallel }}_F$, and use $p$ samples at each of two stages. First draw independent $I_r$ with probabilities $d_i=\mathrm{\parallel }{A}_{i,\ast }{\mathrm{\parallel }}_2^2\mathrm{/}{F}^2$ and set $S_{r,\ast }=A_{I_r,\ast }\mathrm{/}\sqrt{p{d}_{I_r}}$. Conditional on $S$, draw independent $J_c$ with probabilities $f_j=\mathrm{\parallel }{S}_{\ast ,j}{\mathrm{\parallel }}_2^2\mathrm{/}{F}^2$ and set $W_{\ast ,c}=S_{\ast ,J_c}\mathrm{/}\sqrt{p{f}_{J_c}}$. These are the exact normalized two-stage sketches; zero-probability indices are never selected. Then $\mathrm{\parallel }S{\mathrm{\parallel }}_F=\mathrm{\parallel }W{\mathrm{\parallel }}_F=F$, both Gram estimators are unbiased (the second conditional on $S$), and $\mathbb{E}\mathrm{\parallel }{A}^{T}A-S^{T}S{\mathrm{\parallel }}_F^2\le F^4\mathrm{/}p,\mathbb{E}[\mathrm{\parallel }S{S}^T-W{W}^T{\mathrm{\parallel }}_F^2\mid S]\le F^4\mathrm{/}p\mathrm{.}$ For every $\theta >0$, the probability that either Gram error is at least $\theta F^2$ is at most $2\mathrm{/}(p{\theta }^2)$; the two errors need not be independent.

Let $x,y\in {\mathbb{R}}^n$ be nonzero, and define $D_x(i)=x_i^2\mathrm{/}\mathrm{\parallel }x{\mathrm{\parallel }}_2^2$ and $D_y(i)=y_i^2\mathrm{/}\mathrm{\parallel }y{\mathrm{\parallel }}_2^2$. Then $d_{\mathrm{T}\mathrm{V}}(D_x,D_y)\le \frac{2\mathrm{\parallel }x-y{\mathrm{\parallel }}_2}{\mathrm{\parallel }x{\mathrm{\parallel }}_2}\mathrm{.}$ The bound is valid even when its right side exceeds $1$.

Let $x\in {\mathbb{R}}^n$ be nonzero with exact norm, ℓ2 sample access, and entry-query access, and let $y\in {\mathbb{R}}^n$ have entry-query access and known norm. For $0<ϵ\le 1$, a positive integer $m\ge 16\mathrm{/}{ϵ}^2$, and a positive integer $r$ with $2^{-r}\le \delta <1$, there is a finite estimator using the lower median of $r$ block means, with $mr$ samples from $x$ and at most $mr$ entry queries to each of $x$ and $y$, such that $\mathbb{P}(\mathrm{\mid }\widehat{\mu }-⟨x,y⟩\mathrm{\mid }>ϵ\mathrm{\parallel }x{\mathrm{\parallel }}_2\mathrm{\parallel }y{\mathrm{\parallel }}_2)\le \delta \mathrm{.}$ If $y=0$, return $0$ without sampling. All sample and entry-query costs are charged.

Consider a procedure with finitely many stages $j=1,\dots ,L$ and a finite probability space of execution histories. Let ${\delta }_j\ge 0$ for every stage, and let $F_j$ be the event that stage $j$ is the first failing stage. If, after every successful history of positive probability that reaches stage $j$, the conditional probability of failure at stage $j$ is at most ${\delta }_j$, then $\mathbb{P}(\text{some stage fails})\le {\sum }_{j=1}^L{\delta }_j\mathrm{.}$ No independence hypothesis is required. If $r$ fresh trials are mutually independent and each succeeds with probability at least $p\in [0,1]$, their miss probability is at most $(1-p{)}^r\le e^{-pr}$. For a common success probability $p>0$, the expected number of trials capped at $r$ is $[1-(1-p{)}^r]\mathrm{/}p$, which tends to $1\mathrm{/}p$ as $r\to \mathrm{\infty }$.