Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions
- URL: http://arxiv.org/abs/2310.11445v1
- Date: Tue, 17 Oct 2023 17:55:32 GMT
- Title: Stochastic Quantum Sampling for Non-Logconcave Distributions and
Estimating Partition Functions
- Authors: Guneykan Ozgul, Xiantao Li, Mehrdad Mahdavi, Chunhao Wang
- Abstract summary: We present quantum algorithms for sampling from nonlogconcave probability distributions.
$f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
- Score: 13.16814860487575
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present quantum algorithms for sampling from non-logconcave probability
distributions in the form of $\pi(x) \propto \exp(-\beta f(x))$. Here, $f$ can
be written as a finite sum $f(x):= \frac{1}{N}\sum_{k=1}^N f_k(x)$. Our
approach is based on quantum simulated annealing on slowly varying Markov
chains derived from unadjusted Langevin algorithms, removing the necessity for
function evaluations which can be computationally expensive for large data sets
in mixture modeling and multi-stable systems. We also incorporate a stochastic
gradient oracle that implements the quantum walk operators inexactly by only
using mini-batch gradients. As a result, our stochastic gradient based
algorithm only accesses small subsets of data points in implementing the
quantum walk. 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, making the quantum algorithms nontrivial to
analyze. To overcome these challenges, we first build a hypothetical Markov
chain that is reversible, and also converges to the target distribution. Then,
we quantified the distance between our algorithm's output and the target
distribution by using this hypothetical chain as a bridge to establish the
total complexity. Our quantum algorithms exhibit polynomial speedups in terms
of both dimension and precision dependencies when compared to the best-known
classical algorithms.
Related papers
- Robust Dequantization of the Quantum Singular value Transformation and
Quantum Machine Learning Algorithms [0.0]
We show how many techniques from randomized linear algebra can be adapted to work under this weaker assumption.
We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms.
arXiv Detail & Related papers (2023-04-11T02:09:13Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash
Equilibrium [62.51015395213579]
We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games.
The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
arXiv Detail & Related papers (2023-03-02T05:08:15Z) - Concise and Efficient Quantum Algorithms for Distribution Closeness
Testing [0.2741266294612775]
We study the impact of quantum computation on the fundamental problem of testing the property of distributions.
We propose the currently best quantum algorithms for this problem under the metrics of $l1$-distance and $l2$-distance.
arXiv Detail & Related papers (2023-02-13T04:03:59Z) - Importance sampling for stochastic quantum simulations [68.8204255655161]
We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients.
We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage.
Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
arXiv Detail & Related papers (2022-12-12T15:06:32Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
We study the problem of designing worst-case to average-case reductions for quantum algorithms.
We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
arXiv Detail & Related papers (2022-12-06T22:01:49Z) - 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) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle.
We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm.
We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
arXiv Detail & Related papers (2022-05-26T20:32:36Z) - Faster quantum mixing of Markov chains in non-regular graph with fewer
qubits [0.0]
In quantum cases, qsampling from Markov chains can be constructed as preparing quantum states with amplitudes arbitrarily close to the square root of a stationary distribution.
In this paper, a new qsampling algorithm for all reversible Markov chains is constructed by discrete-time quantum walks.
In non-regular graphs, the invocation of the quantum fast-forward algorithm accelerates existing state-of-the-art qsampling algorithms for both discrete-time and continuous-time cases.
arXiv Detail & Related papers (2022-05-12T14:08:08Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
We propose two single-timescale single-loop algorithms that require only one data point each step.
Our results are expressed in a form of simultaneous primal and dual side convergence.
arXiv Detail & Related papers (2020-08-23T20:36:49Z) - 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 Sampling Algorithms for Near-Term Devices [0.0]
We introduce a family of quantum algorithms that provide unbiased samples by encoding the entire Gibbs distribution.
We show that this approach leads to a speedup over a classical Markov chain algorithm.
It opens the door to exploring potentially useful sampling algorithms on near-term quantum devices.
arXiv Detail & Related papers (2020-05-28T14:46:20Z)
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.