# Computing Graph Edit Distance with Algorithms on Quantum Devices

arXiv: https://arxiv.org/abs/2111.10183 · HTML: https://mlsanity.com/paper/2111.10183/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 86 references that are in the map.
- First posted on arXiv 19 Nov 2021.

## Builds on (most cited first, 10 of 10)

- [The power of quantum neural networks](https://mlsanity.com/paper/2011.00027/) (2020)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Quantum Natural Gradient](https://mlsanity.com/paper/1909.02108/) (2019)
- [Graph Isomorphism in Quasipolynomial Time](https://mlsanity.com/paper/1512.03547/) (2015)
- [Optimizing quantum heuristics with meta-learning](https://mlsanity.com/paper/1908.03185/) (2019)
- [Universal discriminative quantum neural networks](https://mlsanity.com/paper/1805.08654/) (2018)
- [Control of automated guided vehicles without collision by quantum annealer and digital devices](https://mlsanity.com/paper/1812.01532/) (2018)
- [Learning the noise fingerprint of quantum devices](https://mlsanity.com/paper/2109.11405/) (2021)
- [Circuit Transformations for Quantum Architectures](https://mlsanity.com/paper/1902.09102/) (2019)
- [Facial Expression Recognition on a Quantum Computer](https://mlsanity.com/paper/2102.04823/) (2021)

## Abstract (arXiv)

Distance measures provide the foundation for many popular algorithms in Machine Learning and Pattern Recognition. Different notions of distance can be used depending on the types of the data the algorithm is working on. For graph-shaped data, an important notion is the Graph Edit Distance (GED) that measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. As the complexity of computing GED is the same as NP-hard problems, it is reasonable to consider approximate solutions. In this paper we present a QUBO formulation of the GED problem. This allows us to implement two different approaches, namely quantum annealing and variational quantum algorithms that run on the two types of quantum hardware currently available: quantum annealer and gate-based quantum computer, respectively. Considering the current state of noisy intermediate-scale quantum computers, we base our study on proof-of-principle tests of their performance.