Element Distinctness and Walks

In short

You are handed a box with N slots. Slot i holds a number x_i \in \{1, 2, \ldots, M\}. Each time you want to read a slot, it costs you one query. Are all N numbers distinct, or is there at least one pair of slots i \ne j with x_i = x_j?

Classically, you cannot do better than \Theta(N) queries: any deterministic or randomised algorithm missing more than a constant fraction of the slots could in the worst case miss the colliding pair. Sort all N items and compare adjacent pairs — that uses N queries and O(N \log N) comparisons — and you cannot do the query count better.

Grover's algorithm does not help directly. Grover searches for a single marked item; element distinctness asks about pairs of items, and the marked set — the pairs that collide — is of size \ge 1 out of \binom{N}{2} \approx N^2/2 total pairs, giving \sqrt{N^2} = N queries from naive Grover-on-pairs. No improvement.

Andris Ambainis's 2003 algorithm solves element distinctness in \Theta(N^{2/3}) queries using a quantum walk on the Johnson graph. The vertices of the Johnson graph J(N, r) are r-element subsets of \{1, \ldots, N\}. The walk moves between vertices by swapping one element in and one element out. Marked vertices are subsets that happen to contain a colliding pair. Quantum walking this graph finds a marked vertex in O(N^{2/3}) queries when r is chosen to be N^{2/3}. Aaronson-Shi 2004 proved this is tight — no quantum algorithm can do better.

Element distinctness is the landmark result that established quantum walks as a general algorithmic tool. It broke the psychological ceiling that "Grover is the best quantum does at search" and kicked off a decade of walk-based algorithm design: triangle finding, matrix product verification, and more.

Play this game. An invigilator sits at the front of a JEE classroom with a stack of N = 1{,}000 index cards. Each card has one name written on it. The invigilator claims that all thousand names are different. You are allowed to ask "what is on card number i?" and receive an answer — but every question costs you one second. How many questions must you ask to be confident the invigilator is right (all distinct) or wrong (there is a repeat)?

Classically, you are stuck. Suppose the invigilator has arranged the cards so that exactly one pair is repeated — cards 483 and 712 both say "Anil." If you ask about 999 of the cards but miss exactly one of \{483, 712\}, you see no repeats and cannot distinguish this case from "all distinct." In the worst case you need to ask about every card but one and still might miss it. The formal statement: any deterministic or randomised algorithm needs \Omega(N) queries.

Now Grover. Grover's algorithm can search N items for a single marked item in O(\sqrt N) queries. Can you use it to find a collision? One natural try: check each pair of items — there are \binom{N}{2} \approx N^2 / 2 pairs, of which at least one is a collision (in the collision case). Grover over N^2 items for one marked item takes O(\sqrt{N^2}) = O(N) queries. No improvement over classical. Grover-on-pairs is not enough.

This is where quantum walks change the game. Andris Ambainis, in a 2003 paper, showed that a discrete quantum walk on a carefully chosen graph solves element distinctness in O(N^{2/3}) queries. The graph is the Johnson graph J(N, r), and the walk is a Szegedy-style walk that exploits the structure of the problem. Aaronson and Shi proved in 2004 that N^{2/3} is the best possible — no quantum algorithm can solve element distinctness in fewer queries, up to constants.

This chapter walks you through Ambainis's algorithm, shows why r = N^{2/3} is the sweet spot, and maps out the family of problems the same framework attacks.

Why Grover-on-pairs fails

Before walks, make sure you see why the naive approach misses the speedup.

Consider N items with at most one collision. Define the search space to be pairs of indices \{(i, j) : 1 \le i < j \le N\}. Declare a pair to be "marked" if x_i = x_j. In the collision case there is at least one marked pair; in the distinct case there are zero.

Apply Grover over this space of size \binom{N}{2} \approx N^2/2. Each oracle query to "is this pair marked?" costs two classical queries (look up x_i and x_j). The number of Grover iterations is O(\sqrt{N^2/2}) = O(N). Total queries: O(N). No speedup.

You might try amplitude amplification on top of a better-chosen preparation unitary. It does not help: whatever preparation you use, the good-amplitude is 1/\sqrt{N^2/2} = \sqrt 2 / N for a single marked pair, and amplification needs \Theta(N) steps to concentrate on it.

The lesson: you need a search space smaller than N^2. You need to find a collision without having to enumerate all pairs. Walks let you do this.

