Related papers: A Constant Measurement Quantum Algorithm for Graph Connectivity

A Constant Measurement Quantum Algorithm for Graph Connectivity

URL: http://arxiv.org/abs/2411.15015v1
Date: Fri, 22 Nov 2024 15:44:00 GMT
Title: A Constant Measurement Quantum Algorithm for Graph Connectivity
Authors: Maximilian Balthasar Mansky, Chonfai Kam, Claudia Linnhoff-Popien,
Abstract summary: We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. The algorithm exhibits a state decay that can be remedied with ancilla qubits.
Score: 4.900041609957432
License:
Abstract: We introduce a novel quantum algorithm for determining graph connectedness using a constant number of measurements. The algorithm can be extended to find connected components with a linear number of measurements. It relies on non-unitary abelian gates taken from ZX calculus. Due to the fusion rule, the two-qubit gates correspond to a large single action on the qubits. The algorithm is general and can handle any undirected graph, including those with repeated edges and self-loops. The depth of the algorithm is variable, depending on the graph, and we derive upper and lower bounds. The algorithm exhibits a state decay that can be remedied with ancilla qubits. We provide a numerical simulation of the algorithm.

Related papers

Quantum Algorithm for Testing Graph Completeness [0.0]
Testing graph completeness is a critical problem in computer science and network theory. We present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE) This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.
arXiv Detail & Related papers (2024-07-29T14:56:25Z)
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)
Full Characterization of the Depth Overhead for Quantum Circuit Compilation with Arbitrary Qubit Connectivity Constraint [6.799314463590596]
In some physical implementations of quantum computers, 2-qubit operations can be applied only on certain pairs of qubits. In this paper, we fully characterize the depth overhead by the routing number of the underlying constraint graph.
arXiv Detail & Related papers (2024-02-04T08:29:41Z)
Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
arXiv Detail & Related papers (2023-11-19T00:06:11Z)
A simple quantum algorithm to efficiently prepare sparse states [0.0]
We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. This is competitive with the best known algorithms for sparse state preparation.
arXiv Detail & Related papers (2023-10-30T07:05:15Z)
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)
Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
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.
arXiv Detail & Related papers (2021-11-19T12:35:26Z)
On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
arXiv Detail & Related papers (2021-06-11T09:43:09Z)
An Online Algorithm for Maximum-Likelihood Quantum State Tomography [6.261444979025642]
We propose the first online algorithm for maximum-likelihood quantum state tomography. The expected numerical error of the algorithm is $O(sqrt ( 1 / T ) D log D )$, where $T$ denotes the number of iterations.
arXiv Detail & Related papers (2020-12-31T08:21:50Z)
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)
Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
arXiv Detail & Related papers (2020-02-24T17:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.