Element-distinctness gate cost in the QRAM model

For $N\ge 4096$, the clamp in [F1] is $r=\lfloor N^{2\mathrm{/}3}\rfloor$. Set $m=\lceil {\log }_2(N+2)\rceil$, $H=\lceil {\log }_{2}N\rceil$, $d=C=16m$, $R=2^{\lceil {\log }_{2}r\rceil }$, and $q=2^H$. The function $({\log }_2(x+2)+1)\mathrm{/}{x}^{2\mathrm{/}3}$ decreases for $x\ge 4096$, because its logarithmic derivative is $1\mathrm{/}((x+2)\ln 2({\log }_2(x+2)+1))-2\mathrm{/}(3x)<0$; indeed $2(x+2)\ln 2({\log }_2(x+2)+1)>3x$ there. Since ${\log }_2(4098)<13$, this gives $d\le 16({\log }_2(N+2)+1)\le 224N^{2\mathrm{/}3}\mathrm{/}256=7N^{2\mathrm{/}3}\mathrm{/}8$. Also $r\ge N^{2\mathrm{/}3}-1\ge 255N^{2\mathrm{/}3}\mathrm{/}256$, so $d\le r\le N\mathrm{/}2$ and $d\le N\le q$. Finally $r\le R<2r\le N$. By [F9], fix a polynomial-basis representation of ${\mathbb{F}}_q$; its irreducible polynomial is a finite hardwired setup description whose generation time is separate.

For fixed $S$ and seed, place each $(i,f(i))$ in its hash bucket and build the two canonical lists of [F12]. Pad each list to a power-of-two length $L=O(r)$ with sentinels. A bitonic sorting network recursively sorts the two halves in opposite directions and merges them by comparing pairs at distance $L\mathrm{/}2$, then recursively merging both halves. A bitonic sequence becomes, after thresholding its keys at any fixed threshold, a circular interval of $1$ bits; the half-distance compare-exchanges place either all $0$ bits in the low half or all $1$ bits in the high half, leaving each half bitonic. Induction proves merge correctness, and thresholding between any alleged inverted output pair would give a Boolean failure, so the network sorts the original keys. A merge uses $O(L\log L)$ comparisons and the sorting recurrence gives $O(L{\log }^{2}L)$ compare-exchanges. Each comparison of $w=O(\log N+b)$-bit records uses $O(w)$ Boolean gates; compute its decision bit into clean history, conditionally swap the records using Fredkin gates, copy the sorted list records, and reverse the network to erase the comparison history. This gives a reversible compute-copy-uncompute sort using $O(r\mathrm{polylog}(N+M))$ gate-time. A scan of the sorted lists computes all level links and spans in $O(rH)$ writes and computes the collision counter from the equal-value runs. If an insertion would exceed a bucket's $C$ slots, use the fixed overflow sentinel of [F12]. The resulting storage is a deterministic function of $(S,\text{seed},f{\mathrm{\mid }}_S)$, so it is independent of the history of the walk.

Choose $H+1$ independent uniform coefficient vectors in ${\mathbb{F}}_q^d$ and use them for $p_{-1},p_0,\dots ,p_{H-1}$ in [F12]. For any $t\le d$ distinct addresses, the first $t$ columns of their Vandermonde evaluation matrix have determinant ${\prod }_{a<b}(x_b-x_a)\mathrm{\ne }0$, so the evaluations are uniform on ${\mathbb{F}}_q^t$. Thus the bucket labels are $d$-wise independent and uniform in $[R]$, and each promotion-bit family is $d$-wise independent and fair. Preparing the coefficient strings uniformly with Hadamards uses $(H+1)dH=O({\log }^{3}N)$ seed bits.

