Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration

• URL: http://arxiv.org/abs/2303.05640v1
• Date: Fri, 10 Mar 2023 01:05:16 GMT
• Title: Quantum Metropolis-Hastings algorithm with the target distribution calculated by quantum Monte Carlo integration
• Authors: Koichi Miyamoto
• Abstract summary: Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $Delta$ compered to classical counterparts. We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference. In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $ell$ scales on $Delta$, the required accuracy $epsilon$ and the standard deviation $sigma$ of $ell$ as $tildeO(sigma/epsilon
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Markov chain Monte Carlo method (MCMC), especially the Metropolis-Hastings (MH) algorithm, is a widely used technique for sampling from a target probability distribution $P$ on a state space $\Omega$ and applied to various problems such as estimation of parameters in statistical models in the Bayesian approach. Quantum algorithms for MCMC have been proposed, yielding the quadratic speedup with respect to the spectral gap $\Delta$ compered to classical counterparts. In this paper, we consider the quantum version of the MH algorithm in the case that calculating $P$ is costly because the log-likelihood $L$ for a state $x\in\Omega$ is obtained via computing the sum of many terms $\frac{1}{M}\sum_{i=0}^{M-1} \ell(i,x)$. We propose calculating $L$ by quantum Monte Carlo integration and combine it with the existing method called quantum simulated annealing (QSA) to generate the quantum state that encodes $P$ in amplitudes. We consider not only state generation but also finding a credible interval for a parameter, a common task in Bayesian inference. In the proposed method for credible interval calculation, the number of queries to the quantum circuit to compute $\ell$ scales on $\Delta$, the required accuracy $\epsilon$ and the standard deviation $\sigma$ of $\ell$ as $\tilde{O}(\sigma/\epsilon^2\Delta^{3/2})$, in contrast to $\tilde{O}(M/\epsilon\Delta^{1/2})$ for QSA with $L$ calculated exactly. Therefore, the proposed method is advantageous if $\sigma$ scales on $M$ sublinearly. As one such example, we consider parameter estimation in a gravitational wave experiment, where $\sigma=O(M^{1/2})$.

Related papers

• Optimized Quantum Simulation Algorithms for Scalar Quantum Field Theories [0.3394351835510634]
  We provide practical simulation methods for scalar field theories on a quantum computer that yield improveds. We implement our approach using a series of different fault-tolerant simulation algorithms for Hamiltonians. We find in both cases that the bounds suggest physically meaningful simulations can be performed using on the order of $4times 106$ physical qubits and $1012$ $T$-gates.
  arXiv  Detail & Related papers  (2024-07-18T18:00:01Z)
• Dividing quantum circuits for time evolution of stochastic processes by orthogonal series density estimation [0.0]
  Quantum Monte Carlo integration (QMCI) is a quantum algorithm to estimate expectations of random variables. In this paper, we propose a method to divide $U_X(t)$ based on orthogonal series density estimation. Our method achieves the circuit depth and total query complexity scaling as $O(sqrtN)$ and $O(N3/2)$, respectively.
  arXiv  Detail & Related papers  (2024-06-04T01:50:21Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  We give a quantum algorithm for solving the ground states of a class of Hamiltonians. The mechanism of the exponential speedup that appeared in our algorithm comes from dissipation in open quantum systems.
  arXiv  Detail & Related papers  (2024-01-25T05:01:02Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants [8.453228628258778]
  We develop quantum algorithms for sampling logconcave distributions and for estimating their normalizing constants. We exploit quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/epsilon1-o(1)$ quantum lower bound for estimating normalizing constants.
  arXiv  Detail & Related papers  (2022-10-12T19:10:43Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

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.