Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
Authors: Andrew Childs
Tongyang Li
Jin-Peng Liu
Chunhao Wang
Ruizhe Zhang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Quantum computing
logconcave sampling
normalizing constants
MCMC methods

Abstract: Given a convex function $f\colon\mathbb{R}^{d}\to\mathbb{R}$, the problem of sampling from a distribution $\propto e^{-f(x)}$ is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their normalizing constants $\int_{\mathbb{R}^d}e^{-f(x)}\mathrm{d} x$. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number $\kappa$ and dimension $d$) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only evaluation (zeroth-order) queries. For estimating normalizing constants, these algorithms also achieve quadratic speedup in the multiplicative error $\epsilon$. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity $\widetilde{O}(\kappa^{1/2}d)$ and $\widetilde{O}(\kappa^{1/2}d^{3/2}/\epsilon)$ for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in $\kappa,d,\epsilon$ over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/\epsilon^{1-o(1)}$ quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in $\epsilon$.

Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants
Andrew M. Childs
Joint Center for Quantum Information and Computer Science,
Department of Computer Science, and Institute for Advanced Computer Studies
University of Maryland amchilds@ume edu
Tongvang Li
Jin-Peng Liu
Center Frontiers of Computing Studies and School of Computer Science
Simons Institute and Department Mathematics
Peking University
UC Berkeley
tongyangli@pku. edu.
jliu1219@terpmail. und edu
Chunhao Wang
Ruizhe Zhang
Department of Computer Science and Engineering Pennsylvania State University
Department of Computer Science
The University of Texas at Austin ruiz ruizhe@utexas.edn edu
cwang@psu. edu
Abstract
Given convex function f: Rd - R, the problem of sampling from distribu- tion e-f(w) is called log-concave sampling. This task has wide applications in machine learning, physics, statistics, etc. In this work, we develop quantum algorithms for sampling log-concave distributions and for estimating their nor- malizing constants Jg. e e-f(=) dz. First, we use underdamped Langevin diffusion to develop quantum algorithms that match the query complexity (in terms of the condition number к and dimension d) of analogous classical algorithms that use gradient (first-order) queries, even though the quantum algorithms use only eval- uation (zeroth-order) queries. For estimating normalizing constants, these algo- rithms also achieve quadratic speedup in the multiplicative error e. Second, we de- velop quantum Metropolis-adjusted Langevin algorithms with query complexity (x22/2d) and 0(22/2,83/2 /e) for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in x; d, e over the best known classical algorithms by exploiting quantum analogs the Monte Carlo method and quantum walks. We also prove 1/cl-o(1) quantum lower bound for estimating normalizing constants, implying near-optimality our quantum algorithms in c.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Introduction
Sampling from given distribution is a fundamental computational problem. For example, in statis- tics, samples can determine confidence intervals or explore posterior distributions. In machine learn- ing, samples are used for regression and train supervised learning models. In optimization, sam- ples from well-chosen distributions can produce points near local or even global optima.
Sampling can be nontrivial even when the distribution is known. Indeed, efficient sampling is often challenging computational problem, and bottlenecks the running time in many applications. Many efforts have been made to develop fast sampling methods. Among those, one of the most successful tools is Markov Chain Monte Carlo (MCMC), which uses Markov chain that converges to the desired distribution (approximately) sample from it.
Here we focus on the fundamental task of log-concave sampling, i.e., sampling from a distribu- tion proportional to e where f: R2 + is a convex function. This covers many practical applications such as multivariate Gaussian distributions and exponential distributions. Provable per- formance guarantees for log-concave sampling have been widely studied [15]. A closely related problem is estimating the normalizing constants of log-concave distributions, which also has many applications [16].
Quantum computing has been applied to speed up many classical algorithms based on Markov pro- cesses, it is natural investigate quantum algorithms for log-concave sampling. If we can prepare a quantum state whose amplitudes are the square roots of the corresponding probabilities, then mea- surement yields random sample from the desired distribution. In this approach, the number of re- quired qubits is only poly-logarithmic in the size of the sample space. Unfortunately, such a quantum state probably cannot be efficiently prepared in general, since this would imply SZK C BQP [1]. Nevertheless, in some cases, quantum algorithms can achieve polynomial speedup over classical algorithms. Examples include uniform sampling on 2D lattice [35], estimating partition func- tions [4. 22, 31, 45, 46], and estimating volumes of convex bodies [6]. However, despite the impor- tance of sampling log-concave distributions and estimating normalizing constants, we are not aware of any previous quantum speedups for general instances of these problems.
Formulation In this paper, we consider a d-dimensional convex function f: Rdd - R which L-smooth and ju-strongly convex, i.e., μ1, L >> O and for any x. E Rd, x #
f(y) f(x) (Vx) E [m,, LJ. x
(1.1)
v113/2
We denote by :- L/μ the condition number of f. The corresponding log-concave distribution has probability density p Rd R with
pf(x) = c ef(s))
(1.2)
25
where the normalizing constant is
Z, = e ((()) dx.
(1.3)
ZERA
When there is no ambiguity, we abbreviate Pj and B as P and Z, respectively. Given an c E (0, 1),
the goal log-concave sampling is to output a random variable with distribution such that ||ا ell < e, and
the goal of normalizing constant estimation is to output a value Ž such that with probability at least 2/3, (1 ------ <)Z < Z < ()
Here || is a certain norm. We consider the general setting where the function f is specified by an oracle. In particular, consider the quantum evaluation oracle O,, standard model in the quantum computing literature [3. 6, 7, 50]. The evaluation oracle acts as
Oflæ, 1z. f(x) + v) Vx E Rdd y R.
(1.4)

---

