Optimization on Large Interconnected Graphs and Networks Using Adiabatic Quantum Computation

• URL: http://arxiv.org/abs/2202.02774v2
• Date: Wed, 24 Aug 2022 15:57:59 GMT
• Title: Optimization on Large Interconnected Graphs and Networks Using Adiabatic Quantum Computation
• Authors: Venkat Padmasola and Rupak Chatterjee
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we demonstrate that it is possible to create an adiabatic quantum computing algorithm that solves the shortest path between any two vertices on an undirected graph with at most 3V qubits, where V is the number of vertices of the graph. We do so without relying on any classical algorithms, aside from creating a (V x V) adjacency matrix. 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 and random graph generators such as the Barabasi-Albert and the Erdos-Renyi methods which can scale based on a power law.

Related papers

• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies [0.9500919522633157]
  We study the quantum dynamics of the encoding scheme proposed in [Nguyen et al., PRX Quantum 4, 010316 (2023) We look at minimum gap scaling with system size along adiabatic protocols. We observe such localization and its effect on the success probability of finding the correct solution.
  arXiv  Detail & Related papers  (2024-11-07T12:10:01Z)
• 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)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs.
  arXiv  Detail & Related papers  (2023-07-30T05:14:19Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• 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)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  We propose the Neighbor2Seq to transform the hierarchical neighborhood of each node into a sequence. We evaluate our method on a massive graph with more than 111 million nodes and 1.6 billion edges. Results show that our proposed method is scalable to massive graphs and achieves superior performance across massive and medium-scale graphs.
  arXiv  Detail & Related papers  (2022-02-07T16:38:36Z)
• Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm and Application to 3D Multi-Shape Analysis [69.08838724594584]
  Finding shortest paths in a graph is relevant for numerous problems in computer vision and graphics. We introduce the novel graph-theoretic concept of a shortest path in a graph with matrix-valued edges.
  arXiv  Detail & Related papers  (2021-12-08T08:23:37Z)
• Graph Partitioning into Hamiltonian Subgraphs on a Quantum Annealer [0.0]
  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.
  arXiv  Detail & Related papers  (2021-04-18T16:15:00Z)
• Laplacian Eigenmaps with variational circuits: a quantum embedding of graph data [0.0]
  We propose a method to compute a Laplacian Eigenmap using a quantum variational circuit. Tests on 32 nodes graph with a quantum simulator show that we can achieve similar performances as the classical laplacian eigenmap algorithm.
  arXiv  Detail & Related papers  (2020-11-10T14:51:25Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.