Related papers: Quantum Algorithm for Path-Edge Sampling

Quantum Algorithm for Path-Edge Sampling

URL: http://arxiv.org/abs/2303.03319v1
Date: Mon, 6 Mar 2023 17:45:12 GMT
Title: Quantum Algorithm for Path-Edge Sampling
Authors: Stacey Jeffery, Shelby Kimmel, Alvaro Piedrafita
Abstract summary: We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases.
Score: 0.9990687944474739
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix, and show that this can be done in query complexity that is asymptotically the same, up to log factors, as the query complexity of detecting a path between s and t. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases. Our main technical contribution is an algorithm for generating a quantum state that is proportional to the positive witness vector of a span program.

Related papers

A quantum algorithm for advection-diffusion equation by a probabilistic imaginary-time evolution operator [0.0]
We propose a quantum algorithm for solving the linear advection-diffusion equation by employing a new approximate probabilistic imaginary-time evolution (PITE) operator. We construct the explicit quantum circuit for realizing the imaginary-time evolution of the Hamiltonian coming from the advection-diffusion equation. Our algorithm gives comparable result to the Harrow-Hassidim-Lloyd (HHL) algorithm with similar gate complexity, while we need much less ancillary qubits.
arXiv Detail & Related papers (2024-09-27T08:56:21Z)
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)
Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
A quantum-based feature selection algorithm for the multi-classification problem, namely, QReliefF, is proposed. Our algorithm is superior in finding the nearest neighbor, reducing the complexity from O(M) to O(sqrt(M)).
arXiv Detail & Related papers (2023-10-01T03:57:13Z)
On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards. For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
arXiv Detail & Related papers (2023-08-23T08:38:53Z)
Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
arXiv Detail & Related papers (2023-06-21T17:03:22Z)
Locality-aware Qubit Routing for the Grid Architecture [1.4459640831465588]
We introduce a locality-aware qubit routing algorithm based on a graph theoretic framework. Our algorithm is designed for the grid and certain "grid-like" architectures.
arXiv Detail & Related papers (2022-03-21T20:46:39Z)
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)
Quantum Algorithms for Prediction Based on Ridge Regression [0.7612218105739107]
We propose a quantum algorithm based on ridge regression model, which get the optimal fitting parameters. The proposed algorithm has a wide range of application and the proposed algorithm can be used as a subroutine of other quantum algorithms.
arXiv Detail & Related papers (2021-04-27T11:03:52Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
arXiv Detail & Related papers (2020-07-01T18:43:32Z)
Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs.
arXiv Detail & Related papers (2020-06-15T13:40:07Z)
A Heuristic Based on Randomized Greedy Algorithms for the Clustered Shortest-Path Tree Problem [2.099922236065961]
This paper introduces a new algorithm that combines the major features of RGAs and Shortest Path Tree Algorithm (SPTA) to deal with the Clustered Shortest-Path Tree Problem (CluSPT) To evaluate the performance of the proposed algorithm, Euclidean benchmarks are selected.
arXiv Detail & Related papers (2020-05-05T08:34:58Z)

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