Algorithms · Quantum walk
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.
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 speedupStated by the primary source: "We introduce the first subset-sum algorithm that beats 2^{n/4}. Specifically, we introduce a quantum algorithm that, under reasonable assumptions, uses at most 2^{(0.241…+o(1))n} qubit operations to solve a subset-sum problem."
- Reported cost2^{(0.241…+o(1))n} qubit operations, where n is the number of integers x₁, …, xₙ and the paper lists an algorithm using 2^{(e+o(1))n} operations as exponent e. The classical algorithms the paper names for the same problem: brute force at 2ⁿ, the Horowitz-Sahni left-right split at 2^{n/2}, and Howgrave-Graham and Joux's representation algorithm at 2^{(0.337…+o(1))n}. The best classical exponent, 0.291… from Becker, Coron and Joux, appears in the paper's comparison table and in no sentence of its text.
- Papers1
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. The algorithm layers three things. From Howgrave-Graham and Joux it takes the representation technique: a solution of weight n/2 is split into overlapping halves in many ways at once, so a solution can be found from any one of its representations rather than from a single fixed decomposition. From Ambainis's element-distinctness algorithm it takes a discrete-time quantum walk on a Johnson graph, whose vertices are r-element subsets of the b-bit strings and whose edges join sets differing in one element. The paper's own contribution is the data structure that makes the walk implementable: Ambainis handles the walk's memory with what the authors call an ad-hoc combination of a hash table and a skip list requiring several pages of analysis, and they replace it with a radix tree. The problem a walk's memory has is history dependence — the stored state must not remember the order in which elements arrived, or the superposition fails to interfere — and the authors solve it by putting a uniform superposition over all possible memory layouts of the nodes, which they say produces a unique quantum data structure representing the set.
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 →
The algorithm layers three things. From Howgrave-Graham and Joux it takes the representation technique: a solution of weight n/2 is split into overlapping halves in many ways at once, so a solution can be found from any one of its representations rather than from a single fixed decomposition. From Ambainis's element-distinctness algorithm it takes a discrete-time quantum walk on a Johnson graph, whose vertices are r-element subsets of the b-bit strings and whose edges join sets differing in one element. The paper's own contribution is the data structure that makes the walk implementable: Ambainis handles the walk's memory with what the authors call an ad-hoc combination of a hash table and a skip list requiring several pages of analysis, and they replace it with a radix tree. The problem a walk's memory has is history dependence — the stored state must not remember the order in which elements arrived, or the superposition fails to interfere — and the authors solve it by putting a uniform superposition over all possible memory layouts of the nodes, which they say produces a unique quantum data structure representing the set. This record's speedup class, "Polynomial", is a secondary source's classification of the algebraic and number theoretic algorithms it files this under — not a claim its primary paper makes. Stated by the primary source: "We introduce the first subset-sum algorithm that beats 2^{n/4}. Specifically, we introduce a quantum algorithm that, under reasonable assumptions, uses at most 2^{(0.241…+o(1))n} qubit operations to solve a subset-sum problem.". Reported cost: 2^{(0.241…+o(1))n} qubit operations, where n is the number of integers x₁, …, xₙ and the paper lists an algorithm using 2^{(e+o(1))n} operations as exponent e. The classical algorithms the paper names for the same problem: brute force at 2ⁿ, the Horowitz-Sahni left-right split at 2^{n/2}, and Howgrave-Graham and Joux's representation algorithm at 2^{(0.337…+o(1))n}. The best classical exponent, 0.291… from Becker, Coron and Joux, appears in the paper's comparison table and in no sentence of its text..
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
- Stated by the primary source: "We introduce the first subset-sum algorithm that beats 2^{n/4}. Specifically, we introduce a quantum algorithm that, under reasonable assumptions, uses at most 2^{(0.241…+o(1))n} qubit operations to solve a subset-sum problem."
- Reported cost
- 2^{(0.241…+o(1))n} qubit operations, where n is the number of integers x₁, …, xₙ and the paper lists an algorithm using 2^{(e+o(1))n} operations as exponent e. The classical algorithms the paper names for the same problem: brute force at 2ⁿ, the Horowitz-Sahni left-right split at 2^{n/2}, and Howgrave-Graham and Joux's representation algorithm at 2^{(0.337…+o(1))n}. The best classical exponent, 0.291… from Becker, Coron and Joux, appears in the paper's comparison table and in no sentence of its text.
- Speedup class
- Polynomial (checked against the record's own primary paper, which states it)
- Complexity basis
- abstract: "This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25."; section 1: "We introduce the first subset-sum algorithm that beats 2^{n/4}. Specifically, we introduce a quantum algorithm that, under reasonable assumptions, uses at most 2^{(0.241…+o(1))n} qubit operations to solve a subset-sum problem."; the exponent convention is Table 1.1's own caption, "An algorithm using 2^{(e+o(1))n} operations is listed as 'exponent' e."; for the classical baseline, section 5: "Howgrave-Graham and Joux introduced this technique in [17] and obtained a subset-sum algorithm that costs just 2^{(0.337…+o(1))n}." Read from the authors' own full text (cr.yp.to, dated 2013.04.07), all eighteen pages, not from the abstract.
- 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-sum by quantum walk over representations
PROBLEM: 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.
IDEA: The algorithm layers three things. From Howgrave-Graham and Joux it takes the representation technique: a solution of weight n/2 is split into overlapping halves in many ways at once, so a solution can be found from any one of its representations rather than from a single fixed decomposition. From Ambainis's element-distinctness algorithm it takes a discrete-time quantum walk on a Johnson graph, whose vertices are r-element subsets of the b-bit strings and whose edges join sets differing in one element. The paper's own contribution is the data structure that makes the walk implementable: Ambainis handles the walk's memory with what the authors call an ad-hoc combination of a hash table and a skip list requiring several pages of analysis, and they replace it with a radix tree. The problem a walk's memory has is history dependence — the stored state must not remember the order in which elements arrived, or the superposition fails to interfere — and the authors solve it by putting a uniform superposition over all possible memory layouts of the nodes, which they say produces a unique quantum data structure representing the set.
REPORTED COST: 2^{(0.241…+o(1))n} qubit operations, where n is the number of integers x₁, …, xₙ and the paper lists an algorithm using 2^{(e+o(1))n} operations as exponent e. The classical algorithms the paper names for the same problem: brute force at 2ⁿ, the Horowitz-Sahni left-right split at 2^{n/2}, and Howgrave-Graham and Joux's representation algorithm at 2^{(0.337…+o(1))n}. The best classical exponent, 0.291… from Becker, Coron and Joux, appears in the paper's comparison table and in no sentence of its text.
BASIS: abstract: "This paper introduces a subset-sum algorithm with heuristic asymptotic cost exponent below 0.25."; section 1: "We introduce the first subset-sum algorithm that beats 2^{n/4}. Specifically, we introduce a quantum algorithm that, under reasonable assumptions, uses at most 2^{(0.241…+o(1))n} qubit operations to solve a subset-sum problem."; the exponent convention is Table 1.1's own caption, "An algorithm using 2^{(e+o(1))n} operations is listed as 'exponent' e."; for the classical baseline, section 5: "Howgrave-Graham and Joux introduced this technique in [17] and obtained a subset-sum algorithm that costs just 2^{(0.337…+o(1))n}." Read from the authors' own full text (cr.yp.to, dated 2013.04.07), all eighteen pages, not from the abstract.
PRIMARY SOURCE: Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, Alexander Meurer (2013), Quantum algorithms for the subset-sum problem — https://doi.org/10.1007/978-3-642-38616-9_2
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
- Subset finding by quantum walk
Algorithms
- Element distinctness by quantum walk
Algorithms
- Grover unstructured search
Algorithms
- Average-case lattice problem variants by filtering
Algorithms
References
- Quantum algorithms for the subset-sum problem
Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, Alexander Meurer · 2013
Primary source and the source of every figure here. Section 1 carries both the cost exponent and the two sentences that scope it — the free-quantum-RAM convention and the statement that the analyses are heuristic. Table 1.1 is the comparison against the other eleven algorithms, quantum and classical, and is the only place the best classical exponent appears. Section 3 is the walk and the radix tree that replaces Ambainis's memory structure; section 5 is the representation technique and the final cost. The version of record is the Springer chapter; the authors' own full text is on cr.yp.to and carries no DOI or venue on its face.