Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Towards Shortest Paths via Adiabatic Quantum Computing

: Bauckhage, Christian; Brito, Eduardo; Cvejoski, Kostadin; Ojeda, César; Schücker, Jannis; Sifa, Rafet

Postprint urn:nbn:de:0011-n-5523210 (1.7 MByte PDF)
MD5 Fingerprint: c0de26ff4aecbe67800dce3c83d1af2c
Created on: 28.8.2019

14th International Workshop on Mining and Learning with Graphs, MLG 2018. Online resource : Held in conjunction with KDD 2018, August 20, 2018, London
London, 2018
6 pp.
International Workshop on Mining and Learning with Graphs (MLG) <14, 2018, London>
International Conference on Knowledge Discovery and Data Mining (KDD) <24, 2018, London>
Conference Paper, Electronic Publication
Fraunhofer IAIS ()
shortest path finding; adiabatic quantum computing

Since first working quantum computers are now available, accelerated developments of this technology may be expected. This will likely impact graph- or network analysis because quantum computers promise fast solutions for many problems in these areas. In this paper, we explore the use of adiabatic quantum computing in finding shortest paths. We devise an Ising energy minimization formulation for this task and discuss how to set up a system of quantum bits to find minimum energy states of the model. In simulation experiments, we numerically solve the corresponding Schrödinger equations and observe our approach to work well. This evidences that shortest path computation can at least be assisted by quantum computers.