The Ambainis algorithm — the headline

The idea in one sentence. Carry a set R \subseteq \{1, \ldots, N\} of size r. Walk on the graph whose vertices are the r-subsets and whose edges are "swap one element." At each vertex, you know x_i for every i \in R. A vertex is marked if R contains a colliding pair.

The walk is a discrete quantum walk on the Johnson graph J(N, r), whose vertex set is all \binom{N}{r} size-r subsets of \{1, \ldots, N\}, with edges between subsets differing in exactly one element. The walk is a Szegedy walk derived from the classical random walk on J(N, r).

Three costs matter, in the MNRS framework (you met it in Discrete Quantum Walks):

Setup S: prepare a uniform superposition over all r-subsets, each dressed with the stored function values (x_i : i \in R). Cost: r queries.
Update U: move from one subset to a neighbouring subset by swapping one element. Cost: 1 query (look up the new element, forget the old).
Check C: test whether the current subset contains a colliding pair. Cost: 0 queries (the function values for all r indices are already in the register; just check pairwise).

And the walk parameters:

Spectral gap \Delta of the Johnson walk: \Delta = \Theta(1/r).
Fraction of marked vertices \varepsilon: if there is one colliding pair (i^*, j^*) in the full set \{1, \ldots, N\}, the fraction of r-subsets containing both i^* and j^* is \binom{N-2}{r-2}/\binom{N}{r} \approx r^2/N^2. So \varepsilon = \Theta(r^2/N^2).

Plug into the MNRS complexity:

S + \frac{1}{\sqrt \varepsilon}\left( \frac{1}{\sqrt \Delta} U + C \right) = r + \frac{N}{r}\left( \sqrt r \cdot 1 + 0 \right) = r + \frac{N}{\sqrt r}.

Minimise over r. Setting r = N/\sqrt r gives r^{3/2} = N, so r = N^{2/3}. The total query count is

\mathbf{r + \frac{N}{\sqrt r} = N^{2/3} + N \cdot N^{-1/3} = 2 N^{2/3}.}

So element distinctness is solved in O(N^{2/3}) queries.

Left: the Johnson graph $J(6, 2)$ (a nine-vertex subgraph shown for clarity) — vertices are 2-subsets of $\{1, \ldots, 6\}$, edges are single-element swaps. If the underlying function has $x_2 = x_5$, then exactly the subsets containing both 2 and 5 are marked. Right: the two components of Ambainis's query cost, $r$ (setup, increasing in $r$) and $N/\sqrt r$ (walk, decreasing in $r$). Their sum is minimised at $r = N^{2/3}$, giving the $O(N^{2/3})$ total query complexity.

Three orders of magnitude less work. For N = 10^6 items, classical is \sim 10^6 queries; quantum-walk is \sim 10^4 queries. The gap widens with N.