(Quantum computing notations are briefly explained in Section 2.) We also consider the quantum gradient oracle o with
0v)læ,=) lr Vf(x) + + Vx, E R
(1.5)
In other words, we allow superpositions of queries to both function evaluations and gradients. The essence of quantum speedup is the ability to compute with carefully designed superpositions.
Contributions Our main results quantum algorithms that speed up log-coneave sampling and normalizing constant estimation.
Theorem 1.1 (Main log-coneave sampling result). Let p denote the log-concave distribution ( (1.2). There exist quantum algorithms that output random variable distributed according to P such that
p) S e where W2 is the Wasserstein 2-norm (2.4), using (1 / / c 1/3 + nd R3 ( 2/3)
queries to the quantum evaluation oracle (1.4); or - ~llv= S where || - || is the total variation distance (2.3), using ( queries to the quantum gradient oracle (1.5), (dx)/2d)/4) queries when the initial distribution is warm (formally defined in Appendix C.2.1).
In the above results, the query complexity 0(167/0g1/6 13d is achieved by our quan- tum ULD-RMM algorithm. Although the quantum query complexity is the same as the best known classical result [37], we emphasize that our quantum algorithm uses zeroth-order oracle while [37] uses first-order oracle. The query complexity (xx2/2d) is achieved by our quantum MALA al- gorithm that uses a first-order oracle (as in classical algorithms). This is a quadratic speedup in k compared with the best known classical algorithm [28]. With warm start, quantum speedup is even more significant: we achieve quadratic speedups in R and as compared with the best known classical algorithm with warm start [47].
Theorem 1.2 (Main normalizing constant estimation result). There exist quantum algorithms that estimate the normalizing constant by Z within multiplicative error with probability least 3/4,
using Ö(k7 /6 + -1) queries to the quantum evaluation oracle (1.4); or using 02 queries to the quantum gradient oracle (1.5).
Furthermore, this task has quantum query complexity least (2e-11)()) (Theorem 5.1).
Our query complexity / kd1/3,-1) for normalizing constant estimation achieves quadratic speedup in precision compared with the best known classical algorithm [16]. More remarkably, our quantum ULD-RMM algorithm again uses zeroth-order oracle while the slower best known classical algorithm uses first-order oracle [16]. Our quantum algorithm working with a first-order oracle achieves polynomial speedups in all parameters compared with the best known classical algorithm [16]. Moreover, the prepision-depeeddenc of our quantum algorithms is nearly optimal, which is quadratically better than the classical lower bound in 1/e [16].
To the best of our knowledge, these are the first quantum algorithms with quantum speedup for the fundamental problems of log-concave sampling and estimating normalizing constants. We explore multiple classical techniques including the underdamped Langevin diffusion (ULD) method [12- 14, 43), the randomized midpoint method for underdamped Langevin diffusion (ULD-RMM) [36, 37]. and the Metropolis adjusted Langevin algorithm (MALA) [8, 11, 15, 28, 29, 47], and achieve quantum speedups. Our main contributions are as follows.
Log-concave sampling. For this problem, our quantum algorithms based on ULD and ULD- RMM have the same query complexity as the best known classical algorithms, but our quantum algorithms only use a zeroth-orde -odorr (evaluation) oracle, while the classical algorithms use the first- order (gradient) oracle. For MALA, this improvement we can use the quantum gradient oracle in our quantum MALA algorithm to achieve a quadratic speedup in the condition number Furthermore, given warm-start distribution, our quantum algorithm achieves a quadratic speedup in all parameters.
the order of oracles is nontrivial, but
Normalizing constant estimation. For this problem, our quantum algorithms provide larger speedups. In particular, our quantum algorithms based on ULD and UL.D-RMM achieve quadratic

---

speedup in the multiplicative precision (while using zeroth-order oracle) compared with the corresponding best-known classical algorithms (using first-order oracle). Our quantum algo- rithm based on MALA achieves polynomial speedups in all parameters. Furthermore, we prove that our quantum algorithm nearly optimal in terms
We summarize our results and compare them to previous classical algorithms in Table and Table 2. See Appendix for more detailed comparisons to related classical and quantum work.
Table 1: Summary the query complexities classical and quantum algorithms for sampling d-dimensional log-concave distribution. Here и = L/ j in (1.1) and e is the error in the designated norm.
Method
Oracle
Complexity
Norm
0(1201244))
ULD [10]
gradient
W₂
111110 --13 + (82318
ULD-RMM [37]
gradient
W₂
MALA [28]
gradient
((dd)
TV
δ Ind!/2)
MALA with warm start (47)
gradient
TV
Ō(x20112--)
Quantum Inexact ULD (Theorem C.I)
evaluation
W2
0 -1/3 + keet/1 (213) ((1112)) δ ((2112001)))
Quantum Inexact ULD-RMM (Theorem C.2)
evaluation
W2
Quantum MALA (Theorem C.7)
gradient
TV
Quantum MALA (warm start) (Theorem C.6) gradient
TV
Table Summary of the query complexities of classical and quantum algorithms for estimating the normalizing constant of d-dimensional log-concave distribution. Here x L/μ (1.1) c the multiplicative error.
Method
Oracle
Complexity
0(20812 01 (ad13(-2)) O(maPe- mm, 51)
Multilevel ULD [16]
gradient
Multilevel ULD-RMM [16]
gradient
MALA [16]
gradient
0(220122))) o6 011700010 ((1))-
Multilevel Quantum Inexact ULD (Theorem D.3)
evaluation
Multilevel Quantum Inexact ULD-RMM (Theorem D.4)
evaluation
Quantum annealing with Quantum MALA (Theorem D.2) gradient
Techniques In this work, we develop systematic approach for studying the complexity of quan- tum walk mixing and show that for any reversible classical Markov chain, we can obtain quadratic speedup for the mixing time long as the initial distribution warm. In particular, apply the quantum walk and quantum annealing in the context of Langevin dynamics and achieve polynomial quantum speedups.
The technical ingredients of our quantum algorithms are highlighted below.
Quantum simulated annealing (Lemma 3.2). Our quantum algorithm for estimating normalizing constants combines the quantum simulated annealing framework of [45] and the quantum mean estimation algorithm of [31]. For each type of Langevin dynamics (which are random walks), build a corresponding quantum walk. Crucially, the spectral gap of the random walk is quadrat- ically amplified in the phase gap of the corresponding quantum walk. This allows to use Grover-like procedure to produce the stationary distribution state given a sufficiently good initial state. In the simulated annealing framework, this initial state is the stationary distribution state of the previous Markov chain.
Fffective spectral gap (Lemma C.7). We show how to leverage "warm" initial distribution to achieve quantum speedup for sampling. Classically, warm start leads to faster mixing even if

