Attested & literatureAlgorithmsQuantum query algorithm2026-08-12

Quantum dynamic programming for path in the hypercube

dynamic programminggrover searchhypercubenp-completeexponential time

Atlas stars stay in the public catalog. Saving this entry to your workspace starts an unstarred private copy.

Given a subgraph of the Boolean hypercube on bit strings of length n, whose edges all run from smaller to larger Hamming weight, decide whether it contains a path from the all-zeros vertex 0^n to the all-ones vertex 1^n. Ambainis, Balodis, Iraids, Kokainis, Prūsis and Vihrovs introduce the path in the hypercube problem, which the paper states models many of the NP-complete problems whose best classical algorithm is an exponential-time application of dynamic programming, and the Zoo likewise records that many such problems can be modelled as instances of it. The technique the paper describes combines Grover's search with computing a partial dynamic programming table, and the bound it reports for that technique, O*(1.817^n), has a smaller base than the O*(2^n) the Zoo gives for the fastest known classical algorithm. The same approach is then applied to a variety of vertex ordering problems on graphs and to graph bandwidth, and similar ideas to the travelling salesman problem and minimum set cover. The Zoo adds the reading of the graph itself, that the vertices of the hypercube graph correspond to bit strings of length n and that the graph joins vertices of Hamming distance one, and it lists feedback arc set alongside the travelling salesman problem among the problems this primitive is applied to.

Circuit & simulation

problem

encodetransform

algorithm

transformmeasure

readout

measure

What this takes and returns

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 →

How it works

Ambainis, Balodis, Iraids, Kokainis, Prūsis and Vihrovs introduce the path in the hypercube problem, which the paper states models many of the NP-complete problems whose best classical algorithm is an exponential-time application of dynamic programming, and the Zoo likewise records that many such problems can be modelled as instances of it. The technique the paper describes combines Grover's search with computing a partial dynamic programming table, and the bound it reports for that technique, O*(1.817^n), has a smaller base than the O*(2^n) the Zoo gives for the fastest known classical algorithm. The same approach is then applied to a variety of vertex ordering problems on graphs and to graph bandwidth, and similar ideas to the travelling salesman problem and minimum set cover. The Zoo adds the reading of the graph itself, that the vertices of the hypercube graph correspond to bit strings of length n and that the graph joins vertices of Hamming distance one, and it lists feedback arc set alongside the travelling salesman problem among the problems this primitive is applied to. This record's speedup class, "Polynomial", is a secondary source's classification of the optimization, numerics, and machine learning it files this under — not a claim its primary paper makes. Not checked against the primary source yet. Reported cost: O*(1.817^n) for path in the hypercube on bit strings of length n, where O* omits polynomial factors, against O*(2^n) for the fastest known classical algorithm; the abstract reports the same approach for vertex ordering problems in O*(1.817^n), which the Zoo sets against O*(2^n) classically, and for graph bandwidth in O*(2.946^n), set against O*(4.383^n) classically, and reports similar ideas for the travelling salesman problem and minimum set cover in O*(1.728^n), with minimum set cover stated by the Zoo as O(poly(m,n) 1.728^n) against O(nm2^n) classically. The two sources differ on one figure: where the abstract writes 1.728^n for the travelling salesman problem and minimum set cover together, the Zoo writes 1.729^n for traveling salesman and feedback arc set against O*(2^n) classically and gives minimum set cover a figure of its own..

Implementation

FrameworkUnsupported

hypercube-dynamic-programming.txt