The index-list spans select the $t$-th member of $S$ and compute $\mathrm{\mid }S\cap [x]\mathrm{\mid }$ by one bounded skip-list search. Define $g(x)=x-\mathrm{\mid }S\cap [x]\mathrm{\mid }$ for $0\le x\le N$, where $[x]=\{1,\dots ,x\}$. It is nondecreasing and increases by one exactly at an unselected index. Binary search for the least $x$ with $g(x)\ge t+1$ therefore gives the $t$-th element of $[N]\setminus S$ and uses $O(\log N)$ rank searches. Each list search has at most $D$ forward entries per level, and each stable node identifier resolves by evaluating $h(i)$ and scanning at most $C$ slots in its bucket. Here is a finite bit-cost implementation of these operations. For $H$-bit field elements, addition is bitwise XOR. A polynomial-basis multiplication forms the $H^2$ pairwise bit products and reduces their carryless product modulo the fixed degree-$H$ irreducible polynomial using $O(H^2)$ Boolean gates; it has $O(H^2)$ serial depth when evaluated by the direct nested-loop circuit. Horner evaluation of one degree-<$d$ polynomial therefore uses $O(d{H}^2)=O(H^3)$ Boolean gates and depth, since $d=O(H)$. Evaluating $p_{-1}$ computes a bucket address within this cost; computing the height of a newly inserted index evaluates at most $H$ promotion polynomials and costs $O(H^4)$ gates and depth. Compute-copy-uncompute using [F6] makes these deterministic calculations reversible with constant-factor gate overhead; the $O(H^2)$ multiplication scratch can be reused. Each stored record has $w=O({\log }^{2}N+b)$ bits. Scanning a bucket costs at most $Cw$ addressed swaps, while its hash computation uses the field-evaluation circuit above. A lexicographic key comparison on the $O(\log N+b)$ index/value bits uses $O(\log N+b)$ Boolean gates and depth by a sequential bit comparison. A rank traversal visits at most $(H+1)D=O({\log }^{2}N)$ entries; span accumulation adds or compares $O(\log N)$-bit integers, so one rank search has $O({\log }^5(N+M))$ QRAM calls and ordinary gates. Complement unranking consequently has $O({\log }^6(N+M))$ such costs. These bounds establish finite polylogarithmic lookup, selected-index, and complement-unranking procedures whenever the capped searches do not overrun.

The QRAM table has $RC=O(r\log N)$ slots. Each slot stores an index, a $b$-bit value, and $O(H)$ pointers and spans of $O(\log N)$ bits each, hence $O({\log }^{2}N+b)$ bits. The seed, counters, rank registers, arithmetic workspace, and comparator-history scratch add $O(r{\log }^{2}N+{\log }^{3}N)$ bits. Therefore total table and workspace memory is $O(r\log N({\log }^{2}N+b)+r{\log }^{2}N+{\log }^{3}N)=O(r{\log }^3(N+M))$. The finite initial table and both sorted lists can be built by the reversible networks in step 1.2 using $O(r\mathrm{polylog}(N+M))$ gate-time after the $r$ value loads.

To update the stored subset, delete the removed index from the index and value lists, apply one inverse XOR query to erase its value, apply one forward XOR query to load the inserted value, and insert its record into both lists. The predecessor search on each level supplies the crossing edge and its old span. If a list has length $r$ and insertion is at base rank $t$, old keys of rank at least $t$ move up by one. At each level containing the new key $x$, replace the crossing span by the two exact differences $t-\mathrm{rank}(p)$ and $\mathrm{rank}(q)+1-t$, where $p$ and $q$ are its predecessor and successor in the old level list; if $x$ is absent at that level, increment the crossing span by one. For deletion of a key $x$ of base rank $t$, if $x$ is present at a level, replace spans $s(p,x)$ and $s(x,q)$ by $s(p,x)+s(x,q)-1$; if it is absent, decrement the unique crossing span by one. The head has rank $-1$ and a missing successor is treated as a virtual tail of rank equal to the current list length, so the same formulas cover both endpoints. Each updated span is an integer at most $r+1\le N$ and fits in $O(\log N)$ bits. Ripple-carry addition, subtraction, and comparison use $O(\log N)$ Boolean gates and depth per operation; at most $H+1$ predecessor paths of at most $D$ entries and $O(H)$ span writes are needed. Their arithmetic, record reads, and writes therefore have polylogarithmic gate and QRAM costs. Two bounded searches in the value list, at $(v,1)$ and $(v,N+1)$, give the multiplicity of a value $v$; maintain the number of value classes with multiplicity at least two, decrementing when a deletion changes multiplicity two to one and incrementing when an insertion changes one to two. This counter makes the marked check an exact zero test with no value query. Compute its nonzero bit into the fresh check flag by reversible XOR and undo the comparison scratch, leaving the canonical memory and every other existing register fixed; the reversed circuit supplies the inverse check at the same polylogarithmic gate/QRAM cost. The fresh-flag Lüders readout and inverse specified by the finding algorithm then implement its required retained-state instrument, with both check calls and the readout charged separately. Reversing these finite operations restores the canonical table. A controlled memory-bit access uses two addressed swaps with clean scratch and a Fredkin between them, so it has constant-factor QRAM overhead by [F3, F10]. Thus the local update and marked-check subroutines use $\mathrm{polylog}(N+M)$ QRAM time and gates whenever their searches fit the cap.

