Quantum-Walk Search and Element Distinctness

Let $(X,P,\pi )$ be a finite reversible Markov chain with positive stationary law, as in Finite reversible Markov chain with positive stationary law, and let $\mathcal{M}\subseteq X$ be a set of marked states. Its stationary marked mass is

$\epsilon :=\pi (\mathcal{M})={\sum }_{x\in \mathcal{M}}{\pi }_x\mathrm{.}$

For a specified threshold ${\epsilon }_0\in (0,1]$, the marked-set detection promise problem has yes-instances with $\mathcal{M}\mathrm{\ne }\mathrm{\varnothing }$ and $\epsilon \ge {\epsilon }_0$, and no-instances with $\mathcal{M}=\mathrm{\varnothing }$. The required classical output is one bit distinguishing these two cases; its permitted failure probability is a separate algorithm input. In the uniform-chain case, ${\pi }_x=1\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$, so $\epsilon =\mathrm{\mid }\mathcal{M}\mathrm{\mid }\mathrm{/}\mathrm{\mid }X\mathrm{\mid }$.

The marked-state finding promise problem has inputs with $\epsilon \ge {\epsilon }_0$ and requires a classical output $x\in \mathcal{M}$. It is a different output relation from detection. A claimed output is checked by the declared finite projective measurement and marked predicate; the corresponding outcome law is Finite projective measurements and Finite POVMs and their outcome law. The encoding of $X$, the coherent marked predicate, and all state-preparation and transition circuits are supplied input data, not consequences of the finite chain matrix.

Let $X$ be the finite state set, $P$ its row-transition matrix, $\mathcal{M}\subseteq X$ the marked set, $U=X\setminus \mathcal{M}$, and $P_{UU}$ the principal submatrix indexed by $U$. For an initial probability row vector $\mu$, the hitting-time survival law is

${\mathrm{Pr}}_{\mu }({\tau }_{\mathcal{M}}>t):={\mu }_U{P}_{UU}^t{\mathbf{1}}_U,t\in {\mathbb{N}}_0,$

where ${\mu }_U$ is the restriction of $\mu$ to $U$ and ${\mathbf{1}}_U$ is the all-ones column vector on $U$. This is the finite sum of probabilities of all length-$t$ paths that remain in $U$; it does not require a path-space construction. For $U=\mathrm{\varnothing }$ the right side is $0$; for $\mathcal{M}=\mathrm{\varnothing }$ it is $1$.

The hitting time ${\tau }_{\mathcal{M}}:=\inf \{t\ge 0:X_t\in \mathcal{M}\}$ is the ${\mathbb{N}}_0\cup \{\mathrm{\infty }\}$-valued variable determined by this survival law. Its extended expectation is ${\mathbb{E}}_{\mu }{\tau }_{\mathcal{M}}={\sum }_{t\ge 0}{\mathrm{Pr}}_{\mu }({\tau }_{\mathcal{M}}>t)$, and a constant-success hitting bound is a specified integer $t$ for which ${\mathrm{Pr}}_{\mu }({\tau }_{\mathcal{M}}\le t)$ is bounded below by a positive constant. These resource conventions are kept separate.

Let $P$ be a finite symmetric row-stochastic matrix on $X$, and let $\mathcal{M}\subseteq X$, $U=X\setminus \mathcal{M}$. Define the row-stochastic absorbing matrix

