Investigating the Chinese postman problem on a quantum annealer

Ilaria Siloi, Virginia Carnevali, Bibek Pokharel, Marco Fornari, Rosa Di Felice

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


The recent availability of quantum annealers has fueled a new area of information technology where such devices are applied to address practically motivated and computationally difficult problems with hardware that exploits quantum mechanical phenomena. D-Wave annealers are promising platforms to solve these problems in the form of quadratic unconstrained binary optimization. Here we provide a formulation of the Chinese postman problem that can be used as a tool for probing the local connectivity of graphs and networks. We treat the problem classically with a tabu algorithm and simulated annealing, and using a D-Wave device. The efficiency of quantum annealing with respect to the simulated annealing has been demonstrated using the optimal time to solution metric. We systematically analyze computational parameters associated with the specific hardware. Our results clarify how the interplay between the embedding due to limited connectivity of the Chimera graph, the definition of logical qubits, and the role of spin-reversal controls the probability of reaching the expected solution.

Original languageEnglish
Article number3
JournalQuantum Machine Intelligence
Issue number1
StatePublished - Jun 2021


  • D-Wave
  • QUBO
  • Quantum annealing
  • Routing problems


Dive into the research topics of 'Investigating the Chinese postman problem on a quantum annealer'. Together they form a unique fingerprint.

Cite this