Gaussian Amplitude Amplification for Quantum Pathfinding
- URL: http://arxiv.org/abs/2112.08167v3
- Date: Fri, 27 May 2022 12:45:53 GMT
- Title: Gaussian Amplitude Amplification for Quantum Pathfinding
- Authors: Daniel Koch, Massimiliano Cutugno, Samuel Karlson, Saahil Patel, Laura
Wessing, Paul M. Alsing
- Abstract summary: We focus on a geometry of sequentially connected bipartite graphs, which naturally gives rise to solution spaces describable by gaussian distributions.
We demonstrate how an oracle which encodes these distributions can be used to solve for the optimal path via amplitude amplification.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study an oracle operation, along with its circuit design, which combined
with the Grover diffusion operator boosts the probability of finding minimum or
maximum solutions on a weighted directed graph. We focus on a geometry of
sequentially connected bipartite graphs, which naturally gives rise to solution
spaces describable by gaussian distributions. We then demonstrate how an oracle
which encodes these distributions can be used to solve for the optimal path via
amplitude amplification. And finally, we explore the degree to which this
algorithm is capable of solving cases which are generated using randomized
weights, as well as a theoretical application for solving the Traveling
Salesman problem.
Related papers
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal.
Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
arXiv Detail & Related papers (2024-09-07T06:37:23Z) - Quantum Speedup of the Dispersion and Codebook Design Problems [6.735173690339397]
Dispersion problems are optimization problems classified as NP-hard.
We propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm.
arXiv Detail & Related papers (2024-06-11T12:00:50Z) - Distributed Markov Chain Monte Carlo Sampling based on the Alternating
Direction Method of Multipliers [143.6249073384419]
In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers.
We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art.
In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
arXiv Detail & Related papers (2024-01-29T02:08:40Z) - Connection between single-layer Quantum Approximate Optimization
Algorithm interferometry and thermal distributions sampling [0.0]
We extend the theoretical derivation of the amplitudes of the eigenstates, and the Boltzmann distributions generated by single-layer QAOA.
We also review the implications that this behavior has from both a practical and fundamental perspective.
arXiv Detail & Related papers (2023-10-13T15:06:58Z) - 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) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average.
Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
arXiv Detail & Related papers (2023-05-22T17:43:34Z) - Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem.
We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
arXiv Detail & Related papers (2023-02-13T19:57:17Z) - Variational Amplitude Amplification for Solving QUBO Problems [0.0]
This study focuses on QUBO (quadratic unconstrained binary optimization) problems, which are well-suited for qubit superposition states.
We demonstrate circuit designs which encode QUBOs as cost oracle' operations $U_textrmC$, which when combined with the standard Grover diffusion operator $U_textrms$ lead to high probabilities of measurement for states corresponding to the optimal and near optimal solutions.
arXiv Detail & Related papers (2023-01-31T14:33:40Z) - Capturing Graphs with Hypo-Elliptic Diffusions [7.704064306361941]
We show that the distribution of random walks evolves according to a diffusion equation defined using the graph Laplacian.
This results in a novel tensor-valued graph operator, which we call the hypo-elliptic graph Laplacian.
We show that this method competes with graph transformers on datasets requiring long-range reasoning but scales only linearly in the number of edges.
arXiv Detail & Related papers (2022-05-27T16:47:34Z) - Pathwise Conditioning of Gaussian Processes [72.61885354624604]
Conventional approaches for simulating Gaussian process posteriors view samples as draws from marginal distributions of process values at finite sets of input locations.
This distribution-centric characterization leads to generative strategies that scale cubically in the size of the desired random vector.
We show how this pathwise interpretation of conditioning gives rise to a general family of approximations that lend themselves to efficiently sampling Gaussian process posteriors.
arXiv Detail & Related papers (2020-11-08T17:09:37Z)
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.