The vertex has to carry its queried values, and the same subset must always be stored the same way regardless of how it was reached. Ambainis calls this the uniqueness problem and states the consequence of getting it wrong: "in the original quantum algorithm, we might have $\alpha|S\rangle$ interfering with $-\alpha|S\rangle$, resulting in $0$ amplitude for $|S\rangle$. If $\alpha|S\rangle - \alpha|S\rangle$ becomes $\alpha|S^{1}\rangle - \alpha|S^{2}\rangle$, there is no interference between $|S^{1}\rangle$ and $|S^{2}\rangle$" — so a data structure that remembers insertion order breaks the algorithm rather than slowing it. The published analysis of the walk assumes at most one solution — "a promise that there is at most one set of $k$ indices" — and the general case is reached by a classical wrapper that reruns the walk on random subsets, not by a different walk. The running-time claim, as opposed to the query claim, is conditional: it needs a circuit model "augmented with gates for random access to a quantum memory", without which "simple data structure operations (for example, removing $y$ from $S$) which require $O(\log N)$ time classically would require $\Omega(r)$ time quantumly".

A rule naming the neighbours of any vertex, a rule saying whether a vertex is marked, somewhere to start — one named vertex, or a distribution over them — and the size bounds the schedule is computed from: the number of vertices, the depth, the maximum degree, or the size of the subsets a vertex stands for. Which of those a method needs is a property of the walk, not of the slot.

1. Search graph with a marked set → A marked item, with its query billadd an element, query it, diffuse, drop one

   The graph has "$\binom{N}{r} + \binom{N}{r+1}$ vertices. The vertices $v_{S}$ correspond to sets $S \subseteq [N]$ of size $r$ and $r + 1$. Two vertices $v_{S}$ and $v_{T}$ are connected by an edge if $T = S \cup \{i\}$ for some $i \in [N]$. A vertex is marked if $S$ contains $i, j, x_{i} = x_{j}$." That marking condition is section 3.1's element-distinctness specialisation, stated there under "let $r = N^{2/3}$"; the general one, which Algorithm 2 uses and which the phase flip below carries, asks for $k$ distinct indices with equal values. The walk runs on two spaces: $\mathcal{H}$ with basis $|S, x, y\rangle$ for $|S| = r$, $x \in [M]^{r}$, $y \in [N] \setminus S$, and $\mathcal{H}'$ with $|S| = r + 1$ and $y \in S$. One step is six operations. Steps 1 and 4 are Grover diffusions on the $y$ register — $|S\rangle|y\rangle \mapsto |S\rangle\left(\left(-1 + \frac{2}{N-r}\right)|y\rangle + \frac{2}{N-r}\sum_{y' \notin S,\, y' \neq y}|y'\rangle\right)$ going up, and the same form with $N - r$ replaced by $r + 1$ and the sum taken over $y' \in S$ coming back down. Between them, step 2 adds $y$ to $S$, step 3 queries $x_{y}$ and inserts it, and steps 5 and 6 use the query a second time to erase the value at the new $y$ before removing it — so the move up and the move back each cost one query. assumption: "$x$ will always be equal to $(x_{i_{1}}, \ldots, x_{i_{r}})$ where $i_{1}, \ldots, i_{r}$ are elements of $S$ in increasing order" — the stored values must be in a canonical order, or the same subset reached two ways occupies two basis states and the interference the algorithm is built on does not happen. Outside the walk sits the phase flip $|S\rangle|y\rangle|x\rangle \to -|S\rangle|y\rangle|x\rangle$ on any $S$ holding $k$ indices with equal values, which costs nothing because those values are already stored. The schedule is $t_{1} = O((N/r)^{k/2})$ outer repetitions of one phase flip followed by $t_{2} = O(\sqrt{r})$ walk steps. assumption: the outer count comes from the overlap $\alpha = \Omega(r^{k/2}/N^{k/2})$ between the walk's starting state and the marked subspace, which is what a promise of at most one solution buys; a domain with many solutions changes $\alpha$ and the paper reaches it through a classical wrapper instead. The data structure that holds $S$ is where the running time is won or lost, and the paper's hash-table-and-skip-list version is not exact: a bucket can overflow, the branch on which it does is bounded per step at $\|\psi_{t}^{bad}\| = O(1/N^{1.5})$, and the distribution a measurement of the real algorithm returns is shown to differ from the ideal one by $O(1/N^{1/2})$ in variational distance.

   assumption

A marked vertex, with the evidence it is marked already in hand from the work stored on it — or the report that the graph holds none, at a stated failure probability.

given  oracle access to x_1 ... x_N with values in [M]                (Sec. 3.1)
       k, the number of equal items to be found
       r, the subset size; r = N^(2/3) for k = 2

# a vertex is a subset S of the inputs together with the values already
# queried for it, so a step costs one query and not r of them

generate the uniform superposition over pairs (S, y) with |S| = r, y not in S
query all x_i for i in S                                     (Sec. 3.2, Alg. 2)

# these r queries are the whole cost of the initial state

repeat t1 = O((N/r)^(k/2)) times:
    flip the phase of every S that already contains k indices with equal values

    # this check costs no queries: the values for S are already stored

    perform t2 = O(sqrt(r)) steps of the walk, each step being      (Alg. 1)
        diffuse over y among the elements not in S
        move to S + {y}, querying x_y and inserting it
        diffuse over y among the elements of S + {y}
        erase the value at the new y by querying x_y again, and drop y

measure, and check whether the measured S contains k equal values
return that S -- its stored values are the witness, or there is none

# the same subset must always be stored the same way, however it was reached.
# Two spellings of one subset do not interfere, and the algorithm is built out
# of that interference

# the analysis above assumes at most one solution. The general case runs this
# on random subsets of the input, classically, and is not a different walk

# do not read the query count as a running time. That needs a model with
# random access to quantum memory, and the paper says so

$O(N^{2/3})$ queries for element distinctness on $N$ items and $O(N^{k/(k+1)})$ for finding $k$ equal items, which the abstract sets against the previous $O(N^{3/4})$ quantum algorithm of Buhrman et al. and against the $\Omega(N^{2/3})$ lower bound the paper attributes to Aaronson and Shi. The bill has two terms and not three: "$r$ for creating the initial state and $O((N/r)^{k/2}\sqrt{r})$ for the rest of the algorithm", so the total is $O(\max(r, N^{k/2}/r^{(k-1)/2}))$ and $r = N^{2/3}$ is where the two meet. Under a memory restriction to $r$ stored numbers the paper reports $O(N/\sqrt{r})$ queries against a classical $O(N^{2}/r)$. Time is a separate and weaker claim: $O(N^{k/(k+1)}\log^{c}(N + M))$ steps, and only in a model with random-access gates. The constant is not uniform in $k$ — "the big-O constant depends on $k$", with $O(k^{2}N^{k/(k+1)})$ stated for non-constant $k$ and its proof omitted from that version.

• A two-qubit circuit for the $N=4$, $k=2$ case, run on IBM Quantum Experience

  • Quantum walk algorithm for element distinctness

    Andris Ambainis · 2003

  About

  A Duke University ECE523 (Quantum Information Science, taught by Jungsang Kim) final project by Yuqi Yun and Ming-Tso Wei, posted as a public GitHub repository rather than a paper (README: "Duke University ECE523 Quantum Information Science instructed by Prof. Jungsang Kim at Duke University in Spring 2017. Final Project authored by Yuqi Yun and Ming-Tso Wei"). The report's own framing sentence names the wrong author for its own reference [2] — "we are focusing on the quantum walk algorithm for element distinctness proposed by Aaronson [2]" — but reference [2] in the same document's bibliography is Ambainis's paper, not a paper by Aaronson; the construction the report goes on to build, the $\binom{N}{r}+\binom{N}{r+1}$-vertex graph with the phase flip and two-step diffusion, is this method's own.

  Methods

  The report exploits the block-diagonal structure of the walk's operators to collapse the $N=4$, $k=2$ instance to two qubits. It first groups the twelve $|S,y\rangle$ basis states (six size-2 sets $S$, each with two choices of $y \notin S$) into five symmetry classes $|\varphi_{j,l}\rangle$ defined by "$|S \cap \{B,C\}| = j$ and $|y \cap \{B,C\}| = l$", which turns the phase flip and both diffusion steps into explicit $5\times5$ (in general $(2k+1)\times(2k+1)$) matrices $U$, $U_1$, $U_2$ acting on that basis. It then reduces further: because the instance's first basis component $|\varphi_{0,0}\rangle$ starts at amplitude zero and is never populated, "the unitary matrices can be reduced to $4\times4$ matrices and represented by only two qubits." Built as circuits, "the first unitary transformation $U$, which does the conditional phase flip, is just a controlled-Z gate"; "the next unitary transformation $U_1$, the first step of quantum walk, is just a SWAP gate"; and $U_2$, being block-diagonal, becomes "two controlled U gates", each decomposed into CNOTs and single-qubit gates via the $U = e^{i\alpha}AXBXC$ construction the report cites to Nielsen and Chuang. The full walk is assembled as the matrix product $((U_2U_1)^{t_2}U)^{t_1}$, which for this instance "is just $U_2 U_1 U U_2 U_1 U$".

  Data

  A synthetic $N=4$ instance with a single planted collision, $x = (x_A, x_B, x_C, x_B)$ with $x_B = x_C$, giving $r=2$: six size-2 subsets $S \subseteq \{A,B,C,D\}$ and four size-3 subsets $T$, ten vertices in all, with the marked vertex being the subset $\{B,C\}$. No external dataset; the report also describes a Box-hosted Mathematica script for simulating arbitrary $N$ at $k=2$, with example runs quoted up to $N = 234857$, and the repository separately checks in a notebook, `Quantum-Walk-n (2).nb`, whose code is written generically in $n$ and $k$ (using `Binomial`, `IntegerPart`, and `MatrixPower`, including $r = \mathrm{IntegerPart}(n^{2/3})$) matching that description, though its saved state has $n$ evaluated at $4$ rather than one of the larger examples the report quotes.

  Code

  Repository `mingweii/Element-distinctness-by-quantum-walk-algorithm-IBM-Q` on GitHub. The circuit is a Qiskit notebook, `N=4, k=2 element distinctness by quantum walk algorithm.ipynb`, importing `from qiskit import QuantumCircuit, execute, Aer, IBMQ` and simulating on `Aer.get_backend('qasm_simulator')`. The same circuits are checked in as raw OpenQASM 2.0: `U.qasm` is a 2-qubit circuit (`qreg q[2]`), and the composed walk `U2U1UU2U1U.qasm` is a 5-qubit, 96-line circuit (`qreg q[5]`) — both confirmed by reading the files directly.

  Results

  Table 1 of the report compares the probability of measuring the marked basis state $|\varphi_{2,0}\rangle$: a Mathematica evaluation of the exact matrices gives $0.59465$; the "IBM Simulator" gives $0.560$ at 100 shots and $0.666$ at 8192 shots; and the "IBM real processor" gives $0.500$ at 1024 shots and $0.493$ at 8192 shots. The report's reading: "Both the IBM simulators and real execution results agree well with the numerical results we obtained." No specific processor model is named beyond "IBM real processor", nor any simulator backend beyond "IBM Simulator" / "IBM quantum simulator". The report scopes the result in two separate places: Section 3 attributes this particular circuit's two-qubit size to the $N=4$ instance's own $|\varphi_{0,0}\rangle$ component starting and staying at zero amplitude, which lets the $5\times5$ walk matrices reduce to $4\times4$; Section 4 separately states, more generally, that element distinctness at $k=2$ never needs more than three qubits, while $k$-distinctness would need $(2k+1)\times(2k+1)$ matrices and "would significantly increase the complexity of the problem" — a cost that, in this circuit's gate budget, also grows with $N$ through $t_1 = (N/r)^{k/2}$ against the roughly hundred-gate ceiling the report says both the simulator and the real device were subject to.

• Element distinctness by quantum walk · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  Given oracle access to N items carrying no promise about the underlying function, find two items that are equal, or establish that all N are distinct.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

• Subset finding by quantum walk · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  In L-subset finding, a black box f maps a domain D of size N into a range R, and a property P picks out some L-element subsets by their arguments and values. The task is to find an L-subset {x₁, …, x_L} of D whose pairs ((x₁, f(x₁)), …, (x_L, f(x_L))) satisfy P, or to reject if none exists, using as few queries as possible. Unstructured search is the case L = 1 and element distinctness the case L = 2.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

• Subset-sum by quantum walk over representations · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  Given integers x₁, x₂, …, xₙ and s, decide whether some subset I of {1, 2, …, n} satisfies the sum of xᵢ over I equal to s. The authors take as the typical hard case that the xᵢ are independent uniform random integers in {0, 1, …, 2ⁿ}. Subset-sum was one of the first problems shown NP-complete, so the question the paper asks is not whether it can be solved in polynomial time but how far below the 2ⁿ cost of searching every subset an exponential-time algorithm can get.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · problem statement and speedup class checked against the Quantum Algorithm Zoo entry · primary reference checked against its arXiv abs page

• Element distinctness by quantum walk

  Given oracle access to N items carrying no promise about the underlying function, find two items that are equal, or establish that all N are distinct.

• Subset finding by quantum walk

  In L-subset finding, a black box f maps a domain D of size N into a range R, and a property P picks out some L-element subsets by their arguments and values. The task is to find an L-subset {x₁, …, x_L} of D whose pairs ((x₁, f(x₁)), …, (x_L, f(x_L))) satisfy P, or to reject if none exists, using as few queries as possible. Unstructured search is the case L = 1 and element distinctness the case L = 2.

• Subset-sum by quantum walk over representations

  Given integers x₁, x₂, …, xₙ and s, decide whether some subset I of {1, 2, …, n} satisfies the sum of xᵢ over I equal to s. The authors take as the typical hard case that the xᵢ are independent uniform random integers in {0, 1, …, 2ⁿ}. Subset-sum was one of the first problems shown NP-complete, so the question the paper asks is not whether it can be solved in polynomial time but how far below the 2ⁿ cost of searching every subset an exponential-time algorithm can get.