Quantum-Walk Search and Element Distinctness — Examples

The parity oracle is exactly one application of the supplied $O_{f_m}$, so its query count is one by [F1]. In an ordinary circuit, form the interaction graph whose vertices are all circuit wires and whose edges join the two wires acted on by each two-wire gate occurrence. If the target's connected component omitted an address bit, then no gate couples that bit to the target or to any intermediary on its component; the circuit factors across this separation, making the target output independent of the omitted bit. This contradicts parity's dependence on each input bit: fixing the other bits and changing the omitted bit changes the target. Hence the graph contains a connected subgraph joining the target and all $m$ address wires. Any connected graph containing these $m+1$ distinct terminals has at least $m$ edges, even if it also contains ancilla vertices; each edge comes from a gate occurrence.

For the explicit upper-bound constructions, choose an ordinary gate alphabet containing CNOT, with basis action $\mathrm{\mid }a,b⟩\mapsto \mathrm{\mid }a,b\oplus a⟩$; this is an additional model choice, not a consequence of [F2]. Applying the $m$ CNOT gates from each address bit to the target computes parity into that target and gives an exact $m$-gate implementation. In QRAM, store $z_i=f_m(i)$ and use one addressed swap to move $z_i$ to a clean scratch bit, copy it by CNOT into the oracle target, and use a second addressed swap to restore the memory and clear the scratch. This is a constant number of RAM calls by [F3], but it still requires the table to have been constructed and maintained. The online gate models therefore count one oracle call versus at least $m$ ordinary two-wire gates for this function, with RAM construction cost recorded separately.

For $N=5,r=2$, the denominator in [F1] is $2r(N-r)=12$. At $j=0,1,2$, the eigenvalues are $1$, $1-5\mathrm{/}12=7\mathrm{/}12$, and $1-8\mathrm{/}12=1\mathrm{/}3$. Their multiplicities are $1$, $\left(\genfrac{}{}{0px}{}{5}{1}\right)-\left(\genfrac{}{}{0px}{}{5}{0}\right)=4$, and $\left(\genfrac{}{}{0px}{}{5}{2}\right)-\left(\genfrac{}{}{0px}{}{5}{1}\right)=5$, totaling $10=\left(\genfrac{}{}{0px}{}{5}{2}\right)$. Thus the nonconstant top eigenvalue is $7\mathrm{/}12$ and the gap is $5\mathrm{/}12$. An independent finite check enumerates the ten $2$-subsets lexicographically and forms the integer matrix $B_{ST}=12P(S,T)$: its diagonal is $6$, and its off-diagonal entry is $1$ exactly when $\mathrm{\mid }S\cap T\mathrm{\mid }=1$. Exact determinant expansion gives $\det (xI-B)=(x-12)(x-7{)}^4(x-4{)}^5$, confirming the scaled spectrum. A fixed colliding pair lies in $\left(\genfrac{}{}{0px}{}{3}{0}\right)=1$ of the $10$ subsets, so its marked fraction is $1\mathrm{/}10$.

For $N=6,r=3$, the denominator is $18$. Formula [F1] gives eigenvalues $1,2\mathrm{/}3,4\mathrm{/}9,1\mathrm{/}3$ for $j=0,1,2,3$. Their multiplicities are $1,5,9,5$, totaling $20=\left(\genfrac{}{}{0px}{}{6}{3}\right)$. The independent exact check enumerates the $20$ triples and forms $B_{ST}=18P(S,T)$ with diagonal $9$ and off-diagonal $1$ exactly when $\mathrm{\mid }S\cap T\mathrm{\mid }=2$; fraction-free determinant expansion gives $\det (xI-B)=(x-18)(x-12{)}^5(x-8{)}^9(x-6{)}^5$, confirming those eigenvalues and multiplicities. The gap is $1-2\mathrm{/}3=1\mathrm{/}3$. A fixed pair belongs to $\left(\genfrac{}{}{0px}{}{4}{1}\right)=4$ of the $20$ subsets, hence has marked fraction $1\mathrm{/}5$.

Under the stated assumption that the only collision pairs are the two named disjoint pairs, each pair is contained in four $3$-subsets, and no $3$-subset contains both pairs because their union has four elements. The two marked families are therefore disjoint and their union has $4+4=8$ subsets, a fraction $8\mathrm{/}20=2\mathrm{/}5$. The value exceeds the one-pair lower bound $1\mathrm{/}5$, as required by the “at least” in [F2]. Without the exclusivity assumptions, the counted families still give lower bounds for the marked fraction, but extra collisions can increase it.

For $N=8,r=4$, the state space has $\left(\genfrac{}{}{0px}{}{8}{4}\right)=70$ subsets. Exactly $\left(\genfrac{}{}{0px}{}{6}{2}\right)=15$ contain the unique colliding pair, so $\epsilon =15\mathrm{/}70=3\mathrm{/}14$, equal to $r(r-1)\mathrm{/}[N(N-1)]=12\mathrm{/}56$. The stationary mass is positive, and [F1] gives four setup value queries, two value queries per update, and no extra value query for the stored-value check.

More generally, for $r=\mathrm{\Theta }(N^{2\mathrm{/}3})$ with $r\le N\mathrm{/}2$, [F2] charges at most two fresh setups, with leading term $2r=\mathrm{\Theta }(N^{2\mathrm{/}3})$ and update/search term $N\mathrm{/}\sqrt{r}=\mathrm{\Theta }(N^{2\mathrm{/}3})$. Thus both terms are of the same asymptotic order and the theorem's total is $O(N^{2\mathrm{/}3})$. For $N=8$, the clamp in the theorem selects $r=4$; its expression is $8+O(8\mathrm{/}2)=8+O(4)$, consistent with this scaling.