ALGORITHM: Quantum dynamic programming for path in the hypercube
PROBLEM: Given a subgraph of the Boolean hypercube on bit strings of length n, whose edges all run from smaller to larger Hamming weight, decide whether it contains a path from the all-zeros vertex 0^n to the all-ones vertex 1^n.
IDEA: Ambainis, Balodis, Iraids, Kokainis, Prūsis and Vihrovs introduce the path in the hypercube problem, which the paper states models many of the NP-complete problems whose best classical algorithm is an exponential-time application of dynamic programming, and the Zoo likewise records that many such problems can be modelled as instances of it. The technique the paper describes combines Grover's search with computing a partial dynamic programming table, and the bound it reports for that technique, O*(1.817^n), has a smaller base than the O*(2^n) the Zoo gives for the fastest known classical algorithm. The same approach is then applied to a variety of vertex ordering problems on graphs and to graph bandwidth, and similar ideas to the travelling salesman problem and minimum set cover. The Zoo adds the reading of the graph itself, that the vertices of the hypercube graph correspond to bit strings of length n and that the graph joins vertices of Hamming distance one, and it lists feedback arc set alongside the travelling salesman problem among the problems this primitive is applied to.
REPORTED COST: O*(1.817^n) for path in the hypercube on bit strings of length n, where O* omits polynomial factors, against O*(2^n) for the fastest known classical algorithm; the abstract reports the same approach for vertex ordering problems in O*(1.817^n), which the Zoo sets against O*(2^n) classically, and for graph bandwidth in O*(2.946^n), set against O*(4.383^n) classically, and reports similar ideas for the travelling salesman problem and minimum set cover in O*(1.728^n), with minimum set cover stated by the Zoo as O(poly(m,n) 1.728^n) against O(nm2^n) classically. The two sources differ on one figure: where the abstract writes 1.728^n for the travelling salesman problem and minimum set cover together, the Zoo writes 1.729^n for traveling salesman and feedback arc set against O*(2^n) classically and gives minimum set cover a figure of its own.
BASIS: Abstract of arXiv:1807.05209 (TeX math delimiters removed, exponents left in caret form): "We give a quantum algorithm that solves path in the hypercube in time O^*(1.817^n). The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time O^*(1.817^n), and graph bandwidth in time O^*(2.946^n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O^*(1.728^n)." The classical baselines and the per-problem contrasts are from the Quantum Algorithm Zoo entry "Quantum Dynamic Programming for path-in-the-hypercube" (LaTeX rendered into Unicode: math delimiters removed, the mathrm markup around poly dropped, spacing inside the math closed up): "a quantum algorithm can solve path-in-the-hypercube in time O^*(1.817^n), where the notation O^* indicates that polynomial factors are being omitted. The fastest known classical algorithm for this problem runs in time O^*(2^n)", and "vertex ordering problems in O^*(1.817^n) vs. O^*(2^n) classically, graph bandwidth in O^*(2.946^n) vs. O^*(4.383^n) classically, traveling salesman and feedback arc set in O^*(1.729^n) vs. O^*(2^n) classically, and minimum set cover in O(poly(m,n) 1.728^n) vs. O(nm2^n) classically." The 1.728 / 1.729 difference is recorded as both sources read: the abstract pairs 1.728^n with the travelling salesman problem and minimum set cover together, while the Zoo gives 1.728^n to minimum set cover alone and 1.729^n to traveling salesman and feedback arc set. Neither reading was reconciled here.
PRIMARY SOURCE: Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs (2018), Quantum Speedups for Exponential-Time Dynamic Programming Algorithms — https://arxiv.org/abs/1807.05209

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.

Quantum vs classical

Classical baseline

Compare Quantum query algorithm 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.

Declared gaps

Nobody has reviewed this record for gaps yet.

Literature & references

Quantum Speedups for Exponential-Time Dynamic Programming Algorithms2018 · Andris Ambainis, Kaspars Balodis, Jānis Iraids, Martins Kokainis, Krišjānis Prūsis, Jevgēnijs Vihrovs

Primary source: it introduces path in the hypercube as a model for NP-complete problems whose best classical algorithm is an exponential-time dynamic program, states the O*(1.817^n) algorithm built from Grover's search plus a partial dynamic programming table, and carries the technique to vertex ordering problems, graph bandwidth, the travelling salesman problem and minimum set cover. Consult it for what the partial table costs and for the assumptions behind each derived bound, none of which the abstract states.

arxiv.org/abs/1807.05209 ↗

Verification

Attested & literature

Peer-reviewed paper

