Title: Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions
We present quantum algorithms for sampling from possibly non-logconcave probability distributions expressed as 𝜋(𝑥)∝exp(−𝛽𝑓(𝑥)) as well as quantum algorithms for estimating the partition function for such distributions. We also incorporate a stochastic gradient oracle that implements the quantum walk operators inexactly by only using mini-batch gradients when 𝑓 can be written as a finite sum. One challenge of quantizing the resulting Markov chains is that they do not satisfy the detailed balance condition in general. Consequently, the mixing time of the algorithm cannot be expressed in terms of the spectral gap of the transition density matrix, making the quantum algorithms nontrivial to analyze. We overcame these challenges by first building a reference reversible Markov chain that converges to the target distribution, then controlling the discrepancy between our algorithm’s output and the target distribution by using the reference Markov chain as a bridge to establish the total complexity. Our quantum algorithms exhibit polynomial speedups in terms of dimension or precision dependencies when compared to best-known classical algorithms under similar assumptions.  more » « less
Award ID(s):
2111221
PAR ID:
10533592
Author(s) / Creator(s):
; ; ;
Publisher / Repository:
Proceedings of the 41st International Conference on Machine Learning
Date Published:
Volume:
235
ISSN:
1938-7228
Page Range / eLocation ID:
38953-38982
Subject(s) / Keyword(s):
Sponsoring Org:
National Science Foundation
More Like this
  1. Markov chain Monte Carlo algorithms have important applications in counting problems and in machine learning problems, settings that involve estimating quantities that are difficult to compute exactly. How much can quantum computers speed up classical Markov chain algorithms? In this work we consider the problem of speeding up simulated annealing algorithms, where the stationary distributions of the Markov chains are Gibbs distributions at temperatures specified according to an annealing schedule. We construct a quantum algorithm that both adaptively constructs an annealing schedule and quantum samples at each temperature. Our adaptive annealing schedule roughly matches the length of the best classical adaptive annealing schedules and improves on nonadaptive temperature schedules by roughly a quadratic factor. Our dependence on the Markov chain gap matches other quantum algorithms and is quadratically better than what classical Markov chains achieve. Our algorithm is the first to combine both of these quadratic improvements. Like other quantum walk algorithms, it also improves on classical algorithms by producing “qsamples” instead of classical samples. This means preparing quantum states whose amplitudes are the square roots of the target probability distribution. In constructing the annealing schedule we make use of amplitude estimation, and we introduce a method for making amplitude estimation nondestructive at almost no additional cost, a result that may have independent interest. Finally we demonstrate how this quantum simulated annealing algorithm can be applied to the problems of estimating partition functions and Bayesian inference. 
    more » « less
  2. We show that the stationary distribution of a finite Markov chain can be expressed as the sum of certain normal distributions. These normal distributions are associated to planar graphs consisting of a straight line with attached loops. The loops touch only at one vertex either of the straight line or of another attached loop. Our analysis is based on our previous work, which derives the stationary distribution of a finite Markov chain using semaphore codes on the Karnofsky–Rhodes and McCammond expansion of the right Cayley graph of the finite semigroup underlying the Markov chain. 
    more » « less
  3. Abstract Markov chain Monte Carlo (MCMC) methods are a family of algorithms designed to approximate probability distributions that are otherwise intractable to sample from directly. However, as the dimensionality and complexity of the target distribution increase, the convergence of these methods can slow considerably, demanding substantial computational resources. In this context, quantum computing emerges as a promising framework to address this limitation, with different quantum circuit constructions serving as quantum MCMC methods. In this work, we present a quantum circuit based on the discrete quantum walk (DQW) algorithm that implements the algorithmic steps of the Metropolis–Hastings method, encoding the target distribution in a position quantum register. The circuit incorporates auxiliary registers to compute and discretize the acceptance probability, and uses controlled operations to modulate the walker’s evolution accordingly. Simulation results show that the marginal probability distribution encoded in the position register converges asymptotically toward the discretized target distribution for both single and multimodal distributions. We further analyze the effect of circuit parameters on convergence behavior and approximation quality, refining the construction by enabling the evaluation of multiple candidate moves per iteration, therefore reducing the number of iterations required for convergence within our implementation. Finally, we provide a qualitative comparison of our approach with related quantum MCMC methods, namely Szegedy’s quantum walk and QAOA, and discuss structural differences as well as the potential incorporation of adaptive proposal techniques within the proposed circuit framework. 
    more » « less
  4. Marc'Aurelio Ranzato, Alina Beygelzimer (Ed.)
    Implementations of the exponential mechanism in differential privacy often require sampling from intractable distributions. When approximate procedures like Markov chain Monte Carlo (MCMC) are used, the end result incurs costs to both privacy and accuracy. Existing work has examined these effects asymptotically, but implementable finite sample results are needed in practice so that users can specify privacy budgets in advance and implement samplers with exact privacy guarantees. In this paper, we use tools from ergodic theory and perfect simulation to design exact finite runtime sampling algorithms for the exponential mechanism by introducing an intermediate modified target distribution using artificial atoms. We propose an additional modification of this sampling algorithm that maintains its ǫ-DP guarantee and has improved runtime at the cost of some utility. We then compare these methods in scenarios where we can explicitly calculate a δ cost (as in (ǫ, δ)-DP) incurred when using standard MCMC techniques. Much as there is a well known trade-off between privacy and utility, we demonstrate that there is also a trade-off between privacy guarantees and runtime. 
    more » « less
  5. Dasgupta, Sanjoy; Mandt, Stephan; Li, Yingzhen (Ed.)
    Cyclical MCMC is a novel MCMC framework recently proposed by Zhang et al. (2019) to address the challenge posed by high-dimensional multimodal posterior distributions like those arising in deep learning. The algorithm works by generating a nonhomogeneous Markov chain that tracks -- cyclically in time -- tempered versions of the target distribution. We show in this work that cyclical MCMC converges to the desired limit in settings where the Markov kernels used are fast mixing, and sufficiently long cycles are employed. However in the far more common settings of slow mixing kernels, the algorithm may fail to converge to the correct limit. In particular, in a simple mixture example with unequal variance where powering is known to produce slow mixing kernels, we show by simulation that cyclical MCMC fails to converge to the desired limit. Finally, we show that cyclical MCMC typically estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target. 
    more » « less