---

the spectral gap is small. Quantumly, we generalize the notion of "effective spectral gap" [6, 27, 34] our more general sampling problem. We show that with a bounded warmness parameter, quantum algorithms can achieve a quadratic speedup in the mixing time. By viewing the sampling problem as a simulated annealing process with only one Markov chain, we prove quadratic speedup for quantum MALA by analyzing the effective spectral gap.
Quantum gradient estimation (Lemma C.I). We adapt Jordan's 's quantum gradient algorithm [24] the ULD and ULD-RMM algorithms and give rigorous proofs bound the sampling error due to gradient estimation errors.
Open questions Our work raises several natural questions for future investigation:
Can achieve quantum speedup in d and for unadjusted Langevin algorithms such ULD and ULD-RMM? The main difficulty is that ULD and ULD-RMM are irreversible, while most available quantum walk techniques only apply to reversible Markov chains. New techniques might be required to resolve this question.
Can we achieve further quantum speedup for estimating normalizing constants with a warm start distribution? This might require a more refined version of quantum mean estimation.
Can we give quantum algorithms for estimating normalizing constants with query complexity sublinear in d? Such result would give provable quantum-classical separation due to the classical lower bound proved in [16].
((d==o(1)/ee
Limitations and societal impacts Researchers working on theoretical aspects of quantum com- puting or Monte Carlo methods may benefit from our results. In the long term, once fault-tolerant quantum computers have been built, our results may find practical applications in MCMC methods arising in the real world. As far as we are aware, our work does not have negative societal impacts.
2 Preliminaries
Basic definitions of quantum computation Quantum mechanics is formulated in terms of linear algebra. The computational basis of Cd is (čo.-.,,441 Ed-1); where ē = 1,...,,,....,. with the 1 in the (i+ 1)xh position. We use Dirac notation, writing [i) (called "ket") for and {il (a "bra") for E
The tensor product of quantum states is their Kronecker product: if (u) e Cd and (p) e Cd, then we have (u) @ lu) E Cdh @ da with
Iu) @ |o) (uo vo, ugV Und 1dd-
(2.1)
The basic element of quantum information is a qubit, quantum state in C2, which can be written as a (0) + b11) for some a, E C with |a|2 [b|2 = 1. An n--ubit tensor product state can be written as (u2) @ ... & (u..) E 22" where for any E [m]. Jus) is one-qubit state. Note however that most states in 2 are not product states. We sometimes abbreviate (u) @ |e) as (u)
Operations quantum states are unitary transformations. They are typically stated in the circuit model, where a k-qubit gate is unitary matrix in C² Two-qubit gates are universal, i.e., every n-qubit gate can be decomposed into a product of gates that act as the identity on n - qubits and as some two-qubit gate on the other qubits. The gate complexity an operation refers to the number of two-qubit gates used in quantum circuit for realizing it.
Quantum access function, referred as a quantum oracle, must be reversible and allow access to different values of the function in superposition (i.c., for linear combinations of computational basis states). For example, consider the unitary evaluation oracle Oy defined in (1.4). Given probability distribution {pr).. and a set of points {x:)= we have
O, Vm = Σ (Dll)))((..))). 1=1
(2.2)
Then measurement would give (xx;) with probability ps- However, quantum oracle can not only
simulate random sampling, but can enable uniquely quantum behavior through interference. Ex- amples include amplitude amplification- the main idea behind Grover's search algorithm [20] and
5

---

