Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 37 min ago
Peer-reviewedCC BY 4.0Quantum

Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

  • Ugo Nzongani1,2
  • Dylan Laplace Mermoud3
  • Giuseppe Di Molfetta1,4
  • Andrea Simonetto2,5
5 affiliations
  1. 1Aix-Marseille Université, CNRS, LIS, 13288 Marseille, France
  2. 2UMA, ENSTA, Institut Polytechnique de Paris, Palaiseau, France
  3. 3Sorbonne Université, CNRS, LIP6, F-75005, Paris, France
  4. 4Institut Universitaire de France, Paris, France
  5. 5CEDRIC, Conservatoire National des Arts et Métiers, 75003 Paris, France
Open at sourcePDFDOICite

Abstract

We introduce SamBa-GQW, a novel quantum algorithm for solving 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 problems, namely MaxCut, maximum independent set, portfolio optimization, and higher-order polynomial problems such as LABS, MAX- k -SAT and a quartic reformulation of the travelling salesperson problem. We empirically demonstrate that SamBa-GQW finds high quality approximate solutions on problems up to a size of n = 30 qubits by only sampling poly( n ) states among 2 n possible decisions. Furthermore, SamBa-GQW compares in par with classically optimized variational approaches, such as the variational guided quantum walk and QAOA (the latter when run on deep circuits). This places Samba-GQW as a promising heuristic to tackle combinatorial problems beyond the NISQ regime.

Related

  1. Reconstructing fluid velocity fields from sparse sensors using a variational quantum algorithm
    Nhat-Quang Nguyen, Mohammad Mehedi Hasan Akash, Kourosh Shoele +2
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Measurement-Efficient Differentiable Quantum Architecture Search for Combinatorial Optimization
    Lukas Theißinger, Thore Gerlach, Christian Bauckhage
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  3. Quantum-echo Markov process for combinatorial optimization
    Tatsuhiko Shirai
    arXivPreprintCC BY 4.0Full textCondensed matterQuantum physics & quantum informationarXiv
  4. A Variational Quantum Algorithm for Multi-Skill Project Scheduling
    Raul Martinez, Miguel Sánchez-Beato, Matilde Osa +2
    arXivPreprintarXiv licenceFull textOptimisation & controlQuantum physics & quantum informationarXiv
  5. Super-Quadratic Quantum Speedups for Combinatorial Optimization via Tilted Walks
    Guneykan Ozgul, Shouvanik Chakrabarti
    arXivPreprintarXiv licenceFull textOptimisation & controlQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@article{nzongani2026sampledbased,
  title = {{Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization}},
  author = {Ugo Nzongani and Dylan Laplace Mermoud and Giuseppe Di Molfetta and Andrea Simonetto},
  journal = {Quantum},
  year = {2026},
  month = oct,
  doi = {10.22331/q-2026-10-13-2234},
  url = {https://quantum-journal.org/papers/q-2026-10-13-2234/},
  note = {CC BY 4.0},
}
RIS
TY  - JOUR
TI  - Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization
AU  - Ugo Nzongani
AU  - Dylan Laplace Mermoud
AU  - Giuseppe Di Molfetta
AU  - Andrea Simonetto
PY  - 2026
DA  - 2026/10/13
JO  - Quantum
DO  - 10.22331/q-2026-10-13-2234
UR  - https://quantum-journal.org/papers/q-2026-10-13-2234/
AB  - We introduce SamBa-GQW, a novel quantum algorithm for solving 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 problems, namely MaxCut, maximum independent set, portfolio optimization, and higher-order polynomial problems such as LABS, MAX- k -SAT and a quartic reformulation of the travelling salesperson problem. We empirically demonstrate that SamBa-GQW finds high quality approximate solutions on problems up to a size of n = 30 qubits by only sampling poly( n ) states among 2 n possible decisions. Furthermore, SamBa-GQW compares in par with classically optimized variational approaches, such as the variational guided quantum walk and QAOA (the latter when run on deep circuits). This places Samba-GQW as a promising heuristic to tackle combinatorial problems beyond the NISQ regime.
SN  - 2521-327X
ER  -