Algorithms · Quantum walk
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.
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 stated by the primary source — the full text of arXiv:quant-ph/0311038 — abstract, section I (introduction), section II (algorithm), section III (analysis), section IV (applications), section V (open problems), the note added and the references. The word "classical" does not appear in the body text. Every comparison the paper makes is against quantum query lower bounds — the Ω(√N) bound for L = 1 and the Ω(N^(2/3)) bound for element distinctness — rather than against the cost of a classical algorithm. was read and makes no such claim
- Reported costO(N^(L/(L+1))) queries for L-subset finding. The L-clique application is given in two variants: a simple one using O(N^(2L/(L+1))) edge queries and a recursive one using Õ(N^((5L−2)/(2L+4))), which the abstract says is an improvement for L ≤ 5.
- Papers1
A part this method uses, worked through
This page says Grover diffusion operators
— 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 StudioIn 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. Childs and Eisenberg rework Ambainis's discrete-time quantum walk for element distinctness. The walk runs on a bipartite graph whose vertices are the size-M and size-(M+1) subsets of D, each vertex carrying the subset together with the function values already queried for it. A shift operator costing one query moves between the two subset sizes, Grover diffusion operators act as coins on the element added or removed, and a phase flip marks any subset that already contains a solution — a check that costs no further queries once the values are stored. Running the walk interleaved with the phase flip, for iteration counts chosen from a spectral and perturbative analysis of the walk operator, rotates amplitude from the symmetric initial state onto a solution state with probability close to one. The same construction is then applied to finding an L-clique in a graph, in two variants.
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 →
Childs and Eisenberg rework Ambainis's discrete-time quantum walk for element distinctness. The walk runs on a bipartite graph whose vertices are the size-M and size-(M+1) subsets of D, each vertex carrying the subset together with the function values already queried for it. A shift operator costing one query moves between the two subset sizes, Grover diffusion operators act as coins on the element added or removed, and a phase flip marks any subset that already contains a solution — a check that costs no further queries once the values are stored. Running the walk interleaved with the phase flip, for iteration counts chosen from a spectral and perturbative analysis of the walk operator, rotates amplitude from the symmetric initial state onto a solution state with probability close to one. The same construction is then applied to finding an L-clique in a graph, in two variants. 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 stated by the primary source — the full text of arXiv:quant-ph/0311038 — abstract, section I (introduction), section II (algorithm), section III (analysis), section IV (applications), section V (open problems), the note added and the references. The word "classical" does not appear in the body text. Every comparison the paper makes is against quantum query lower bounds — the Ω(√N) bound for L = 1 and the Ω(N^(2/3)) bound for element distinctness — rather than against the cost of a classical algorithm. was read and makes no such claim. Reported cost: O(N^(L/(L+1))) queries for L-subset finding. The L-clique application is given in two variants: a simple one using O(N^(2L/(L+1))) edge queries and a recursive one using Õ(N^((5L−2)/(2L+4))), which the abstract says is an improvement for L ≤ 5..
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 stated by the primary source — the full text of arXiv:quant-ph/0311038 — abstract, section I (introduction), section II (algorithm), section III (analysis), section IV (applications), section V (open problems), the note added and the references. The word "classical" does not appear in the body text. Every comparison the paper makes is against quantum query lower bounds — the Ω(√N) bound for L = 1 and the Ω(N^(2/3)) bound for element distinctness — rather than against the cost of a classical algorithm. was read and makes no such claim
- Reported cost
- O(N^(L/(L+1))) queries for L-subset finding. The L-clique application is given in two variants: a simple one using O(N^(2L/(L+1))) edge queries and a recursive one using Õ(N^((5L−2)/(2L+4))), which the abstract says is an improvement for L ≤ 5.
- Speedup class
- Polynomial (checked against the record's own primary paper, which does not state it)
- Complexity basis
- abstract of arXiv:quant-ph/0311038: "an O(N^{L/(L+1)})-query algorithm for finding L equal numbers… One of these algorithms uses O(N^{2L/(L+1)}) edge queries, and the other uses Õ(N^{(5L−2)/(2L+4)}), which is an improvement for L ≤ 5."; section III, Theorem 1: "The quantum query complexity of L-subset finding is O(N^{L/(L+1)})."; section IV, for the two clique variants: "choosing M = ⌊N^{L/(L+1)}⌋ gives an overall query complexity of O(N^{2L/(L+1)})" and "choosing M = ⌊N^{L/(L+2)}⌋ gives an overall query complexity of Õ(N^{(5L−2)/(2L+4)})".
- 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: Subset finding by quantum walk
PROBLEM: 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.
IDEA: Childs and Eisenberg rework Ambainis's discrete-time quantum walk for element distinctness. The walk runs on a bipartite graph whose vertices are the size-M and size-(M+1) subsets of D, each vertex carrying the subset together with the function values already queried for it. A shift operator costing one query moves between the two subset sizes, Grover diffusion operators act as coins on the element added or removed, and a phase flip marks any subset that already contains a solution — a check that costs no further queries once the values are stored. Running the walk interleaved with the phase flip, for iteration counts chosen from a spectral and perturbative analysis of the walk operator, rotates amplitude from the symmetric initial state onto a solution state with probability close to one. The same construction is then applied to finding an L-clique in a graph, in two variants.
REPORTED COST: O(N^(L/(L+1))) queries for L-subset finding. The L-clique application is given in two variants: a simple one using O(N^(2L/(L+1))) edge queries and a recursive one using Õ(N^((5L−2)/(2L+4))), which the abstract says is an improvement for L ≤ 5.
BASIS: abstract of arXiv:quant-ph/0311038: "an O(N^{L/(L+1)})-query algorithm for finding L equal numbers… One of these algorithms uses O(N^{2L/(L+1)}) edge queries, and the other uses Õ(N^{(5L−2)/(2L+4)}), which is an improvement for L ≤ 5."; section III, Theorem 1: "The quantum query complexity of L-subset finding is O(N^{L/(L+1)})."; section IV, for the two clique variants: "choosing M = ⌊N^{L/(L+1)}⌋ gives an overall query complexity of O(N^{2L/(L+1)})" and "choosing M = ⌊N^{L/(L+2)}⌋ gives an overall query complexity of Õ(N^{(5L−2)/(2L+4)})".
PRIMARY SOURCE: Andrew M. Childs, Jason M. Eisenberg (2003), Quantum algorithms for subset finding — https://arxiv.org/abs/quant-ph/0311038
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
- Element distinctness by quantum walk
Algorithms
- Grover unstructured search
Algorithms
- Discrete-time quantum walk on a line
Algorithms
References
- Quantum algorithms for subset finding
Andrew M. Childs, Jason M. Eisenberg · 2003
Primary source, and the source of this record's cost claim. Consult it for the uniqueness promise the analysis assumes, for the spectral argument that fixes the two iteration counts, and for section V, where the matching lower bound for general L is left as a conjecture and the best known bound is stated as Ω(N^(2/3)) independent of L.