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.
翻译:远程测量为机器学习和模式识别中许多流行的算法提供了基础。 视算法所使用数据的类型,可以使用不同的距离概念。 对于图形形状数据,一个重要的概念是“图形编辑距离”(GED),它测量两个图形之间在使两个图形具有相同操作所需的差异程度。由于计算GED的复杂性与NP- 硬问题相同,因此考虑近似的解决办法是合理的。 在本文中,我们对GED问题提出了一个QUB的配方。这使我们能够实施两种不同的方法,即量子整射和变异量算法,分别运行于目前可用的两种量子硬件:量子射线和门基量子计算机。考虑到目前噪音的中间级量计算机的状况,我们的研究以其性能的证明测试为基础。