14:30
15:30

We introduce Sampled-Based Guided Quantum Walk (SamBa–GQW), a
novel quantum algorithm for approximating solutions of binary
combinatorial optimization problems of arbitrary degree with no use of
any classical optimizer. The algorithm is based on a continuous-time
quantum walk on the solution space represented as a graph. The walker
explores the solution space to find its way to vertices that minimize
the cost function of the optimization problem. The key novelty of our
algorithm is an offline classical sampling protocol that gives
information about the spectrum of the problem Hamiltonian. Then, the
extracted information is used to guide the walker to high quality
solutions via a quantum walk with a time-dependent hopping rate. We
investigate the performance of SamBa–GQW on several quadratic and
higher-order polynomial problems. We empirically demonstrate that
SamBa–GQW finds high quality approximate solutions on problems up to a
size of n=20 qubits by only sampling n^2 states among 2^n possible
decisions.

https://combalgo.labri.fr/pmwiki.php/Groupe/Info-Quantique

Français
On Zoom