For fixed $S$ and a bucket $v$, let $X_v$ count its selected indices. The $d$-wise hash family from step 2.1 gives, with $C\le d$, $\mathrm{Pr}(X_v\ge C)\le \mathbb{E}\left(\genfrac{}{}{0px}{}{X_v}{C}\right)=\left(\genfrac{}{}{0px}{}{r}{C}\right)R^{-C}$. Since $\left(\genfrac{}{}{0px}{}{r}{C}\right)\le r^C\mathrm{/}C!$, $R\ge r$, and $C!\ge 2^{C-1}$ (each factor $2,\dots ,C$ is at least $2$), this is at most $2^{1-C}$. With $C=16m$ and $2^m\ge N+2$, $2^{1-C}\le 2(N+2{)}^{-16}$. A union bound over $R\le N$ buckets gives probability at most $2N(N+2{)}^{-16}$.

Put $s=\lfloor d\mathrm{/}2\rfloor =8m$. For either fixed key order and each level $\mathrm{\ell }<H$, condition on the seeds for levels below $\mathrm{\ell }$; this fixes the level-$\mathrm{\ell }$ list and its key order. Among at most $r$ consecutive windows of $s$ nodes, $s$-wise independence makes the chance that the promotion bits are all zero or all one equal to $2^{1-s}$. A union bound over two lists and $H$ levels gives probability at most $4rH{2}^{-s}\le 4rH(N+2{)}^{-8}$. These events control the traversals below level $H$; the initial traversal at level $H$ needs a separate occupancy bound.

Let $X_H$ count nodes of $S$ with height $H$; it is the same count in both key orders. For any $s$ distinct nodes, step 2.1 and independence of the $H$ promotion seeds give probability $2^{-Hs}=q^{-s}$ that all reach level $H$. Thus $\mathrm{Pr}(X_H\ge s)\le \mathbb{E}\left(\genfrac{}{}{0px}{}{X_H}{s}\right)=\left(\genfrac{}{}{0px}{}{r}{s}\right)q^{-s}\le (r\mathrm{/}q{)}^s\mathrm{/}s!\le 2^{1-s}\le 2(N+2{)}^{-8}$, since $s\le d\le r$, $r\le q$, and $s!\ge 2^{s-1}$. Outside this event, the top list has fewer than $s$ nodes, and deleting and inserting one node leaves at most $s$ there. Below the top level, absence of the run events in step 3.3 bounds every run of unpromoted nodes by $s-1$. Deleting a promoted node can merge two such runs, and the subsequent insertion can add at most one unpromoted node, giving at most $2s-1$ consecutive unpromoted nodes. A search descends from the predecessor found at the next level and inspects only such a run and its boundary entries. Hence every search before, during, or after one replacement fits $D=2s+1$ entries at each lower level; the top traversal also fits this cap.

