Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.

They show that for strongly log-concave distributions with condition number $\kappa$:

1. 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.
2. 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$).

They also show a $1/\epsilon^{1-o(1)}$ quantum lower bound for normalizing constant estimateion, giving near-optimality in $\epsilon$.

Key quantum tools include:

* Jordan's algorithm which gives an estimate of the gradient using O(1) queries to a quantum evaluation oracle.
* 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.)
* Quantum algorithm for mean estimation, and quantum version of multilevel Monte Carlo whose query complexity has dependence $O(1/\epsilon)$.
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).

Some 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.
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.
* 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)?

Minor notes:

* line 51: delete "log-concave" - that is a description of the distribution, not the problem. Add: random variable "with distribution" $\tilde \rho$.
* (A.3): missing - sign
* line 527: Besides... also have -> In addition... also has.
* line 637: There seems to be a missing factor of 2: $||x||^2/(2\sigma_i^2)$
* line 643: Missing $\sqrt{\cdot}$, $\ge$ should be $\le$.
* 666: speedup -> sped up
* 704: oracle "satisfying" -> satisfies
* 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.
* Algorithm 8, line 6: missing tilde.
* 790: register -> registers
* 797: What does "uncompute" mean?
* 849: What is T in the following equation?
* 855: $O(\epsilon)$ should be $O(\beta \epsilon)$.
* 867: Given a state... -> Let ... be a state
* 929: "speedup" the query complexity -> reduce
* 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.)
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper discusses quantum type algorithms in estimating the log concave probability measures. The rates in total variation and W2 norm are provided.
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.
However, 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.
questions: The paper is well written and I do not have question.
limitations: NA
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The main contributions of the paper are two-fold. 
The 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. 
The second part of the paper aims at the estimation of the normalizing constant $Z_f$ using what they call _quantum speedup for MLMC_. 
Essentially, this paper is (one of) the first to use the quantum estimation techniques in the problem of MCMC sampling. 
strengths_and_weaknesses: STRENGTHS
The main advantage 
of this approach is the low query complexity for each iteration which implements a known zeroth-order gradient estimation algorithm. 

WEAKNESSES
The 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. 
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.
review_title: null

Meta-review: metareview: This work considers the problem of sampling and normalizing constant estimation for log-concave distributions in the quantum setting. 
Starting from state-of-the-art bounds for classical algorithms, the authors show how to achieve quantum speedup in a number of settings.
A quantum lower bound for normalizing constant estimation is also derived (as a function of the desired accuracy $\epsilon$). This submission initiates a natural direction --- using quantum algorithms to speed up gradient-based MCMC algorithms --- and obtains interesting and non-trivial improvements in some base cases. The expert reviewers who read the paper in depth found this work conceptually interesting, well-written, and technically non-trivial. Consequently, I recommend acceptance.
confidence: Less certain
Decision: Accept