Related papers: A quantum parallel Markov chain Monte Carlo

A quantum parallel Markov chain Monte Carlo

URL: http://arxiv.org/abs/2112.00212v4
Date: Sun, 19 Mar 2023 22:06:58 GMT
Title: A quantum parallel Markov chain Monte Carlo
Authors: Andrew J. Holbrook
Abstract summary: We use the Gumbel-max trick to turn the generalized accept-reject step into a discrete optimization problem. We embed target density evaluations within a well-known extension of Grover's quantum search algorithm.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose a novel hybrid quantum computing strategy for parallel MCMC algorithms that generate multiple proposals at each step. This strategy makes the rate-limiting step within parallel MCMC amenable to quantum parallelization by using the Gumbel-max trick to turn the generalized accept-reject step into a discrete optimization problem. When combined with new insights from the parallel MCMC literature, such an approach allows us to embed target density evaluations within a well-known extension of Grover's quantum search algorithm. Letting $P$ denote the number of proposals in a single MCMC iteration, the combined strategy reduces the number of target evaluations required from $\mathcal{O}(P)$ to $\mathcal{O}(P^{1/2})$. In the following, we review the rudiments of quantum computing, quantum search and the Gumbel-max trick in order to elucidate their combination for as wide a readership as possible.

Related papers

Quantum-Efficient Kernel Target Alignment [0.0]
We investigate KTA-trained quantum embedding kernels and employ a low-rank matrix approximation, the Nystr"om method, to reduce the quantum circuit executions needed to construct the Kernel Matrix. We empirically evaluate the performance of our approach across various datasets, focusing on the accuracy of the resulting SVM and the reduction in quantum circuit executions.
arXiv Detail & Related papers (2025-02-12T09:08:51Z)
A Quantum Approximate Optimization Method For Finding Hadamard Matrices [0.0]
We propose a novel qubit-efficient method by implementing the Hadamard matrix searching algorithm on a gate-based quantum computer. We present the formulation of the method, construction of corresponding quantum circuits, and experiment results in both a quantum simulator and a real gate-based quantum computer.
arXiv Detail & Related papers (2024-08-15T06:25:50Z)
Quantum Speedups for Multiproposal MCMC [8.580097282861725]
We present a new, faster quantum multiproposal MCMC strategy, QPMCMC2. QPMCMC2 requires only $mathcalO(P)$ target evaluations and $mathcalO(log P)$ qubits when computing over a large number of proposals $P$. We demonstrate this flexibility by applying QPMCMC2 to novel Ising-type models built on bacterial evolutionary networks.
arXiv Detail & Related papers (2023-12-03T14:05:08Z)
A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria. This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
arXiv Detail & Related papers (2023-11-17T20:38:38Z)
QAOA-MC: Markov chain Monte Carlo enhanced by Quantum Alternating Operator Ansatz [0.6181093777643575]
We propose the use of Quantum Alternating Operator Ansatz (QAOA) for quantum-enhanced Monte Carlo. This work represents an important step toward realizing practical quantum advantage with currently available quantum computers.
arXiv Detail & Related papers (2023-05-15T16:47:31Z)
A self-consistent field approach for the variational quantum eigensolver: orbital optimization goes adaptive [52.77024349608834]
We present a self consistent field approach (SCF) within the Adaptive Derivative-Assembled Problem-Assembled Ansatz Variational Eigensolver (ADAPTVQE) This framework is used for efficient quantum simulations of chemical systems on nearterm quantum computers.
arXiv Detail & Related papers (2022-12-21T23:15:17Z)
Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z)
Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
arXiv Detail & Related papers (2022-09-01T17:08:41Z)
Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z)
Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z)

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