Call a seed bad for $S$ if some bucket has occupancy at least $C$ or a run event of step 3.3 or the top-level event of step 4.1 occurs. Its probability is ${\eta }_N\le 2N(N+2{)}^{-16}+(4rH+2)(N+2{)}^{-8}=O(N^{-7}\log N)$ by steps 3.2, 3.3, and 4.1. Cap every bounded lookup, rank, select, and collision check after the prescribed bucket/level limits: a failed read writes a fixed invalid sentinel to its clean output and leaves the canonical table unchanged; a failed check returns the non-marked bit. For a Johnson replacement, compute all endpoint and search flags before modifying the table and apply the toggle only if both endpoint loads are below $C$ and every search fits; otherwise act as the identity. This update cap is symmetric in its endpoints, so the accepted toggle is an involution and the rejected basis states are fixed. A coherent row access applies the same cap to each coin-labelled replacement branch, retaining the coin label so distinct source/successor blocks remain orthogonal. Read/check caps are reversible XORs into clean outputs. Thus each cap is a finite unitary and agrees with the ideal operation on every good configuration. The initial table is a deterministic isometry; it agrees with the ideal stored representation on good seeds and can differ only on the bad-seed block.

For a fixed subset and neighbor, either endpoint is bad with probability at most $2{\eta }_N$ by the union bound. The retained logical labels make distinct subset/neighbor blocks orthogonal, so on a state whose seed is uniform conditional on each logical history, the squared norm of the bad block for one logical data-access unit is at most $2{\eta }_N$. Since the capped and ideal operations are unitary and agree off that block, their state-vector difference on that prefix is at most $2\sqrt{2{\eta }_N}$. The same estimate covers the initial table encoding, a one-subset check, and the final capped scan. The finding algorithm has only finitely many Lüders tests and outcome-controlled unitary suffixes. By [F17], defer those measurements to outcome-record registers; the ideal search and its recorded branch controls are independent of the hash seed, while the canonical table is a deterministic encoding of the current subset and seed. Hence each ideal prefix keeps the seed uniform conditional on its logical labels and recorded outcomes, as required for the bad-block bound.

Write ${\delta }_{\ast }=N\mathrm{/}[2r(N-r)]$ and ${\epsilon }_{\ast }=r(r-1)\mathrm{/}[N(N-1)]$. For $0<q\le 1$, define $\mathrm{dyad}(q)=2^{-j}$ for the least integer $j\ge 0$ with $2^{-j}\le q$, determined by exact rational comparisons; then $q\mathrm{/}2\le \mathrm{dyad}(q)\le q$. Supply ${\delta }_0=\mathrm{dyad}({\delta }_{\ast })$, ${\epsilon }_0=\mathrm{dyad}({\epsilon }_{\ast })$, and $\rho =1\mathrm{/}2$ to [F11]. Since $r\le N\mathrm{/}2$, ${\delta }_{\ast }\ge 1\mathrm{/}(2r)$; since $r-1\ge r\mathrm{/}2$ and $N(N-1)\le N^2$, ${\epsilon }_{\ast }\ge r^2\mathrm{/}(2N^2)$. Thus ${\delta }_0\ge 1\mathrm{/}(4r)$ and ${\epsilon }_0\ge r^2\mathrm{/}(4N^2)$. Counting each capped walk update and mark check as one logical operation, [F11] gives $O({\epsilon }_0^{-1\mathrm{/}2}({\delta }_0^{-1\mathrm{/}2}+1))=O(N\mathrm{/}\sqrt{r})$ such operations. The complete wrapper makes only $O(1)$ fresh stationary preparations at this fixed failure target. Each uses $O(r)$ value queries by [F1], so all setups together use $O(r)$ queries; table encoding and final reading occur only $O(1)$ times. Thus even counting every setup query, $T=O(r+N\mathrm{/}\sqrt{r})=O(N^{2\mathrm{/}3})$. A hybrid over these $T$ data-dependent operations gives state-vector error at most $2T\sqrt{2{\eta }_N}$. The final success probability changes by at most twice this error: [F13] writes it as $\mathrm{\parallel }\mathrm{\Pi }\psi {\mathrm{\parallel }}^2$ for the success projection, [F16] bounds $\mathrm{\mid }\mathrm{\parallel }\mathrm{\Pi }\psi \mathrm{\parallel }-\mathrm{\parallel }\mathrm{\Pi }\varphi \mathrm{\parallel }\mathrm{\mid }$ by $\mathrm{\parallel }\psi -\varphi \mathrm{\parallel }$, and [F15] bounds the difference of squares. Since ${\eta }_N=O(N^{-7}\log N)$, this probability error tends to zero; choose fixed $N_0$ large enough that it is at most $1\mathrm{/}40$ for all $N\ge N_0$. The fixed target $\rho =1\mathrm{/}2$ includes only a constant number of fresh outer trials in the complete wrapper, so all its calls are included in $T$. By [F11], the ideal wrapper succeeds with probability at least $1\mathrm{/}2$; its capped-storage implementation therefore succeeds with probability at least $19\mathrm{/}40$. Verify any reported pair directly with two value queries; this preserves one-sided error and adds only $O(1)$ queries.