the amplitude estimation procedure used in this paper- and many other quantum algorithms relying on coherent quantum access to a function. Similar arguments apply to the quantum gradient oracle (1.5). If classical oracle can be computed by explicit classical circuit, then the corresponding quantum oracle can implemented by a quantum circuit of approximately the same size. There- fore, these quantum oracles provide useful framework for understanding the quantum complexity of log-concave sampling and normalizing constant estimation.
To sample from a distribution 9, it suffices to prepare the state (T) : Th VTlaa) and then measure it. For a Markov chain specified by a transition matrix P with stationary distribution π, one can construct a corresponding quantum walk operator W(P) (P). Intuitively, quantum walks can be viewed as applying a sequence quantum unitaries on a quantum state encoding the initial distribution to rotate it to the subspace of stationary distribution [T) The number of rotations needed (i.e., the angle between the initial distribution and stationary distribution) depends on the spectral gap of P, and a quantum algorithm can achieve a quadratic speedup via quantum phase estimation and amplification algorithms. More background on quantum walk is given in Appendix C.2.2.
Notations Throughout the paper, the big-O notations O(-), o(-), 2(-), and O(-) follow common definitions. The Ô notation omits poly-logarithmic terms, i.e., O(f) == Of poly f)). We say function f is L--Lipschitz continuous if [f - f(y)] s L.|2 yll for all y sufficiently near x. The total variation distance (TV-distance) between two functions f, g: Rd RR is defined
/ 15(x) g(x))dr.
|| g.|TV = 2 JR
(2.3)
Let (TR.)) denote the Borel a-field of Rd. Given probability measures 1 and v on (IRd, ((R))), a transference plan ( between μ and v is defined as a probability measure on (IRd x Id, B(RR) x B(E*)) such that for any A S. Rdd <(A x Ed) p(A) and ((Rdd A) ((A). We let I(u. v) denote the set of all transference plans. We let
W2(H,v) == inf / (CET( Jzxza | v(
(2.4)
denote the Wasserstein 2-norm between and v.
3 Quantum Algorithm for Log-Concave Sampling
In this section, we describe several quantum algorithms for sampling log-concave distributions.
Quantum inexact ULD and ULD-RMM We first show that the gradient oracle in the classical ULD and ULD-RMM algorithms can be efficiently simulated by the quantum evaluation oracle via quantum gradient estimation. Suppose we are given access to the evaluation oracle (1.4) for fxx). Then by Jordan's 's algorithm [24] (see Lemma C.1 for details), there is quantum algorithm that can compute V If fz) with a polynomially small errrro by querying the evaluation oracle O(1) times. Using this, we can prove the following theorem (see Appendix C.1 for details).
Theorem 3.1 (Informal version of Theorem C. and Theorem C.2). Letp x e be d-dimensional log-concave distribution with f satisfying (I.1). Given quantum evaluation oracle for f,
the quantum inexact ULD algorithm uses dx22d//22"" queries, and the quantum inexact ULD-RMM algorithm uses /66 1/3 + kdd -3--3/
2/3) queries.
to quantumly sample from a distribution that is c-close to p in Wy-distance.
We note that the query complexities of our quantum algorithms using zeroth-order oracle match the state-of-the-are classical ULD [10] and ULD-RMM [37] complexities with a first-order oracle. The main technical difficulty of applying the quantum gradient algorithm is that it produces a stochastic gradient oracle in which the output of the quantum algorithm g satisfies ||[/]] - [z S d 21), In particular, the randomness of the gradient computation is "entangled" with the randomness of the Markov chain. We use the classical analysis of ULD and ULD-RMM processes [36] to prove that the stochastic gradient will not significantly slow down the mixing of ULDD processes, and that the error caused by the quantum gradient algorithm can be controlled.

---

We next propose two quantum algorithms with lower query complexity than classical MALA, one with a Gaussian initial distribution and another with a warm-start distribution. The main technical tool we use is a quantum walk in continuous space.
Quantum MALA
The classical MALA (i.e., Metropolized HMC) starts from Gaussian distribution. /V(0, T.- and performs leapfrog step in each iteration. It is well-known that the initial Gaussian state
lpo)
( Jzd
T.
d/4
e
-1=-==111 (2) d=
(3.1)
2
can be efficiently prepared. We show that the quantum walk update operator
f dx Jax dy PPs-yyl>aa @ [0)
{
U U==
JRc
(3.2)
can be efficiently implemented. where Px-ty == p(a, y) the transition density from x to y. and the density p satisfies Jq p(z. y) dy for any I 12d.
Lemma 3.1 (Informal version of Lemma C.6). The continuous-paac quantum walk operator cor- responding to the MALA Markov chain can implemented with ((1) gradient and evaluation queries.
In general, difficult to quantumly speed up the mixing time of a classical Markov chain, which is upper bounded by O log (og((m)))) where d the spectral gap. However, [45] shows that a quadratic speedup is possible when following a sequence of slowly-varying Markov chains. More specifically, let Po..... Pr be the stationary distributions of the reversible Markov chains Mo..... ..... MM and let (po).... ................................ (pr) for all E (O.....r
be the corresponding quantum states. Suppose (ps|Ptta)l 2 1), and suppose the spectral gaps of M, are lower-bounded by Then we can prepare a quantum state lot) that e-close to (p+) using 0(8-1/2rp-1) quan- tum walk steps. To fulfill the slowly-varying condition, consider annealing process that goes from Po -O Ia) the target distribution PM++1 p in M Ö(vd) stages. At the ith stage, the stationary distribution is P. e with f; := + 30, ||x|| By properly choosing
ai I ... I d.M. we prove that this sequence of Markov chains is slowly varying.
Lemma 3.2 (Informal version Lemma B.6). we we take of záz and o; (1 + Jg) then for 0 < i S M, we have Kp 1) 2 22(1.
Combining Lemma 3.1, Lemma 3.2, and the effective spectral gap of MALA (Lemma C.7), have:
Theorem 3.2 (Informal version of Theorem C.7). Let p x e- be a d-dimensional log-concave distribution with of satisfying (1.1). There is a quantum algorithm (Algorithm 1) that prepares state (P) with [|p) 1p)1l S using ((k2/2d) gradient and evaluation oracle queries.
Algorithm 1: QUUNTUANALLLAORRLO--CCOONSSSSES
(Informal) Evaluation oracle O, gradient oracle Ovy, smoothness parameter I., convexity
Input:
parameter /
Output: Quantum state (p) close to the stationary distribution state fea f dlæ))
Compute the cooling schedule parameters PI,...,0M
Prepare the state (Pu) Sg - ||x=1///f d|z)
for i +- 1,......,... MM do
Construct O, and Ov,, where f((x= = f(x) + /
5
Construct quantum walk update unitary U with O₁, and Ovi.
Implement the quantum walk operator and the approximate reflection R.
7 Prepare (ps) by performing -amplitude amplification with RG on the state |p: 1)
return (PM)
For the classical MALA with Gaussian initial distribution, it was shown by [29] that the mixing time is at least ((dd). Theorem 3.2 quadratically reduces the x dependence.
7

---

Note that Algorithm I uses a first-order oracle, instead of the zeroth-order oracle used in the quantum ULD algorithms. The technical barrier to applying the quantum gradient algorithm (Lemma C.1) in the quantum MALA is to analyze the classical MALA with a stochastic gradient oracle. We currently do not know whether the "entangled randomness" dramatically increases the mixing time.
More technical details and proofs are provided in Appendix C.
4 Quantum Algorithm for Estimating Normalizing Constants
In this section, we apply our quantum log-concave sampling algorithms to the normalizing constant estimation problem. A very natural approach to this problem is via MCMC, which constructs multi-stage annealing process and uses a sampler at each stage to solve a mean estimation problem. We show how to quantumly speed up these annealing processes and improve the query complexity of estimating normalizing constants.
Quantum speedup for the standard annealing process We first consider the standard annealing process for log-concave distributions, as already applied in the previous section. Recall that we pick parameters d1 d2
< JM and construct a sequence of Markov chains with stationary distributions Ps x e e- where fi = + 20? |,. Then, at the ith stage, we estimate the expectation
Ep, 191 where g. = =xxp (2 (0,0,"-
(4.1)
If we can estimate each expectation with relative error at most O(/MM), then the product of these M quantities estimates the normalizing constant Z = = e- f(x) dæ with relative error at most c.
For the mean estimation problem, [31] showed that when the relative variance Var,, [ad] is constant, ",,191
there is a quantum algorithm for estimating the expectation p9 within relative error at most e using ((1/e) quantum samples from the distribution pi. Our annealing schedule satisfies the bounded relative variance condition. Therefore, by the quantum mean estimation algorithm, we improve the sampling complexity of the standard annealing process from ( to (M
To further improve the query complexity, we consider using the quantum MALAs developed in the previous section to generate samples. Observe that Algorithm outputs a quantum state correspond- ing to some distribution that is close to ps. instead of an individual sample. If we can estimate the expectation without destroying the quantum state, then we can reuse the state and evolve it for the (i + 1)st Markov chain. Fortunately, we can use -on-destreetive mean estimation to estimate the expectation and restore the initial states. A detailed error analysis of this algorithm can be found in I6, 22]. We first prepare Ö(ME copies of initial states corresponding to the Gaussian distribu- tion (0, La). Then, for each stage, we apply the non-destructive mean estimation algorithm to estimate the expectation [9.] and then run quantum MALA to evolve the states |p:) to (pt+1)- This gives our first quantum algorithm for estimating normalizing constants.
Theorem 4.1 (Informal version of Theorem D.2). Let Z be the normalizing constant in (1.3). There is quantum algorithm (Algorithm 2) that outputs estimate Z with relative error most using ( ke (2c-)) queries the quantum gradient and evaluation oracles.
Quantum speedup for MLMC Now we consider using multilevel Monte Carlo (MLMC) as the annealing process and show how to achieve quantum speedup. MLMC was originally developed by [23] for parametric integration; then [17] applied MLMC to simulate stochastic differential equa- tions (SDEs). The idea of MLMC is natural: we choose a different number of samples at each stage based on the cost and variance of that stage.
To estimate normalizing constants, variant of MLMC was proposed in [16]. Unlike the standard MLMC for bounding the mean-squared error, they upper bound the bias and the variance separately, and the analysis technically difficult. The first quantum algorithm based on MLMC was subse- quently developed by [2) based on the quantum mean estimation algorithm. Roughly speaking, the quantum algorithm can quadratically reduce the e-dependence of the sample complexity compared with classical MLMC.
8

---

Algorithm 2: AOONTTTALLLOOSTTTAIIIOAAAAOOOOOO (Informal)
Input: Evaluation oracle O, gradient oracle Ovs
Output: Estimate Z of with relative error at m
1 M + ((vd), K + Ō
Compute the cooling schedule parameters -1,--.300
3 for j e- 1..... K do
L Prepare the state (mr)) Jga e /a]= (x)))
7 +- (2Tof)
for i f- I,..., M do
9i f Non-destructive mean estimation for 9i using .l.,,))...,,ll k)),
7. < Zij
for j t I..... . do
10
((+11) < QUANTUMMALA(O), Ov
11 return
In this work, we apply the quantum accelerated MLMC (QA-MLMC) scheme [2] to simulate under- damped Langevin dynamics the SDE. One challenge using QA-MLMC is that gi in our setting is not Lipschitz. Fortunately, as suggested by [16], this issue can be resolved by truncating large (r:t)² }. with the choice
and replacing gi by h4 == min Dr. exp( (xp(o?((ta>)) (f(ta-)))
= Ō (
1
r = Epus || + ( log(1/e)
(4.2)
Vdlog(1/e))
to ensure h._ is O Lipschitz. Furthermore, |E (h+ 9i)l < by Lemmas C.7 and C.8 in Fe,9: [16]. For simplicity, we regard 9i as a Lipschitz continuous function in our main results. We present QA-MLMC in Algorithm 3, where the sampling algorithm A can be chosen to be quantum inexact ULD/ULD-RMN or quantum MALA.
Algorithm 3: QA (Informal)
Input: Evaluation oracle O, function g. error e, a quantum sampler A(ro, fn) for p Output: An estimate of R = EEph
K t Ō(E-))
2 Compute the initial point do and the step size TJo Compute the number of samples NI...., Nu
for j < 1, 1..... K do
Let 77, 11
for i + 1.....N, .N do
Sample X. by A(f, zo, nj), and sample X,u/² 2 by A(f, G. QMEANEST(( (X,) )eIN))) and G (Mo DEEN,)
return == Go Σj= - - Ō+)
This MC framework reduces the e-dependence of the sampling complexity for estimating normalizing constants from - to c in both the ULD and ULD-RMM cases, compared with the state-of-the-ar classical results [16].
Using the quantum inexact ULD and ULD-RMM algorithms (Theorem 3.1) to generate samples, we obtain our second quantum algorithm for estimating normalizing constants (see Appendix for proofs).
Theorem 4.2 (Informal version of Theorem D.3 and Theorem D.4). Let Z be the normalizing con- stant in (1.3). There exist quantum algorithms for estimating Z with relative error at most using
quantum inexact ULD with 2 queries to the evaluation oracle, and

