Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance
- URL: http://arxiv.org/abs/2111.10183v1
- Date: Fri, 19 Nov 2021 12:35:26 GMT
- Title: Benchmarking Small-Scale Quantum Devices on Computing Graph Edit
Distance
- Authors: Massimiliano Incudini, Fabio Tarocco, Riccardo Mengoni, Alessandra Di
Pierro, and Antonio Mandarino
- Abstract summary: Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical.
In this paper we present a comparative study of two quantum approaches to computing GED.
- Score: 52.77024349608834
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- 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 comparative study of two quantum
approaches to computing GED: quantum annealing and variational quantum
algorithms, which refer to the two types of quantum hardware currently
available, namely 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 the performance of
these quantum algorithms.
Related papers
- The Algorithm for Solving Quantum Linear Systems of Equations With Coherent Superposition and Its Extended Applications [8.8400072344375]
We propose two quantum algorithms for solving quantum linear systems of equations with coherent superposition.
The two quantum algorithms can both compute the rank and general solution by one measurement.
Our analysis indicates that the proposed algorithms are mainly suitable for conducting attacks against lightweight symmetric ciphers.
arXiv Detail & Related papers (2024-05-11T03:03:14Z) - Scalable Quantum Algorithms for Noisy Quantum Computers [0.0]
This thesis develops two main techniques to reduce the quantum computational resource requirements.
The aim is to scale up application sizes on current quantum processors.
While the main focus of application for our algorithms is the simulation of quantum systems, the developed subroutines can further be utilized in the fields of optimization or machine learning.
arXiv Detail & Related papers (2024-03-01T19:36:35Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering [3.187381965457262]
We develop a quantum algorithm that tests for and quantifies the separability of a general bipartite state by using the quantum steering effect.
Our findings provide a meaningful connection between steering, entanglement, quantum algorithms, and quantum computational complexity theory.
arXiv Detail & Related papers (2023-03-14T13:55:06Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages.
The computation can then be implemented using a series of non-Pauli measurements on this graph state.
arXiv Detail & Related papers (2022-09-15T14:52:31Z) - Machine learning applications for noisy intermediate-scale quantum
computers [0.0]
We develop and study three quantum machine learning applications suitable for NISQ computers.
These algorithms are variational in nature and use parameterised quantum circuits (PQCs) as the underlying quantum machine learning model.
We propose a variational algorithm in the area of approximate quantum cloning, where the data becomes quantum in nature.
arXiv Detail & Related papers (2022-05-19T09:26:57Z) - From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions.
For its practicability and wide-applicability, we give a brief review of typical graph learning techniques.
We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
arXiv Detail & Related papers (2022-02-19T02:56:47Z) - Quantum Computer Benchmarking via Quantum Algorithms [0.0]
We present a framework that utilizes quantum algorithms, an architecture aware quantum noise model and an ideal simulator to benchmark quantum computers.
The benchmark metrics highlight the difference between the quantum computer evolution and the simulated noisy and ideal quantum evolutions.
arXiv Detail & Related papers (2021-12-17T11:54:05Z) - Electronic structure with direct diagonalization on a D-Wave quantum
annealer [62.997667081978825]
This work implements the general Quantum Annealer Eigensolver (QAE) algorithm to solve the molecular electronic Hamiltonian eigenvalue-eigenvector problem on a D-Wave 2000Q quantum annealer.
We demonstrate the use of D-Wave hardware for obtaining ground and electronically excited states across a variety of small molecular systems.
arXiv Detail & Related papers (2020-09-02T22:46:47Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.