On the walk branch $N\ge N_0$, the actual gap is ${\delta }_{\ast }$ by [F1] and the marked mass is at least ${\epsilon }_{\ast }$ by [F1]. Use the dyadic bounds fixed in step 7.1; they satisfy ${\epsilon }_0<1\mathrm{/}2$. By [F1], the coherent Johnson row preparation has stationary edge setup at most $r+2$, controlled row reflection at most $4$, and controlled $W,W^{\ast }$ access at most $8$ value queries; thus the complete fixed-target wrapper in [F11], with all its fresh setups counted as in step 7.1, gives $O\text{\hspace{0.17em}⁣}(r+{\epsilon }_0^{-1\mathrm{/}2}({\delta }_0^{-1\mathrm{/}2}+1))=O(r+N\mathrm{/}\sqrt{r})=O(N^{2\mathrm{/}3})$ value queries. Moreover ${\delta }_0\ge 1\mathrm{/}(4r)\ge 1\mathrm{/}(2N)$ and ${\epsilon }_0\ge r^2\mathrm{/}(4N^2)\ge 1\mathrm{/}{N}^2$, so the phase-register lengths in the reversible-finding algorithm are $O(\log N)$. Each phase-estimation run therefore uses $O({\log }^{2}N)$ phase-register and inverse-QFT gates by [F14]; the number of such runs is at most the number of controlled-walk calls because each run uses at least one. Reversible arithmetic and local checks add $\mathrm{polylog}(N+M)$ gate-time per charged update. Each fresh stationary preparation charges $G_{\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{e}\mathrm{t}}$ for its uniform subset, $O(r\mathrm{polylog}(N+M))$ for value loading and table construction, and $O(G_{\mathrm{r}\mathrm{o}\mathrm{w}})$ for its edge-row preparation. There are only $O(1)$ fresh preparations by step 7.1, so their total cost is $O(G_{\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{s}\mathrm{e}\mathrm{t}}+r\mathrm{polylog}(N+M)+G_{\mathrm{r}\mathrm{o}\mathrm{w}})$. The final stored-value scan costs $O(r\mathrm{polylog}(N+M))$. Charging each of the $O(N^{2\mathrm{/}3})$ walk-access units at $G_{\mathrm{r}\mathrm{o}\mathrm{w}}$ gives the stated formula; direct verification of a reported pair costs at most two further value queries and polylogarithmic gate-time. For $4\le N<N_0$, direct pair comparison uses $N$ value queries and $O(N^2\log (M+1))$ gates; since $N_0$ is a fixed constant, this finite branch is absorbed by the asymptotic bounds. The phase-gate bound is in the ideal continuous-rotation submodel; fixed-alphabet synthesis and a polylogarithmic bound for $G_{\mathrm{r}\mathrm{o}\mathrm{w}}$ are not proved here.

For the optional Boolean value circuit, [F5] counts every non-input node, including unused constants, in $S$, so [F6] gives the serial bound $6S+4E+m$. The parallel construction in [F7] instead uses at most $6S$ evaluation/reversal gates, $4E$ input fanout/unfanout gates across the two passes, $2m$ output fanout/unfanout gates, and $m$ output CNOTs, totaling at most $6S+4E+3m$. Its stated depth follows by substituting $L=\lceil {\log }_2(F+1)\rceil$ and $L_m=\lceil {\log }_2(m+1)\rceil$ in [F7]. These are separate implementations of the same XOR query; their occurrence and written-depth bounds do not assert minimum depth or bound the other walk gates.