Algorithms · Quantum walk
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.
Attested & literatureUpdated
Open on the mapView frozen graph
A small worked example, computed in your browser. It is not a result from this record's papers.
A discrete-time quantum walk on a 4-cycle
One coin qubit, two position qubits (4 positions on a cycle), 3 steps starting at position 0.
Step 1 of 3 · Quantum walk step (4-cycle)
Probability of each outcome after this step
- 01150%
- 11050%
Flips the coin with a Hadamard, then shifts the position by +1 if the coin is |1⟩ or -1 mod 4 if the coin is |0⟩; with the coin in superposition, both shifts happen at once, entangling coin and position.
Probability leaves the outcome it was on and appears on 2 entirely different ones — not one outcome is populated both before and after. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
The same coin flip and shift, applied again.
Probability leaves all 2 outcomes it was on and appears on 4 entirely different ones — not one outcome is populated both before and after.
The same coin flip and shift, a third time.
Probability leaves all 4 outcomes it was on and appears on 2 entirely different ones — not one outcome is populated both before and after. The entanglement comes apart here: each qubit has a state of its own again.
Readout The position always reads 3, for either value of the coin: constructive interference on this small cycle concentrates the walk onto a single position after exactly 3 steps.
Open in Studio- Record typeLiterature reference
- Speedup class (secondary source)Polynomial
- Primary source on the speedupNot checked against the primary source yet
- Reported costO(N^(2/3)) queries for element distinctness on N items, matching the lower bound of Shi and improving the previous O(N^(3/4))-query quantum algorithm; the same algorithm uses O(N^(k/(k+1))) queries to find k equal items among N. The Zoo gives Θ(N) classical query complexity for element distinctness, and for the two-to-one collision problem O(N^(1/3)) quantum queries against Θ(√N) classical randomized queries, with Brassard, Hoyer and Tapp stating O((N/r)^(1/3)) expected function evaluations for r-to-one functions.
- Papers2
A part this method uses, worked through
This page says Grover's search
— here is a concrete, runnable instance of it.
Grover's algorithm finds |101⟩
3 qubits, searching for |101⟩ among 8 states, with 2 Grover iterations.
Where it ends up
- 10195%
- 0001%
- 1101%
- 0011%
- 4 more outcomes3%
Measuring gives 101, the marked state, with high probability.
One of its steps changes only phase: the outcome probabilities stay put while the state does not.
Open this part in StudioGiven 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. Ambainis builds the algorithm out of a quantum walk instead of a direct search, which is what improves on the earlier O(N^(3/4))-query quantum algorithm the abstract credits to Buhrman et al. and matches the query lower bound of Shi. The same construction also solves the generalization in which k equal items must be found among N. The easier promised version is older: when f is r-to-one, Brassard, Hoyer and Tapp give an algorithm that finds a collision by using Grover's search in a novel way, and their technique also yields a claw-finding algorithm for a pair of functions and a space-time tradeoff. The Zoo groups the two under one entry because dropping the two-to-one promise is exactly what turns collision finding into element distinctness.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Ambainis builds the algorithm out of a quantum walk instead of a direct search, which is what improves on the earlier O(N^(3/4))-query quantum algorithm the abstract credits to Buhrman et al. and matches the query lower bound of Shi. The same construction also solves the generalization in which k equal items must be found among N. The easier promised version is older: when f is r-to-one, Brassard, Hoyer and Tapp give an algorithm that finds a collision by using Grover's search in a novel way, and their technique also yields a claw-finding algorithm for a pair of functions and a space-time tradeoff. The Zoo groups the two under one entry because dropping the two-to-one promise is exactly what turns collision finding into element distinctness. This record's speedup class, "Polynomial", is a secondary source's classification of the oracular algorithms it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: O(N^(2/3)) queries for element distinctness on N items, matching the lower bound of Shi and improving the previous O(N^(3/4))-query quantum algorithm; the same algorithm uses O(N^(k/(k+1))) queries to find k equal items among N. The Zoo gives Θ(N) classical query complexity for element distinctness, and for the two-to-one collision problem O(N^(1/3)) quantum queries against Θ(√N) classical randomized queries, with Brassard, Hoyer and Tapp stating O((N/r)^(1/3)) expected function evaluations for r-to-one functions..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Speedup class (secondary source)
- Polynomial
- Primary source on the speedup
- Not checked against the primary source yet
- Reported cost
- O(N^(2/3)) queries for element distinctness on N items, matching the lower bound of Shi and improving the previous O(N^(3/4))-query quantum algorithm; the same algorithm uses O(N^(k/(k+1))) queries to find k equal items among N. The Zoo gives Θ(N) classical query complexity for element distinctness, and for the two-to-one collision problem O(N^(1/3)) quantum queries against Θ(√N) classical randomized queries, with Brassard, Hoyer and Tapp stating O((N/r)^(1/3)) expected function evaluations for r-to-one functions.
- Speedup class
- Polynomial (not yet checked against the record's own primary paper)
- Complexity basis
- abstract of arXiv:quant-ph/0311001: "For element distinctness (the problem of finding two equal items among N given items), we get an O(N^{2/3}) query quantum algorithm. This improves the previous O(N^{3/4}) query quantum algorithm of Buhrman [link mangled to 'this http URL' on the abs page] (quant-ph/0007016) and matches the lower bound by Shi (quant-ph/0112086)", and "For this problem, we get an O(N^{k/(k+1)}) query quantum algorithm"; Zoo entry "Collision Finding and Element Distinctness": element distinctness "has Θ(N) classical query complexity", and for the collision problem "The classical randomized query complexity of this problem is Θ(√N), whereas ... a quantum computer can achieve this using O(N^{1/3}) queries"; abstract of arXiv:quant-ph/9705002: "finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function".
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum walk with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Element distinctness by quantum walk
PROBLEM: 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.
IDEA: Ambainis builds the algorithm out of a quantum walk instead of a direct search, which is what improves on the earlier O(N^(3/4))-query quantum algorithm the abstract credits to Buhrman et al. and matches the query lower bound of Shi. The same construction also solves the generalization in which k equal items must be found among N. The easier promised version is older: when f is r-to-one, Brassard, Hoyer and Tapp give an algorithm that finds a collision by using Grover's search in a novel way, and their technique also yields a claw-finding algorithm for a pair of functions and a space-time tradeoff. The Zoo groups the two under one entry because dropping the two-to-one promise is exactly what turns collision finding into element distinctness.
REPORTED COST: O(N^(2/3)) queries for element distinctness on N items, matching the lower bound of Shi and improving the previous O(N^(3/4))-query quantum algorithm; the same algorithm uses O(N^(k/(k+1))) queries to find k equal items among N. The Zoo gives Θ(N) classical query complexity for element distinctness, and for the two-to-one collision problem O(N^(1/3)) quantum queries against Θ(√N) classical randomized queries, with Brassard, Hoyer and Tapp stating O((N/r)^(1/3)) expected function evaluations for r-to-one functions.
BASIS: abstract of arXiv:quant-ph/0311001: "For element distinctness (the problem of finding two equal items among N given items), we get an O(N^{2/3}) query quantum algorithm. This improves the previous O(N^{3/4}) query quantum algorithm of Buhrman [link mangled to 'this http URL' on the abs page] (quant-ph/0007016) and matches the lower bound by Shi (quant-ph/0112086)", and "For this problem, we get an O(N^{k/(k+1)}) query quantum algorithm"; Zoo entry "Collision Finding and Element Distinctness": element distinctness "has Θ(N) classical query complexity", and for the collision problem "The classical randomized query complexity of this problem is Θ(√N), whereas ... a quantum computer can achieve this using O(N^{1/3}) queries"; abstract of arXiv:quant-ph/9705002: "finds collisions in arbitrary r-to-one functions after only O((N/r)^(1/3)) expected evaluations of the function".
PRIMARY SOURCE: Andris Ambainis (2003), Quantum walk algorithm for element distinctness — https://arxiv.org/abs/quant-ph/0311001
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Where this sits
This record is named by the layer graph at:
- Walk over subsets that remember their queries Method
Takes 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. Returns 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.
Related entries
- Discrete-time quantum walk on a line
Algorithms
- Grover unstructured search
Algorithms
- Amplitude amplification
Algorithms
References
- Quantum walk algorithm for element distinctness
Andris Ambainis · 2003
Primary reference for element distinctness by quantum walk; the source of this record's cost claim.
- Quantum Algorithm for the Collision Problem
Gilles Brassard, Peter Hoyer, Alain Tapp · 1997
The promised half of the same Zoo entry. For arbitrary r-to-one functions given as a black box the authors find collisions in O((N/r)^(1/3)) expected evaluations, more efficient than any classical algorithm even with randomization, and they extend the technique to claw finding in pairs of functions and exhibit a space-time tradeoff.