Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer
- URL: http://arxiv.org/abs/2104.09503v1
- Date: Sun, 18 Apr 2021 16:15:00 GMT
- Title: Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer
- Authors: Eugenio Cocchi, Edoardo Tignone, Davide Vodola
- Abstract summary: We show that a quantum annealer can be used to solve the NP-complete problem of graph partitioning into subgraphs.
We formulate the problem as a quadratic unconstrained binary optimisation and run it on a D-Wave Advantage quantum annealer.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We demonstrate that a quantum annealer can be used to solve the NP-complete
problem of graph partitioning into subgraphs containing Hamiltonian cycles of
constrained length. We present a method to find a partition of a given directed
graph into Hamiltonian subgraphs with three or more vertices, called vertex
3-cycle cover. We formulate the problem as a quadratic unconstrained binary
optimisation and run it on a D-Wave Advantage quantum annealer. We test our
method on synthetic graphs constructed by adding a number of random edges to a
set of disjoint cycles. We show that the probability of solution is independent
of the cycle length, and a solution is found for graphs up to 4000 vertices and
5200 edges, close to the number of physical working qubits available on the
quantum annealer.
Related papers
- Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
This article presents a novel and succinct algorithmic framework via alternating quantum walks.
It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs.
The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
arXiv Detail & Related papers (2024-07-01T06:09:19Z) - An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem.
We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
arXiv Detail & Related papers (2024-06-11T04:40:05Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.
Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix.
Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
arXiv Detail & Related papers (2024-02-29T09:26:46Z) - Bell pair extraction using graph foliage techniques [0.0]
We are interested in whether multiple pairs can communicate simultaneously across a network.
Quantum networks can be represented with graph states, and producing communication links amounts to performing certain quantum operations on graph states.
arXiv Detail & Related papers (2023-11-25T22:33:29Z) - Comparison among Classical, Probabilistic and Quantum Algorithms for
Hamiltonian Cycle problem [0.0]
Hamiltonian cycle problem (HCP) consists of having a graph G with n nodes and m edges and finding the path that connects each node exactly once.
In this paper we compare some algorithms to solve aHCP, using different models of computations and especially the probabilistic and quantum ones.
arXiv Detail & Related papers (2023-11-18T02:36:10Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing.
The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph.
For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
arXiv Detail & Related papers (2023-02-08T08:17:43Z) - Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
We study Grover's search algorithm focusing on continuous-time quantum walk on graphs.
Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
arXiv Detail & Related papers (2022-07-04T19:33:06Z) - Optimization on Large Interconnected Graphs and Networks Using Adiabatic
Quantum Computation [0.0]
We create an adiabatic quantum computing algorithm that solves the shortest path between any two vertices on an undirected graph with at most 3V qubits.
The objective of this paper is to demonstrate the fact that it is possible to model large graphs on an adiabatic quantum computer using the maximum number of qubits available.
arXiv Detail & Related papers (2022-02-06T13:47:31Z) - Solving correlation clustering with QAOA and a Rydberg qudit system: a
full-stack approach [94.37521840642141]
We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits.
Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering.
We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
arXiv Detail & Related papers (2021-06-22T11:07:38Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$.
We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
arXiv Detail & Related papers (2020-05-13T14:53:36Z) - Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph.
It can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph.
We present a number of numerical simulations supporting this hypothesis.
arXiv Detail & Related papers (2020-02-26T00:10:38Z)
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.