---

quantumm inexact ULD-RMM with O(dd x//6 =d)= queries to the evaluation oracle.
5 Quantum Lower Bound
Finally, we lower bound the quantum query complexity of normalizing constant estimation.
Theorem 5.1. For any fixed positive integer k, given query access (1.4) to a function f: IR + R that is 1.5-smooth and 0.5-strongly convex, the quantum query complexity of estimating the partition function Z = fgs c f(() dæ within multiplicative error e with probability at least 2/3 is (2(c IT37K).
The proof of our quantum lower bound is inspired by the construction in Section of [16]. They consider a log-concave function whose value is negligible outside a hypercube centered at 0. The interior of the hypereube is decomposed into cells of two types. The function takes different values on each type, and the normalizing constant estimation problem reduces to determining the number of cells of each type. Quantumly, we follow the same construction and reduce the cell counting problem to the Hamming weight problem: given an n-bit Boolean string and two integers l < E, decide whether the Hamming weight (i.e., the number of ones) of this string is & or fg. This problem has known quantum query lower bound [32], which implies the quantum hardness of estimating the normalizing constant. The full proof of Theorem 5.1 appears Appendix
Acknowledgements
AMC acknowledges support from the Army Research Office (grant W911NF-20-1-0015); the De- partment of Energy, Office of Science, Office of Advanced Scientific Computing Research, Ac- celerated Research in Quantum Computing program; and the National Science Foundation (grant CCF-1813814)) TL was supported by a startup fund from Peking University, and the Advanced Institute of Information Technology, Peking University. JPI. was supported by the National Science Foundation (grant CCF-1813814 1)), an NSF Quantum Information Science and Engineering Network (QISE-NET) triplet award (DMR-1747426), a Simons Foundation award (No. 825053), and the Si- mons Quantum Postdoctoral Fellowship. RZ was supported by the University Graduate Continuing Fellowship from UT Austin.
References
[1] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowl- edge, Proceedings of the 35th Annual ACM Symposium Theory of Computing, pp. 20-29, 2003, ar "xiv:quant-ph003000
[2] Dong An, Noah Linden, Jin-Peng Liu, Ashley Montanaro, Changpeng Shao, and Jiasu Wang, Quantum- accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance Quantum 5 (2021), 481, arXiv:2012.06255
[3] Joran van Apeldoom, András Gilyén, Sander Gribling, and Ronald de Wolf, Convex optimization using quantum oracles, Quantum 4 (2020), 220, arXiv:1809.00644
[4] Srinivasan Arunachalam, Vojtech Havlicek. Giacomo Nannicini, Kristan Temme. and Pawel Woc- jan, Simpler (classical) and faster (quantum) algorithms for Gibbs partition functions, 2021 IEEE In- terntiional Conference Quantum Computing and Engineering (QCE), pp. 112- 122, IEEE, 2021,
MrXiv:2009.112700
[5] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, Quantum amplitude amplification and estimation, Contemporary Mathematics 305 (2002), 53 74, arXiv:quant ph/0005055.
[6] Shouvanik Chakrabarti, Andrew M. Childs, Shih-Han Hung. Tongyang Li, Chunhao Wang, and Xiaodi Wu, Quantum algorithm for estimating volumes of corvex bodies, 2019, arXiv:1908.0300 1908.03903.
[7] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li. and Xiaodi Wu, Quantum algorithms and lower bounds for convex optimization, Quantum 4 (2020), 221, 10%.01109..1131...
[8] Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu, Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients, Journal of Machine Learning Research 21 (2020), 1-72, arXiv: 12247.
[9] Yuansi Chen, Raaz Dwivedi, Martin J Wainwright, and Bin Yu, Fast mixing of metropolized hamiltonian monte carlo: Benefits of multi-step gradients., J. Mach. Learn Res. 21 (2020), 92-1.
10

---

[10] Xiang Cheng, Niladri S. Chatterji. Peter L. Bartlett, and Michael I. Jordan, Underdamped langevin meme: A non-asymplotic analysis, Conference on learning theory, pp. 300-323, PMLR, 2018, 1707 707.03663.
[11] Sinho Chewi, Chen Lu, Kwangjun Ahn, Xiang Cheng, Thibaut Le Gouic, and Philippe Rigollet, Optimal dimension dependence of the metropolis-adjjused langevin algorithm, Conference on Learning Theory, pp. I 1260-1300, PMIR, 2021, arXiv:2012.
[12] Amnk Dalalyan and Avetik Karagulyan. User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient, Stochastic Processes and their Applications 129 (2019), no. 12, 5278-5311, 11.0:1710.00095.
[13] Alain Durmus, Szymon Majewski, and Blažej Miasojedow, Analysis of Langevin Monte Carlo via convex optimization. The Journal of Machine Learning Research 20 (2019), no. 2666 2711, arXiv: 802.09188.
[14] Alain Durmus and Eric Moulines, Nonasymptotic convergence analysis for the wnadjusted Langevin al- gorithm, The Annals of Applied Probability 27 (2017), no. 3, 1551-1587, arXiv: S.di:1557.00000 50002050...
[15] Raaz Dwivedi, Yuansi Chen, Martin Wainwright, and Bin Yu, Log-concave sampling: Metropolis- Hastings algorithms are fast!, Conference on learning theory, pp. 793-797, PMLR, 2018, arXiv:1801.00 180..02999..
[16] Rong Ge. Holden Lee, and Jianfeng Lu, Estimating normalizing constants for log-concave distributions: Algorithms and lower bounds, Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pp. 579-586, 2020, 1rXiv:1911.000 1.00443.
[17] Michael B. Giles, Multilevel Monte Carlo path simulation, Operations Research 56 (2008), no. 3, 607-
617.
[18] Michael B. Giles, Multilevel Monte Carlo methods, Acta Numerica 24 (2015), 259-328.
[19] Lov Grover and Terr Rudolph, Creating superpositions that correspond to efficiently integrable proba- bility distributions, 2002, arXiv:quant- pptpttt/hhh/////11 11200
[20] Lov K. Grover, A fast quantum mechanical algorithm for database search, Proceedings of the Twenty- eighth Annual ACM Symposium on Theory of Computing, pp. 212-219, ACM, 1996, arXiv:quant- ph/9605043,
[21] Yassine Hamoudi and Frédéric Magniez, Quantum Chebyshev's 's inequality and applications, Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, Leibniz International Proceedings in Informatics, vol. 132. pp. 69:1 16:16666,, 2019, arXiv:1807 ,06456.
[22] Aram W. Harrow and Annie Y. Wei, Adaptive quantum simulated annealing for Bayesian inference and extimating partition functions, Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Al- gorithms, pp. 193-212, 2020, Sttv:1907.0996.
[23] Stefan Heinrich, Multilevel Monte Carlo methods, International Conference on Large-Scale Scientific Computing, pp. 58-67, Springer, 2001.
[24] Stephen P. Jordan, Fast quantum algorithm for numerical gradient estimation, Physical Review Letters 95 (2005), no. 5, 050501.
[25] Ravi Kannan, László Lovász, and Ravi Montenegro, Blocking conductance and mixing random walks, Comb, Probab. Comput. 15 (2006), no. 4, 541-570.
[26] Phillip Kaye and Michele Mosca, Quantum networks for generating arbitrary quantum states, Interna- tional Conference on Quantum Information, p. PB28, Optical Snciety of America, 2001, arXiv:quant- ph/0407102.
[27] Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, and Mario Szegedy, Quanium query complexity of state conversion, 2011 1 IEEE 52nd Annual Symposium Foundations of Computer Science, pp. 344- 353, IEEE, 2011.
[28] Yin Tat Lee, Ruoqi Shen, and Kevin Tian, Logsmooth gradient concentration and tighter runtimes for metropolized Homiltonian Monte Carlo, Conference on Learning Theory, pp. 2565-2597, PMLR, 2020, XXix:2002.04221
[29] Yin Tat Lee, Ruoqi Shen, and Kevin Tian, Lower bounds on Metropolized sampling methods for well- conditioned distributions, Advances in Neural Information Processing Systems, vol. 34, pp. 18812- 18824, 2021, arXiv:2106.0m 054400.
[30] Guang Hao Low, Theodore J. Yoder, and Isaac L. Chuang, Quantum inference on Bayesian networks, Physical Review A 89 (2014), no. 6, 062315, arXiv: 140.7399..
[31] Ashley Montanaro, Quantum speedup of Monte Carlo methods, Proceedings of the Royal Society A 471
(2015), no. 2181, 20150301, arXiv:1504.06999
[32] Ashwin Nayak and Felix Wu, The quantum query complexity of approximating the median and related statistics, Proceedings of the st Annual ACM Symposium on Theory of Computing, pp. 384 384-393, 1999, arXiv.quatt-ph/980 906600066.
11

---

[33] Maris Ozols, Martin Roetteler, and Jérémie Roland, Quaniton rejection sampling, ACM Transactions on Computation Theory (TOCT) 5 (2013), no. 1-33, 1tXiv:1103.2774
[34] Ben W. Reichardt, Spon programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function, 2009 50th Annual IEEE Symposium on Foundations of Computer Sci- ence, pp.
IEEE, 2009, arXiv:0904.275:
[35] Peter C. Richter, Quantum speedup of classical mixing processes, Physical Review A 76 (2007), no. 4, 042306, arXivvquant uzXiv.quant-ph/0000200. ph/0609204.
[36] Abhishek Roy, Lingqing Shen, Krishnakumar Balasubramanian, and Saeed Ghadimi, Stochastic zeroth- order discretizations of Langevin diffusions for Bayesian inference, 2019, arXiv:1902.01372.
[37] Ruoqi Shen and Yin Tat Lee, The randomized midpoint method for log-concave sampling, Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 2100-2111, 2019, MxXiv:1909005599
[38] Rolando D. Somma, Sergio Boixo, and Howard Barnum, Quantum simulated annealing. 2007, 112.
[39] Rolando D. Somma, Sergio Boixo, Howard Barnum, and Emanuel Knill, Quantum simulations of classi- cal annealing processes, Physical Review Letters 101 (2008), no. 13, 130504, arXiv:0804.157)
[40] Daniel Štefankovič, Santosh Vempala, and Eric Vigoda, Adaptive simulated annealing: A near- optimal connection between sampling and counting, Journal of the ACM 56 (2009), no. 3, 1-36. MrXiv:ss00120058
[41] Mario Szegedy, Quantum speed-up of Markov chain based algorithms, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 32-41, 2004.
[42] Kristan Temme. Tobias J. Osborne, Karl G. Vollbrecht, David Poulin, and Frank Verstraete, Quantum Metropolis sampling, Nature 471 (2011), no. 7336, 87-90, arXiv:0911.3635.
[43] Santosh Vempala and Andre Wibisono, Rapid convergence of the unadjusted Langevin algorithm:: Isoperimetry suffices, Advances in Neural Information Processing Systems 32 (2019), 8094 8106, arXiv:1903.08$3 0.8668....8......
[44] Nathan Wiebe and Christopher Granade, Can small quantum systems learn?, 2015, arXiv:1512.033
[45] Pawel Woejan and Anura Abeyesinghe, Speedup via quantum sampling, Physical Review A 78 (2008), no, 4, 042336, arXiv:0804.4259.
[46] Pawel Woejan, Chen-Fu Chiang, Daniel Nagaj, and Anura Abeyesinghe, Quantum algorithm for approx- imating partition functions, Physical Review 80 (2009), no. 022340, arXiv:08 11 .,0566.
[47] Keru Wu, Scott Schmidler, and Yuansi Chen, Minimax mixing time of the Metropolis-adjustee Langevin algorithm for log-concave sampling, Journal of Machine Learning Research 23 (2022). no. 270, 1-63, arXiv:2109.1380 13055.
[48] Man-Hong Yung and Alán Aspuru-Guzik, A quantum--qantumm Metropolis algorithm, Proceedings of the National Academy of Sciences 109 (2012), no. 3, 754-759, 1rX 1.1468.
[49] Christof 7alka, Simulating quantum systems on a quantum computer, Proceedings the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 454 (1 (1998), no. 1969, 313-322,
arXiv:quant- www-quantt-h/66030222 ph/9603026.
[50] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, Quantum algorithms for escaping from saddle points, Quan- tum 5 (2021), 529, arXiv:2007.1025.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
12

---

3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you't re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi-
able information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "PiKsE2Ieyva", "reviewer": "Reviewer_DQxR", "summary": "The main contributions of the paper are two-fold. \nThe first contribution consists of applying quantum estimators of the gradient of the potential function $\\nabla f$ in Langevin-type algorithms that sample from a target distribution $\\pi(\\cdot) = \\exp(-f(\\cdot))/Z_f$. The authors use Underdamped Langevin algorithm, Metropolis adjusted Langevin algorithm, ULA with randomized midpoint discretization method. \nThe second part of the paper aims at the estimation of the normalizing constant $Z_f$ using what they call _quantum speedup for MLMC_. \nEssentially, this paper is (one of) the first to use the quantum estimation techniques in the problem of MCMC sampling. ", "questions": "The paper is very hard to read. There no many proofs and the claims are hard to check, as most lemmas and propositions are taken from other papers. The main algorithms should be presented in detail and proofs of the main claims should be stated clearly. ", "limitations": "The application of this work is not possible at this moment and it is not clear when it will be possible to implement such an algorithm. While as the existing work on Langevin sampling is simple to implement when compared to the proposed methods. ", "rating": 3, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTHS\nThe main advantage \nof this approach is the low query complexity for each iteration which implements a known zeroth-order gradient estimation algorithm. \n\nWEAKNESSES\nThe weakness of the paper is the quality of presentation and the applicability of the algorithm. The paper is hard to read, as most notions are presented very briefly. The quantum computations and the estimation algorithm are not well written and are not well defined. The main sampling algorithms are not presented either. This is very inconvenient for an unexperienced reader in any of these two topics. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4ywBDDgvIwL", "reviewer": "Reviewer_gFQg", "summary": "The authors consider the problem of sampling and normalizing constant estimation for log-concave distributions, and derive query complexity bounds for quantum algorithms. The authors use state-of-the-art bounds for classical algorithms as a starting point, and show how to achieve quantum speedup.\n\nThey show that for strongly log-concave distributions with condition number $\\kappa$:\n\n1. Sampling: Using underdamped Langevin diffusion, quantum algorithms can obtain the same query complexity as classical algorithms while using zeroth rather than first-order (gradient) queries. Moreover, quantum MALA has mixing time that is the square root of classical MALA, $\\tilde O(\\kappa^{1/2} d)$ and $\\tilde O(\\kappa^{1/2}d^{1/4})$ from a cold or warm start, respectively.\n2. Normalizing constant estimation: Quantum algorithms can speed up normalization constant estimation, obtaining query complexity $\\tilde O(\\kappa^{1/2}d^{3/2}/\\epsilon)$ (with MALA) or $\\tilde O((\\kappa^{7/6}d^{7/6} + \\kappa d^{4/3})/\\epsilon)$ (using ULD-RMM), which improves the classical dependence on $\\epsilon^2$).\n\nThey also show a $1/\\epsilon^{1-o(1)}$ quantum lower bound for normalizing constant estimateion, giving near-optimality in $\\epsilon$.\n\nKey quantum tools include:\n\n* Jordan's algorithm which gives an estimate of the gradient using O(1) queries to a quantum evaluation oracle.\n* A general square-root speedup for quantum algorithms based on reversible Markov chains, when using a sequence of Markov chains with *slowly varying* stationary distributions, starting from the initial distribution. (This is applied to MALA.)\n* Quantum algorithm for mean estimation, and quantum version of multilevel Monte Carlo whose query complexity has dependence $O(1/\\epsilon)$.", "questions": "* How are quantum states over $\\mathbb R^d$ defined; what \"space\" do they live in? It seems that they have to be \"square roots\" of probability distributions over $\\mathbb R^d$. Some care (and measure theory...) is required to make this mathematically formal, but the preliminaries section only discusses the case of finite-dimensional spaces.\n* In what sense can one expect to prepare these states (in e.g., a discrete quantum circuit, or another reasonable model of a quantum computer)?\n\nMinor notes:\n\n* line 51: delete \"log-concave\" - that is a description of the distribution, not the problem. Add: random variable \"with distribution\" $\\tilde \\rho$.\n* (A.3): missing - sign\n* line 527: Besides... also have -> In addition... also has.\n* line 637: There seems to be a missing factor of 2: $||x||^2/(2\\sigma_i^2)$\n* line 643: Missing $\\sqrt{\\cdot}$, $\\ge$ should be $\\le$.\n* 666: speedup -> sped up\n* 704: oracle \"satisfying\" -> satisfies\n* Algorithm 6-7: It seems that the computation of $\\tilde g$ can be put at the beginning of the for loop to avoid writing it twice.\n* Algorithm 8, line 6: missing tilde.\n* 790: register -> registers\n* 797: What does \"uncompute\" mean?\n* 849: What is T in the following equation?\n* 855: $O(\\epsilon)$ should be $O(\\beta \\epsilon)$.\n* 867: Given a state... -> Let ... be a state\n* 929: \"speedup\" the query complexity -> reduce\n* 974: \"much\" complicated -> more", "limitations": "The authors acknowledge some limitiations which they present as open questions. Most significantly, do the quantum algorithms based on underdamped Langevin have a better dependence on $d$ and $\\kappa$? (Known speedups don't apply to irreversible chains.) ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper initiates work on the very natural idea of using quantum algorithms to speed up gradient-based MCMC algorithms, establishing basic quantum analogues of the well-studied Langevin-based algorithms and obtaining the signature \"square-root\" speedups in certain cases. This paves a good foundation for a promising area of research. The observation that quantum algorithms can make do with 0th order information is useful and surprising (for me).\n\nSome of the math regarding the quantum \"objects\" involved can be made more mathematically precise, especially for those who are not as familiar. I suggest adding more exposition on the quantum formalism.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0vjnLIR5AI", "reviewer": "Reviewer_rirc", "summary": "This paper discusses quantum type algorithms in estimating the log concave probability measures. The rates in total variation and W2 norm are provided.", "questions": "The paper is well written and I do not have question.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well presented and I mostly enjoyed reading the paper. The results in the paper are scientifically correct and make sense to me.\nHowever, the tools used in the paper to prove the convergence rate are quite standard. The novelty here is to put all analysis in the quantum lens. Moreover, as we can see in Table 1, the quantum versions of ULA or MALA do not really differ from the standard ULA and MALA, regarding the dependence in dimension d. This raised question on whether the quantum setting is really beneficial.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept