Walk over subsets that remember their queries

What it fills

• Walk a graph to the vertex you want

  When candidates sit on a graph and the work done at one vertex is still worth something at its neighbour, walk the graph instead of sampling it — and pay per move rather than per candidate.

When it applies

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".

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

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

Cost, as the source states it

$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.

Implementations

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

  • Quantum walk algorithm for element distinctness

  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.

  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$".

  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.

  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.

  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.

What it needs

Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.

Other ways to fill the same slot

Different approaches

• Walk the backtracking tree itself

  Take the tree a classical backtracking algorithm would have explored — never built, never known in advance — and walk it from the root. Phase estimation on the walk operator says whether a solution is down there at all; running that test on subtree after subtree turns the answer into the solution.

In the Atlas

• 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.

Sources

• Quantum walk algorithm for element distinctness↗Andris Ambainis · 2003theory yes · simulation ? · hardware no