Why r = N^{2/3} is the sweet spot: the setup cost grows linearly with r (you need r queries to populate the register with function values). The walk cost shrinks with r like N/\sqrt r (larger r means a larger fraction of subsets contain the collision, so fewer walk steps are needed, but the walk's spectral gap also shrinks as 1/r, partially undoing the win). The two costs balance when r = N/\sqrt r, i.e. r = N^{2/3}. Too small an r: the walk spends all its time looking at subsets that do not contain the collision. Too large: the setup dominates. The N^{2/3} balance is the core structural insight of Ambainis's 2003 paper.

What the walk actually does — more detail

Zoom in on how the algorithm uses quantum walks.

The register. The main register stores a subset R \subseteq \{1, \ldots, N\} of size r, together with the function values (x_i : i \in R). A basis state is |R\rangle|x_R\rangle where |x_R\rangle is a compact encoding of the stored values. The total register size is O(r \log M + r \log N) qubits.

Setup. Prepare the uniform superposition over all \binom{N}{r} subsets:

|\Psi_0\rangle = \frac{1}{\sqrt{\binom{N}{r}}} \sum_R |R\rangle|x_R\rangle.

Building this requires r oracle queries — one for each element of each R, performed in superposition. The specifics use a sequence of controlled oracle calls; the total query cost is r.

Walk step. One step of the Szegedy walk on J(N, r): pick an element i \in R and an element j \notin R uniformly at random (quantum coin), swap them to move to R' = R \setminus \{i\} \cup \{j\}. The quantum walk's step operator does this coherently via the Szegedy construction. Each walk step uses exactly one oracle query — to read x_j when adding it to the register. The old value x_i is already there and does not cost a fresh query to forget.

Marked-vertex check. After the walk, check whether the current subset contains a colliding pair. This is done by examining the stored (x_i : i \in R) without any further oracle queries — just scan the r stored values for duplicates. Cost: 0 queries.

Amplitude amplification. The walk, combined with phase estimation, distinguishes marked from unmarked subsets. Amplitude amplification boosts the probability of landing on a marked subset. The total number of walk steps is O(\tfrac{1}{\sqrt \varepsilon} \cdot \tfrac{1}{\sqrt \Delta}) = O(\tfrac{N}{r} \cdot \sqrt r) = O(N/\sqrt r). Multiplied by 1 query per walk step, that is O(N/\sqrt r) oracle queries in the walk phase.

Total: r + N/\sqrt r, minimised at r = N^{2/3}, giving O(N^{2/3}).

The Aaronson-Shi lower bound — this is tight

Ambainis's O(N^{2/3}) is not just a clever upper bound. In 2004, Scott Aaronson and Yaoyun Shi proved a matching lower bound: any quantum algorithm solving element distinctness requires \Omega(N^{2/3}) queries.

Their proof uses the polynomial method for quantum query lower bounds — a technique that shows any quantum algorithm making T queries produces an acceptance probability that is a polynomial of degree \le 2T in the input bits. To distinguish "all distinct" from "one collision," this polynomial must take substantially different values on the two classes of inputs. A combinatorial argument — bounds on symmetric polynomials on the Johnson scheme — forces the degree to be \Omega(N^{2/3}), giving the matching lower bound.

You will see the polynomial method in more depth in Quantum Query Lower Bounds. The point here is: element distinctness is a tight problem. Ambainis's algorithm matches the lower bound up to constants. You cannot do better, on this problem, with any cleverer quantum algorithm.

The Indian connection — Ashwin Nayak, again

Element distinctness and its sibling results are centrally a product of research in the MNRS lineage — the framework named for Magniez, Nayak, Roland, and Santha, where Nayak is Indian-origin (IIT Kanpur undergraduate). MNRS 2007 subsumes element distinctness as a special case; the generalised MNRS complexity reduces to Ambainis's N^{2/3} when instantiated on the Johnson graph with the element-distinctness marking rule.

The polynomial-method lower bound for element distinctness, Aaronson-Shi 2004, uses techniques building on earlier work by Ramamohan Paturi (Indian-origin, UCSD) and others on symmetric polynomials. Indian students studying quantum query complexity will encounter all three names — Aaronson, Shi, Ambainis — in every quantum-algorithms curriculum worldwide.

The Institute of Mathematical Sciences (IMSc) Chennai, TIFR, and IIT Kanpur actively teach element distinctness as the canonical example of a walk-based speedup beyond Grover. It is standard material in advanced quantum-algorithms electives at Indian institutions.

Example 1: Element distinctness on $N = 4$ by hand

Take a small instance. Function f : \{1, 2, 3, 4\} \to \{A, B, C, D\} with values (x_1, x_2, x_3, x_4) = (A, B, C, B). So x_2 = x_4 = B — there is a collision. Classically you might need up to 4 queries to notice. Walk through Ambainis on this small instance.

Step 1: choose r. With N = 4 tiny, set r = 2 for illustration. Subsets of size 2: there are \binom{4}{2} = 6 of them — \{1,2\}, \{1,3\}, \{1,4\}, \{2,3\}, \{2,4\}, \{3,4\}.

Step 2: marked vertices. Subsets containing both colliding elements 2 and 4: only \{2, 4\}. So 1 marked out of 6, giving \varepsilon = 1/6.

Step 3: setup. Prepare the uniform superposition

|\Psi_0\rangle = \tfrac{1}{\sqrt 6}\Big( |\{1,2\}\rangle|A,B\rangle + |\{1,3\}\rangle|A,C\rangle + |\{1,4\}\rangle|A,B\rangle + |\{2,3\}\rangle|B,C\rangle + |\{2,4\}\rangle|B,B\rangle + |\{3,4\}\rangle|C,B\rangle \Big).

Setup cost: r = 2 queries per subset, but done in superposition — total 2 oracle queries. Why 2 queries suffice: the preparation unitary queries the oracle twice, each time in superposition over an index within the subset. The superposition of query outcomes then produces the correct stored-values register for all 6 subsets in parallel. This is the query-counting accounting for preparing the Johnson-walk starting state.

Step 4: the walk. Johnson graph J(4, 2) has 6 vertices, each connected to r(N-r) = 2 \cdot 2 = 4 neighbours (swap one of 2 in-elements for one of 2 out-elements). The classical walk on J(4,2) has spectral gap \Delta \approx 1/r = 1/2. With \varepsilon = 1/6 and \Delta = 1/2, the MNRS formula gives \sqrt{1/\varepsilon} \cdot \sqrt{1/\Delta} \approx \sqrt 6 \cdot \sqrt 2 \approx 3.5 walk steps. Round up: 4 walk steps, each with 1 query.

Step 5: total queries. r + N/\sqrt r = 2 + 4/\sqrt 2 \approx 2 + 2.8 \approx 5. Classical worst case for N = 4 is 4. On this toy size the quantum walk is not actually faster — the asymptotic N^{2/3} only beats N for N large enough. For N = 4, N^{2/3} \approx 2.5 versus classical 4 — the constants matter more than the asymptotics for tiny N.

Result. The walk-plus-amplitude-amplification procedure concentrates amplitude on the marked subset \{2, 4\}, and a final measurement with high probability reveals a pair of indices (i, j) with x_i = x_j. For N in the thousands, the algorithm uses \sim N^{2/3} queries versus classical N, a roughly N^{1/3}-fold savings.

What this shows. The algorithm is not about cleverly inspecting each index. It is about setting up a structured search — the Johnson graph — where the quantum walk's mixing properties match the combinatorial structure of the collision problem. For small N the quantum constants do not beat the classical straight-line N-query algorithm; the asymptotic speedup shows up only once N is large enough that N^{2/3} is meaningfully smaller than N (say N \ge 100 or so).

Example 2: Why $r = N^{2/3}$ is the minimum

Derive the N^{2/3} minimiser explicitly.

Step 1: the query-cost function. From the MNRS framework, the total query count for element distinctness on the Johnson graph is

T(r) = r + \frac{N}{\sqrt r}.

The first term is the setup; the second is the walk. You want to choose r to minimise T(r) over r \in \{2, 3, \ldots, N\}.

Step 2: differentiate. Treating r as continuous and differentiating:

\frac{dT}{dr} = 1 - \frac{N}{2 r^{3/2}}.

Why differentiating works: T(r) is smooth and unimodal on [1, \infty) — the first term grows linearly, the second decays as r^{-1/2}, and their sum has a unique interior minimum. The calculus tool exactly finds it.

Step 3: set to zero. \tfrac{dT}{dr} = 0 gives 1 = \tfrac{N}{2 r^{3/2}}, i.e. r^{3/2} = \tfrac{N}{2}, so

r^* = \left(\tfrac{N}{2}\right)^{2/3} = \frac{N^{2/3}}{2^{2/3}}.

The optimal subset size is N^{2/3}, up to a constant.

Step 4: the minimum value. Plug r^* = (N/2)^{2/3} back into T:

T(r^*) = \left(\tfrac{N}{2}\right)^{2/3} + \frac{N}{\left(\tfrac{N}{2}\right)^{1/3}} = \left(\tfrac{N}{2}\right)^{2/3} + N \cdot \left(\tfrac{2}{N}\right)^{1/3} = \left(\tfrac{N}{2}\right)^{2/3} + 2^{1/3} \cdot N^{2/3}.

Both terms are \Theta(N^{2/3}), summing to approximately (1 + 2) \cdot (N/2)^{2/3} / \text{factor} = \Theta(N^{2/3}). The leading constant is not particularly clean, but for asymptotic analysis all that matters is that both components scale as N^{2/3} and the minimum is \Theta(N^{2/3}).

Step 5: intuition. Too small an r, say r = 1: you are doing Grover over single elements, but the "collision" you are looking for is a pair, so \varepsilon = 0 and the walk cannot find it. Too large an r, say r = N: you have queried everything in setup, and there is no walking to do — T(N) = N, matching classical. The minimum lies strictly between — at the balance point where setup cost equals walk cost, which is r = N/\sqrt r, i.e. r^{3/2} = N, r = N^{2/3}.

Result. The optimal subset size for the Johnson-walk algorithm on element distinctness is r = N^{2/3}, and the total query complexity is T(r^*) = \Theta(N^{2/3}).

What this shows. The N^{2/3} scaling is not arbitrary. It is the balance point of a two-component trade-off: setup scales with r, walking scales with N/\sqrt r. The balance always happens at r to the 3/2 power equalling N, giving the N^{2/3} exponent. This same balancing logic — different exponents, same shape — produces n^{5/3} for matrix verification, n^{13/10} for triangle-finding before improvements, and the (k-1)/k exponents for k-distinctness. Once you recognise the template, you can derive the query exponent for a new walk-based algorithm by setting up setup-versus-walk costs and minimising.

Common confusions

"Element distinctness is like Grover's search." Both are quantum search problems, but Grover's answer space is single items (N^{1/2} speedup); element distinctness's answer is a pair, which Grover-on-pairs does not accelerate. Walks bridge the gap: N^{2/3}, better than classical N, worse than Grover's \sqrt N on pairs would be if it worked. The walk's structure — being on the Johnson graph of subsets — is what lets you beat naive Grover.
"N^{2/3} is the square-root of N^{4/3}." It is; more usefully it is N^{1 - 1/3}. You save a factor of N^{1/3} over classical N. For N = 10^6, that is a factor of 100 — meaningful.
"The subset size r is a free parameter the user chooses." Mathematically yes; operationally the algorithm designer sets r = \lceil N^{2/3} \rceil once and runs. The "choice" is a tuning decision made at algorithm-design time, not at runtime.
"The O(N^{2/3}) bound is just a conjecture." No. It is a proven upper bound (Ambainis 2003) and a proven matching lower bound (Aaronson-Shi 2004). Element distinctness is one of the most satisfyingly nailed-down problems in quantum query complexity.
"Element distinctness lets you crack hashes." The closely related collision problem — given a function promised to be one-to-one or two-to-one, decide which — has \Theta(N^{1/3}) quantum complexity (Brassard-Høyer-Tapp 1997). This is relevant to hash-function collision resistance: a quantum attacker finds a collision in an n-bit hash in 2^{n/3} queries versus classical 2^{n/2}. The standard response is to use a hash with 3n/2 output bits for n bits of security.
"Ambainis's algorithm needs a million qubits." For N items, the register size is O(N^{2/3} \cdot \log M) qubits — polynomial in N but not tiny. For N = 10^6 and M = 2^{20}, the register is around 10^4 \cdot 20 = 200{,}000 qubits. This is orders of magnitude beyond NISQ-era hardware. Element distinctness, like most quantum-walk algorithms, is a fault-tolerant-era algorithm.

Going deeper

If you understand that classical element distinctness needs \Omega(N) queries, that Grover-on-pairs gives O(N) and is therefore no help, that Ambainis's 2003 quantum walk on the Johnson graph J(N, r) with r = N^{2/3} gives O(N^{2/3}) queries, that Aaronson-Shi 2004 proved this is tight via the polynomial method, and that the same framework handles collision finding, triangle finding, and matrix verification — you have chapter 184. What follows is the rigorous version: the MNRS instantiation in detail, the polynomial-method lower bound sketch, the span-program reformulation, and the modern state of walk-based algorithms.

The MNRS formula on the Johnson graph

The Johnson graph J(N, r) has vertices \binom{[N]}{r} (size-r subsets) and edges \{R, R'\} where |R \triangle R'| = 2 (symmetric difference of size 2, i.e. single-element swap). Its parameters:

Number of vertices: \binom{N}{r}.
Regular of degree: r(N - r).
Classical random walk spectral gap: \Delta = \frac{N}{r(N - r)} \approx \frac{1}{r} for r \ll N.
Fraction of marked vertices (one collision): \varepsilon = \frac{\binom{N-2}{r-2}}{\binom{N}{r}} = \frac{r(r-1)}{N(N-1)} \approx \frac{r^2}{N^2}.

Plug into MNRS:

T = S + \frac{1}{\sqrt \varepsilon}\left(\frac{U}{\sqrt \Delta} + C\right) = r + \frac{N}{r}\left(\sqrt r + 0\right) = r + \frac{N}{\sqrt r}.

Optimising over r gives r^* = N^{2/3} and T^* = \Theta(N^{2/3}).

The cost accounting: setup is r queries (building the size-r subset register); each walk step costs 1 query (swap one element); check is 0 queries (inspect the already-stored values for a duplicate).

The polynomial-method lower bound, in outline

The polynomial method (Beals-Buhrman-Cleve-Mosca-de Wolf 2001) says: any quantum algorithm with T queries to an oracle f has the property that its acceptance probability, as a function of the N bits of f, is a polynomial of degree at most 2T in those bits.

For element distinctness, the input is the function values x_1, \ldots, x_N. You can boolean-encode each value as \log M bits, so the input has N \log M bits. A quantum algorithm accepting with high probability when the input has a collision and rejecting when it does not must be computed by a low-degree polynomial of these input bits.

Aaronson-Shi's argument constructs a symmetric polynomial over the Johnson scheme (the association scheme whose orbits are Johnson graphs) and uses lower bounds on symmetric polynomials approximating the characteristic function of the collision set. The combinatorics yields a lower bound of \Omega(N^{2/3}) on the degree, hence \Omega(N^{2/3} / 2) = \Omega(N^{2/3}) on the query complexity.

This is one of the cleanest applications of the polynomial method, and the Aaronson-Shi paper is a standard reference in quantum query complexity.

Span programs and the Belovs reformulation

Aleksandrs Belovs (2012) gave an alternative construction of the element-distinctness algorithm using span programs — a framework originally from classical complexity that Reichardt showed fits quantum query complexity perfectly. The span-program version of Ambainis's algorithm is slightly cleaner and generalises more naturally to k-distinctness (for k \ge 3). Belovs's framework also gave the optimal O(N^{(k-1)/k + o(1)}) upper bounds for k-distinctness, matching partial lower bounds.

The span-program formulation of quantum walks is, for the theorist, perhaps the most illuminating. Walks on graphs become span programs on associated matrices. The MNRS framework becomes a special case of span-program-based search. QSVT unifies everything at the top.

The modern frontier

Post-Ambainis-2003 walk-based algorithms have kept appearing:

Triangle finding (Magniez-Santha-Szegedy 2005; later improvements by Belovs, Le Gall, Lee-Magniez-Santha 2013) — from \tilde O(n^{13/10}) down to \tilde O(n^{5/4}), with the current best around n^{1.2}.
Graph collision and related problems — a family of problems about finding specific patterns in graphs, with walk-based algorithms active to the present day.
Subset sum and learning with errors — quantum walk ingredients appear in the design of quantum attacks on post-quantum cryptography, though these involve walks as subroutines rather than as the whole algorithm.

The elements-distinctness result itself has not been improved since Aaronson-Shi, because the matching upper and lower bounds closed the problem. But the framework — quantum walk on a Johnson-like graph, with subset size chosen to balance setup and walk costs — continues to be applied to new problems.

Why element distinctness is the canonical walk-based result

Of all the walk-based algorithms, element distinctness is taught first because it is the cleanest: well-defined problem, clean N^{2/3} answer, matching lower bound, and a single parameter (r) to tune. Triangle finding is messier (multiple bounds, ongoing improvements); k-distinctness requires span programs; collision finding predates walks technically. Element distinctness sits at the sweet spot — advanced enough to showcase walk-based thinking, accessible enough to work out by hand as you just did.

Every student of quantum algorithms meets element distinctness. It is the problem that convinced the field that walks were not a curiosity but a core technique.

Where this leads next

Discrete Quantum Walks — the coin-and-shift model and the Szegedy walk this chapter depends on.
Continuous Quantum Walks — the Hamiltonian flavour and the glued-trees exponential speedup.
Collision Finding Quantum — the sister problem solved in O(N^{1/3}).
Triangle Finding — the multi-parameter walk-based generalisation.

References

Andris Ambainis, Quantum walk algorithm for element distinctness (2003), SIAM J. Comp. — arXiv:quant-ph/0311001. The O(N^{2/3}) algorithm.
Scott Aaronson, Yaoyun Shi, Quantum lower bounds for the collision and the element distinctness problems (2004), J. ACM — author copy. The tight lower bound.
Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha, Search via quantum walk (2007) — arXiv:quant-ph/0608026. The MNRS framework.
Aleksandrs Belovs, Span programs for functions with constant-sized 1-certificates (2012), STOC — arXiv:1105.4024. The span-program reformulation and k-distinctness.
Gilles Brassard, Peter Høyer, Alain Tapp, Quantum cryptanalysis of hash and claw-free functions (1997) — arXiv:quant-ph/9705002. The O(N^{1/3}) collision algorithm.
Wikipedia, Element distinctness problem.