Graphs on Qubits: Demonstrating Three Graph Algorithms on Quantum Computers

Graph algorithms are at the center of database optimization and data management, and countless optimization algorithms can be expressed as graph algorithms. Additionally, graph algorithms form the foundational mechanism to query graph databases. In this work, we demonstrate how three central graph problems, all-pairs shortest path, graph isomorphism, and community detection, can be solved using quantum annealers. The problem formulation for the all-pairs shortest path problem is new. The work is implemented in a demonstration system, which shows that the selected graph algorithms have natural quantum computational formulations and that running small but realistic workloads on quantum annealers is feasible.

Conference paper

In VLDB 2024 Workshop The Second International Workshop on Quantum Data Science and Management (QDSM’24)