Computing Graph Edit Distance with Algorithms on Quantum Devices

Abstract

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.

arXiv comment12 pages, 9 figures. Comments are welcome

References in corpus (26)

• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• The theory of variational hybrid quantum-classical algorithms
• Adiabatic Quantum Computing
• The power of quantum neural networks
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Perspectives of quantum annealing: Methods and implementations
• Quantum Natural Gradient
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Quantum Computer Systems for Scientific Discovery
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Benchmarking the Quantum Approximate Optimization Algorithm
• Power of Pausing: Advancing Understanding of Thermalization in Experimental Quantum Annealers
• Quantum hardware simulating four-dimensional inelastic neutron scattering
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Simultaneous Perturbation Stochastic Approximation of the Quantum Fisher Information
• Universal discriminative quantum neural networks
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Improved success probability with greater circuit depth for the quantum approximate optimization algorithm
• Dimensional Expressivity Analysis of Parametric Quantum Circuits
• Improving quantum annealing of the ferromagnetic $p$-spin model through pausing
• Why and when is pausing beneficial in quantum annealing?
• Bipartite unitary gates and billiard dynamics in the Weyl chamber