Method: Curation only. The problem statement and speedup class were checked against the Quantum Algorithm Zoo's entry "Quantum Dynamic Programming for path-in-the-hypercube" (Optimization, Numerics, and Machine Learning); the primary reference's title, authors and submission year were read from its arXiv abs page; the complexity claim was taken from a clause of that paper's abstract (Abstract of arXiv:1807.05209 (TeX math delimiters removed, exponents left in caret form): "We give a quantum algorithm that solves path in the hypercube in time O^*(1.817^n). The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time O^*(1.817^n), and graph bandwidth in time O^*(2.946^n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O^*(1.728^n)." The classical baselines and the per-problem contrasts are from the Quantum Algorithm Zoo entry "Quantum Dynamic Programming for path-in-the-hypercube" (LaTeX rendered into Unicode: math delimiters removed, the mathrm markup around poly dropped, spacing inside the math closed up): "a quantum algorithm can solve path-in-the-hypercube in time O^*(1.817^n), where the notation O^* indicates that polynomial factors are being omitted. The fastest known classical algorithm for this problem runs in time O^*(2^n)", and "vertex ordering problems in O^*(1.817^n) vs. O^*(2^n) classically, graph bandwidth in O^*(2.946^n) vs. O^*(4.383^n) classically, traveling salesman and feedback arc set in O^*(1.729^n) vs. O^*(2^n) classically, and minimum set cover in O(poly(m,n) 1.728^n) vs. O(nm2^n) classically." The 1.728 / 1.729 difference is recorded as both sources read: the abstract pairs 1.728^n with the travelling salesman problem and minimum set cover together, while the Zoo gives 1.728^n to minimum set cover alone and 1.729^n to traveling salesman and feedback arc set. Neither reading was reconciled here.). No circuit was constructed, simulated or run.
Result: Pass · the record's problem, speedup class and primary reference agree with the two sources named above.
Caveat: This is a literature record: no circuit was constructed, compiled, simulated or run, and no instance of path in the hypercube was decided here. Every figure above is an asymptotic running time as the two sources state it, with O* omitting polynomial factors, so none of it fixes a gate count, a circuit depth, a qubit count, a constant factor or an error-correction budget, and none of it says which n is reachable on a device. The comparison is against the fastest classical algorithm currently known, which the Zoo gives as O*(2^n) for this problem, rather than against a proved classical lower bound, and both sides remain exponential in n. The Zoo classes the speedup as polynomial; neither source gives a reason for that classification and none is supplied here. The two sources also attach the 1.728^n figure to different problems, as noted above, and give the travelling salesman problem different bases, 1.728 in the abstract against 1.729 in the Zoo; nothing here resolves either difference. How the partial dynamic programming table is held and addressed on a quantum device, and the cost of the Grover subroutine's oracle for a concrete graph, are outside this record, as are the NP-complete problems the Zoo says can be modelled as instances of path-in-the-hypercube beyond the ones named.

Facts

Record type: Literature reference
Speedup class (secondary source): Polynomial
Primary source on the speedup: Not checked against the primary source yet
Reported cost: O*(1.817^n) for path in the hypercube on bit strings of length n, where O* omits polynomial factors, against O*(2^n) for the fastest known classical algorithm; the abstract reports the same approach for vertex ordering problems in O*(1.817^n), which the Zoo sets against O*(2^n) classically, and for graph bandwidth in O*(2.946^n), set against O*(4.383^n) classically, and reports similar ideas for the travelling salesman problem and minimum set cover in O*(1.728^n), with minimum set cover stated by the Zoo as O(poly(m,n) 1.728^n) against O(nm2^n) classically. The two sources differ on one figure: where the abstract writes 1.728^n for the travelling salesman problem and minimum set cover together, the Zoo writes 1.729^n for traveling salesman and feedback arc set against O*(2^n) classically and gives minimum set cover a figure of its own.
Secondary source for the speedup class: Quantum Algorithm Zoo — "Quantum Dynamic Programming for path-in-the-hypercube"
Section it is filed under: Optimization, Numerics, and Machine Learning
Complexity basis: Abstract of arXiv:1807.05209 (TeX math delimiters removed, exponents left in caret form): "We give a quantum algorithm that solves path in the hypercube in time O^*(1.817^n). The technique combines Grover's search with computing a partial dynamic programming table. We use this approach to solve a variety of vertex ordering problems on graphs in the same time O^*(1.817^n), and graph bandwidth in time O^*(2.946^n). Then we use similar ideas to solve the travelling salesman problem and minimum set cover in time O^*(1.728^n)." The classical baselines and the per-problem contrasts are from the Quantum Algorithm Zoo entry "Quantum Dynamic Programming for path-in-the-hypercube" (LaTeX rendered into Unicode: math delimiters removed, the mathrm markup around poly dropped, spacing inside the math closed up): "a quantum algorithm can solve path-in-the-hypercube in time O^*(1.817^n), where the notation O^* indicates that polynomial factors are being omitted. The fastest known classical algorithm for this problem runs in time O^*(2^n)", and "vertex ordering problems in O^*(1.817^n) vs. O^*(2^n) classically, graph bandwidth in O^*(2.946^n) vs. O^*(4.383^n) classically, traveling salesman and feedback arc set in O^*(1.729^n) vs. O^*(2^n) classically, and minimum set cover in O(poly(m,n) 1.728^n) vs. O(nm2^n) classically." The 1.728 / 1.729 difference is recorded as both sources read: the abstract pairs 1.728^n with the travelling salesman problem and minimum set cover together, while the Zoo gives 1.728^n to minimum set cover alone and 1.729^n to traveling salesman and feedback arc set. Neither reading was reconciled here.
Circuit: Not supplied

Source

Quantum Speedups for Exponential-Time Dynamic Programming Algorithms ↗

Kind: curated reference
Reviewed by: Leona Quantum curation pass
License: Citation metadata only; source publication terms apply