$P_{xy}^{\mathrm{\prime }}=\{\begin{array}{ll}1,& x=y\in \mathcal{M},\\ 0,& x\in \mathcal{M},y\mathrm{\ne }x,\\ P_{xy},& x\in U\mathrm{.}\end{array}$

For the general row-stochastic discriminant $D(P^{\mathrm{\prime }}{)}_{xy}=\sqrt{P_{xy}^{\mathrm{\prime }}{P}_{yx}^{\mathrm{\prime }}}$ of Szegedy row-preparation map and discriminant,

$D(P^{\mathrm{\prime }})=P_{UU}\oplus I_{\mathcal{M}},$

where $P_{UU}$ is the principal submatrix on $U$. In general $P^{\mathrm{\prime }}$ need not be symmetric or reversible.

Let $X$ be a finite set of size $n\ge 2$, and let $P=(I+Q)\mathrm{/}2$ where $Q$ is a symmetric row-stochastic matrix. Let $\mathbf{u}=n^{-1\mathrm{/}2}{\mathbf{1}}_X$. Assume the second-largest eigenvalue of $P$ is at most $1-\delta$, where $0<\delta \le 1$. For $\mathcal{M}\subseteq X$, put $\epsilon =\mathrm{\mid }\mathcal{M}\mathrm{\mid }\mathrm{/}n$, $U=X\setminus \mathcal{M}$, and let ${\mathrm{\Pi }}_U$ be the coordinate orthogonal projection defined by ${\mathrm{\Pi }}_U{e}_x=e_x$ for $x\in U$ and ${\mathrm{\Pi }}_U{e}_x=0$ for $x\mathrm{\notin }U$. Let $P_U={\mathrm{\Pi }}_{U}P{\mathrm{\Pi }}_U$ restricted to vectors supported on $U$. Then $P$ has spectrum in $[0,1]$ and

$\mathrm{\parallel }{P}_U\mathrm{\parallel }\le 1-\delta \epsilon \mathrm{.}$

The empty compression has norm $0$ by convention.

Under the hypotheses of Spectral bound for a symmetric lazy walk killed on a marked set, suppose $\mathrm{\varnothing }\mathrm{\ne }\mathcal{M}\mathrm{\ne }X$ and start uniformly on $U=X\setminus \mathcal{M}$. Then

$\mathrm{Pr}({\tau }_{\mathcal{M}}>t)\le (1-\delta \epsilon {)}^t(t\in {\mathbb{N}}_0),$

so $\mathbb{E}{\tau }_{\mathcal{M}}\le 1\mathrm{/}(\delta \epsilon )$ and $O(1\mathrm{/}(\delta \epsilon ))$ steps give constant success probability. If $\mathcal{M}=X$, the hitting time is $0$.

Let a QRAM contain an ordered classical memory word $z=(z_0,\dots ,z_{L-1})\in \{0,1{\}}^L$, with $L\ge 1$. Its random-access quantum-memory gate acts on an address register encoding $i\in \{0,\dots ,L-1\}$, a target bit $b$, and the memory register by

$\mathrm{\mid }i,b,z_0\cdots z_{L-1}⟩⟼\mathrm{\mid }i,z_i,z_0\cdots z_{i-1}b{z}_{i+1}\cdots z_{L-1}⟩\mathrm{.}$

For address superpositions, this basis action is extended linearly. On valid addresses it swaps the target with the addressed memory bit, so the gate is an involutive permutation of the ordered computational basis and hence unitary; unused address encodings, if any, are fixed. One call has cost one QRAM gate-time unit by this model's convention. A read into a clean scratch target followed by copying and restoring the addressed bit uses the corresponding additional calls. The memory word itself, its address width, the circuit used to construct or update it, and the other ordinary gates are separate charged resources. This is a quantum random-access memory model; it does not assert an implementation by a bounded-arity ordinary circuit of the same gate count.

This is the finite-generation and execution procedure OP2 in research/quantum-algorithms-planning/operational-contracts.md, section “OP2 — MNRS approximate reflection and finite tolerant recursive finding”, transcribed with its declared constants and charged branches.

Input. A finite ergodic reversible row chain $(X,P,\pi )$ with ${\pi }_x>0$, a supplied positive dyadic rational lower absolute-gap bound ${\delta }_0$, a dyadic rational marked-mass lower bound ${\epsilon }_0>0$ with promise $\pi (\mathcal{M})=0$ or $\pi (\mathcal{M})\ge {\epsilon }_0$, a coherent marked-bit check of cost $C$, and a dyadic rational failure target $\rho \in (0,1)$. These finite parameter encodings suffice for real positive promises: choose dyadic lower bounds within a factor of two of the gap and nonzero marked-mass bounds, and a dyadic target in $({\rho }_{\ast }\mathrm{/}2,{\rho }_{\ast }]$ for desired failure probability ${\rho }_{\ast }$. Write $\mathrm{\mid }\sqrt{\pi }⟩={\sum }_{x\in X}\sqrt{{\pi }_x}\mathrm{\mid }x⟩$ and let $T\mathrm{\mid }x⟩=\mathrm{\mid }x⟩{\sum }_y\sqrt{P_{xy}}\mathrm{\mid }y⟩$ be the row isometry of Szegedy row-preparation map and discriminant. The supplied clean preparation $A_{\pi }$ maps its specified blank input to the stationary edge state $\mathrm{\mid }{\pi }_{\mathrm{e}\mathrm{d}\mathrm{g}\mathrm{e}}⟩=T\mathrm{\mid }\sqrt{\pi }⟩={\sum }_{x\in X}\sqrt{{\pi }_x}\mathrm{\mid }x⟩{\sum }_{y\in X}\sqrt{P_{xy}}\mathrm{\mid }y⟩,$ returns all its work registers to their specified blank states, and has charged cost $S$. The row-access interface of Finite row-preparation access model for a Szegedy walk supplies the row-preparation unitary $V_P$, its inverse, controlled forward and inverse calls, the clean-state reflection $R_0$ and its controlled call, and the swap $S$ and its controlled call. On the clean-work logical walk space these implement $R_A=2T{T}^{\ast }-I=V_P{R}_0{V}_P^{\ast }$, $U=S{R}_A$, and $W=U^2$, with each constituent charged. Supply controlled calls to $W$ and $W^{\ast }$ for the coherent QPE circuits and an exact controlled $R_A$ for the all-zero branch. A single bound $U_0$ covers each controlled $W$ or $W^{\ast }$ call and the controlled $R_A$ call, including their factorwise implementation costs. A matrix $P$ alone supplies none of these circuits.

Marked check and retained-state instrument. Write $m(x)={\mathbf{1}}_{\mathcal{M}}(x)$. The supplied exact coherent check is a unitary $B_{\mathcal{M}}$ with separately supplied inverse and specified fresh flag $F$ and scratch $J$. On the declared logical encoding it satisfies, for every $x\in X$, $b\in \{0,1\}$, and vector $\eta$ of all existing remaining registers, $B_{\mathcal{M}}(\mathrm{\mid }x⟩\mathrm{\mid }\eta ⟩\mathrm{\mid }b{⟩}_F\mathrm{\mid }0{⟩}_J)=\mathrm{\mid }x⟩\mathrm{\mid }\eta ⟩\mathrm{\mid }b\oplus m(x){⟩}_F\mathrm{\mid }0{⟩}_J\mathrm{.}$ Its unitary extension outside the logical encoding is supplied too. Thus it preserves the first label and every existing walk, phase, data, and work auxiliary on clean new scratch. In the relevant query/check cost coordinates, $C$ bounds each forward and inverse check call; declare the flag-readout cost separately and include it in $C$ in any coordinate that counts readout as a check. A flag readout uses no value-oracle query. Gate, output-bit, and new flag/scratch costs are separately priced.

On the whole existing register space set ${\mathrm{\Pi }}_1={\mathrm{\Pi }}_{\mathcal{M}}=({\sum }_{x\in \mathcal{M}}\mathrm{\mid }x⟩⟨x\mathrm{\mid })\otimes I_{\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{t}}$ and ${\mathrm{\Pi }}_0=I-{\mathrm{\Pi }}_{\mathcal{M}}$, with identity on every existing auxiliary, including every retained $K_j$. Every marked/unmarked test below uses the specified Lüders instrument ${\mathcal{I}}_a(Z)={\mathrm{\Pi }}_{a}Z{\mathrm{\Pi }}_a,a\in \{0,1\},$ in the sense of Finite instruments and conditional states: its positive-probability conditional density is ${\mathcal{I}}_a(Z)\mathrm{/}\mathrm{tr}({\mathcal{I}}_a(Z))$; no conditional state is assigned when that trace is zero. Execute the test by appending $\mathrm{\mid }0{⟩}_F\mathrm{\mid }0{⟩}_J$, applying $B_{\mathcal{M}}$, reading only the fresh flag with the explicitly chosen computational-basis Lüders maps $Y\mapsto Q_{a}Y{Q}_a$, where $Q_a=I\otimes \mathrm{\mid }a⟩⟨a{\mathrm{\mid }}_F\otimes I_J$, storing $a$ in the classical output record, and applying $B_{\mathcal{M}}^{\ast }$ to return the fresh flag and scratch to zero. Retain every pre-existing register; on an unmarked result read no finer first-label information. A marked result may then be followed by label readout and verification for output. Charge one forward check, one inverse check, and one flag readout per test, hence $O(C)$ in the stated query/check profile. The recursive marked phase flip is implemented by $B_{\mathcal{M}}$, a phase $-1$ on flag $1$, and $B_{\mathcal{M}}^{\ast }$, also with both calls charged.

Approximate stationary reflection $R(\beta )$. Set $s=\min \{q\ge 1:4^q{\delta }_0\ge 64\}$ and $k=\min \{j\ge 1:2^j\beta \ge 2\}$, using exact integer/rational comparisons. With $Q=2^s$, these comparisons give $Q\ge 8\mathrm{/}\sqrt{{\delta }_0}>2\pi \mathrm{/}\sqrt{{\delta }_0}$ using $\pi <4$ from The Gregory-Leibniz series: pi over four equals 1-1/3+1/5-1/7+.... Append $k$ separate $s$-bit zero phase registers. Coherently execute the finite QPE circuit prefix from Quantum phase estimation on $W$ in each register, using the declared controlled powers. This prefix is a unitary circuit on the full walk register and is executed on arbitrary walk states, including superpositions; the eigenvector input in the QPE analysis is not a restriction on the circuit's action. Do not measure these phase registers. If at least one phase register is nonzero, apply $-I$ to the walk state. If all are zero, apply the exact controlled row-space reflection $R_A=2T{T}^{\ast }-I$ using the charged row-preparation, inverse, and clean-state reflection calls. Reverse the $k$ coherent QPE prefixes in reverse chronological order, using the supplied controlled inverse powers. Charge $2k(2^s-1)$ controlled $W$ and $W^{\ast }$ calls, the controlled $R_A$ branch, all-zero comparisons, phase-register gates, and the allocated classical arithmetic. The all-zero branch is required: $W$ has the extra zero-phase subspace $A^{\perp }\cap B^{\perp }$, where $R_A=-I$, while $R_A=+I$ on the stationary state.

Recursive circuit $A_i$. Let $\gamma =1\mathrm{/}120$, ${\beta }_i=\gamma \mathrm{/}(16i^2)$ for $i\ge 1$, and $A_0=I$. For $i>0$, allocate a fresh $K_i$ for $R({\beta }_i)$ and execute chronologically: (i) $A_{i-1}$, the marked phase flip, and $A_{i-1}^{†}$; (ii) coherently test every older $K_j$, $j<i$, applying $-I$ if any is nonzero and otherwise applying $R({\beta }_i)$ on the walk and fresh $K_i$; compute and uncompute the control predicate; (iii) apply $A_{i-1}$. Each ${\beta }_i$ is rational, and the $k_i$ loop in $R({\beta }_i)$ is an exact rational comparison. An inverse means the exact reversed finite gate list, not a reset of measured work.

Tolerant finding wrapper. If ${\epsilon }_0\ge 1\mathrm{/}2$, take $n_s=\min \{n\ge 1:2^{-n}\le \rho \}$ fresh stationary samples, verify each label, return the first marked label, and output NO MARKED if all fail. Otherwise, let $t_{\max }$ be the least integer $t\ge 0$ such that $3^t\arcsin \sqrt{{\epsilon }_0}\ge \pi \mathrm{/}4$. Determine it by the exact algebraic threshold comparison ${\epsilon }_0\ge {\sin }^2(\pi \mathrm{/}(4\cdot 3^t))$; equality takes the $\ge$ branch. Let $n_{\mathrm{o}\mathrm{u}\mathrm{t}}=\min \{n\ge 1:(19\mathrm{/}20{)}^n\le \rho \}$, found by exact rational comparisons. In each outer trial:

1. Prepare a fresh stationary sample, test its first label, and return it if marked.
2. Prepare a fresh stationary walk state with all $K_1,\dots ,K_{t_{\max }}$ zero.
3. For $i=1,\dots ,t_{\max }$, apply $A_i$, execute the marked/unmarked Lüders test specified above, and on a marked outcome read, verify, and return the label. On an unmarked outcome retain the conditional current state and all auxiliary registers, and continue; do not reprepare or reset them.
4. If no level succeeds, discard the trial and begin the next fresh outer trial.

If all trials fail, output NO MARKED. Every loop has a finite cap; all confidence calculations, comparisons, reversible predicates, retained auxiliary space, state preparation, update, inverse, controlled, reflection, and check costs are charged. In the ${\epsilon }_0\ge 1\mathrm{/}2$ branch, the cap above gives false-negative probability at most $\rho$; in the other branch correctness and the sharper cost are proved separately in Finite reversible-walk finding cost.

Let $N\ge 2$, let $\mathcal{V}$ be a finite nonempty value set, and let $f:[N]\to \mathcal{V}$, where $[N]=\{1,\dots ,N\}$. A coherent value oracle is a supplied finite unitary $O_f$ with an explicitly specified injective encoding $\mathrm{enc}:\mathcal{V}\to \{0,1{\}}^b$ for some finite $b$, and action $\mathrm{\mid }i,z⟩\mapsto \mathrm{\mid }i,z\oplus \mathrm{enc}(f(i))⟩$ on valid addresses and target strings, as in Coherent XOR function oracle. Injectivity ensures that stored encodings compare equal exactly when the underlying values do. Oracle-query cost and ordinary gate-occurrence cost are separate coordinates under Finite circuit resource accounting. The function table or name alone supplies no oracle circuit.

For $N\ge 4$ and $2\le r\le \lfloor N\mathrm{/}2\rfloor$, the lazy Johnson walk has state space ${\mathrm{\Omega }}_r=\{S\subseteq [N]:\mathrm{\mid }S\mathrm{\mid }=r\}$ and transitions

$P(S,S)=\frac{1}{2},P(S,S\setminus \{i\}\cup \{j\})=\frac{1}{2r(N-r)}(i\in S,j\mathrm{\notin }S),$

with all other entries zero. Its marked vertices are

${\mathcal{M}}_f:=\{S\in {\mathrm{\Omega }}_r:\mathrm{\exists }i,j\in S,i\mathrm{\ne }j,f(i)=f(j)\}\mathrm{.}$

The stored data at $S$ are the $r$ labeled values $(f(i){)}_{i\in S}$. Preparing the uniform $r$-subset state and loading these values has value-query cost $S_0=r$, with subset preparation gates charged separately. A neighbor update erases the removed value and loads the added value, so its value-query cost is $U_0=2$; the XOR oracle is its own inverse. Checking whether the stored subset is marked uses no further value queries, so $C_0=0$, but comparison gates and memory accesses are charged. After measuring a marked subset, scanning its stored values outputs a colliding pair with no additional value query; the scan's gate/time cost remains separate. For $N\le 3$, use direct pairwise comparison rather than the $r$-subset walk. The lower bound $r\ge 2$ is essential: a one-element subset cannot contain a collision pair.

Let $N\ge 4096$, $2\le r\le \lfloor N\mathrm{/}2\rfloor$, and $f:[N]\to [M]$ with the injective value encoding in Element-distinctness Johnson walk and value access. Put $H=\lceil {\log }_{2}N\rceil$, $d=C=16\lceil {\log }_2(N+2)\rceil$, $R=2^{\lceil {\log }_{2}r\rceil }$, and $q=2^H$, and assume $d\le N$. Fix as part of the representation a monic irreducible polynomial of degree $H$ over ${\mathbb{F}}_2$ and its polynomial-basis field ${\mathbb{F}}_q$; the storage is canonical relative to this fixed field representation and the hash seed. Choose $H+1$ independent uniform coefficient tuples in ${\mathbb{F}}_q^d$ and use them as coefficients of degree-at-most-$(d-1)$ polynomials $p_{-1},p_0,\dots ,p_{H-1}$. For each $i\in [N]$, let $\mathsf{e}\mathsf{n}\mathsf{c}(i)$ be the field element whose $H$-bit polynomial-basis coordinate string is the $H$-bit binary encoding of $i-1$; these elements are distinct. Let $h(i)$ be the integer represented by the low ${\log }_{2}R$ bits of $p_{-1}(\mathsf{e}\mathsf{n}\mathsf{c}(i))$, and let $b_{\mathrm{\ell }}(i)$ be the low bit of $p_{\mathrm{\ell }}(\mathsf{e}\mathsf{n}\mathsf{c}(i))$. The height of $i$ is the number of consecutive $1$ bits starting at $b_0(i)$, capped at $H$; equivalently, $\mathrm{height}(i)\ge \mathrm{\ell }$ exactly when $b_0(i)=\cdots =b_{\mathrm{\ell }-1}(i)=1$.

For a subset $S\in \left(\genfrac{}{}{0px}{}{[N]}{r}\right)$, the fixed memory word has $R$ hash buckets, each with $C$ slots, and one overflow bit. If no bucket exceeds capacity, every $i\in S$ is stored in bucket $h(i)$; occupied slots are sorted by index, and each record contains $i$, $f(i)$, and its skip-list fields. A node identifier is the input index $i$; resolving it means computing $h(i)$ and scanning that bucket. If any bucket would exceed capacity, set the overflow bit and put the same fixed sentinel in the data slots. Thus the represented word is a total, unique function of the subset and seed; the skip-list structure is valid exactly when the overflow bit is zero.

The storage also contains two nested skip lists, one in increasing index order and one in lexicographic order of $(f(i),i)$. Level $\mathrm{\ell }$ of either list, for $0\le \mathrm{\ell }\le H$, contains exactly the keys with height at least $\mathrm{\ell }$; level $0$ contains all keys. Each forward pointer names a node identifier and stores its span, the difference between the source and target ranks in level $0$ (the head sentinel has rank $-1$). These spans support rank and select operations. The two lists, bucket positions, pointers, and spans are the unique ones determined by $(S,f{\mathrm{\mid }}_S,p_{-1},p_0,\dots ,p_{H-1})$; they do not depend on the path used to reach $S$. A capped search inspects at most $D=2\lfloor d\mathrm{/}2\rfloor +1$ forward entries at each level before raising an overrun flag. This definition specifies a finite representation and search convention; it does not assert a probability or cost bound.

Let $N\ge 4$ and $2\le r\le \lfloor N\mathrm{/}2\rfloor$. For the lazy Johnson transition matrix $P$ on the $r$-subsets of $[N]$ from Element-distinctness Johnson walk and value access, all eigenvalues, counted with multiplicity, are

${\lambda }_j=1-\frac{j(N+1-j)}{2r(N-r)},0\le j\le r,$

with multiplicity $\left(\genfrac{}{}{0px}{}{N}{j}\right)-\left(\genfrac{}{}{0px}{}{N}{j-1}\right)$, where $\left(\genfrac{}{}{0px}{}{N}{-1}\right)=0$. They are nonnegative, and for the uniform stationary law the absolute spectral gap, in the sense of Absolute spectral gap of a finite reversible chain, is

$\delta (P)=1-{\lambda }_1=\frac{N}{2r(N-r)}\mathrm{.}$

Let $(X,P,\pi )$ be a finite ergodic reversible chain with actual absolute spectral gap ${\delta }_{\mathrm{a}\mathrm{c}\mathrm{t}}\in (0,1]$. Supply the algorithm with a dyadic rational lower bound ${\delta }_0\in (0,{\delta }_{\mathrm{a}\mathrm{c}\mathrm{t}}]$ and suppose the marked set is empty or has stationary mass at least the dyadic rational lower bound ${\epsilon }_0\in (0,1]$. Let the dyadic rational failure target be $\rho \in (0,1)$. Let $S_0$ be the cost of preparing the stationary walk state, $U_0$ a common upper bound for one controlled $W$ or $W^{\ast }$ update and the exact controlled row-space reflection $R_A$ used by the construction, and $C$ the cost of a coherent marked check. For $0<{\epsilon }_0<1\mathrm{/}2$, one outer trial of MNRS finite reversible-walk finding with gap input ${\delta }_0$ has one-sided error, finds a marked state with probability at least $1\mathrm{/}20$ when one exists, and uses

$2S_0+O\text{\hspace{0.17em}⁣}\left(\frac{1}{\sqrt{{\epsilon }_0}}(\frac{U_0}{\sqrt{{\delta }_0}}+C)\right)\mathrm{.}$

in the corresponding query/update/check cost coordinates. The capped wrapper with failure target $\rho \in (0,1)$ uses $O((S_0+{\epsilon }_0^{-1\mathrm{/}2}(U_0\mathrm{/}\sqrt{{\delta }_0}+C))(1+\ln (1\mathrm{/}\rho )))$ in that profile. When ${\epsilon }_0\ge 1\mathrm{/}2$, its direct-sampling branch uses $O((S_0+C)(1+\ln (1\mathrm{/}\rho )))$. If the actual gap is dyadic and supplied exactly, one may set ${\delta }_0={\delta }_{\mathrm{a}\mathrm{c}\mathrm{t}}$; otherwise a dyadic lower bound within a factor of two gives the same asymptotic bound in the actual gap. For gate, width, precision, and bit-time coordinates, the phase-register gates, controlled reflection, comparisons, numerical generation, and retained workspace are charged separately.