arXiv:2609.20253

Quantum Speedups for Log-Concave Sampling from Local Structure

Chenghua Liu, Qisheng Wang, Zhengfeng Ji

quant-phcs.DSSubmitted Aug 14, 2026• Announced Aug 17, 2026• 0 citations

Abstract

For a convex function $f \colon \mathbb{R}^d \to \mathbb{R}$, the problem of sampling from a distribution proportional to $e^{-f(x)}$ is called log-concave sampling. In many practical scenarios, the function $f(x)$ turns out to admit a local decomposition $f(x) = \sum_{a=1}^R ψ_a(x_{S_a})$. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause $ψ_a(\cdot)$, which can be computationally much cheaper than the queries to $f(x)$ itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using $\widetilde{O}(\sqrtκd)$ local queries, where $κ$ is the condition number. This improves the prior best classical result $\widetilde{O}(κd)$ due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result $\widetilde{O}(\sqrtκ d^2)$ implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.

Related papers

Quantum Algorithms for Gibbs Expectation of Non-log-concave and Heavy-tailed Distributions

Xinmiao Li, Jin-Peng Liu

quant-pharXiv:2604.00656Apr 2, 20260 citations

Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants

Andrew M. Childs, Tongyang Li, Jin-Peng Liu +2 more

arXiv:2210.06539neural information processing systemsJan 1, 20220 citations

Quantum algorithm for Markov random fields structure learning

Liming Zhao, Ming-Xing Luo, Lin‐Chun Wan

Physica ScriptaJun 26, 20251 citation

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

quant-pharXiv:2609.35660Sep 29, 20260 citations

Sample-efficient learning of quantum many-body systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara +1 more

Annual Symposium on Foundations of Computer ScienceNov 1, 202010 citations

Quantum algorithm for the gradient of a logarithm-determinant

Thomas E. Baker, Jaimie Greasley

arXiv:2501.09413Jan 16, 20250 citations

arXiv:2609.20253

Quantum Speedups for Log-Concave Sampling from Local Structure

Chenghua Liu, Qisheng Wang, Zhengfeng Ji

quant-phcs.DSSubmitted Aug 14, 2026• Announced Aug 17, 2026• 0 citations

arXiv HTML PDF

Abstract

For a convex function

f \colon \mathbb{R}^d \to \mathbb{R}

, the problem of sampling from a distribution proportional to

e^{-f(x)}

is called log-concave sampling. In many practical scenarios, the function

f(x)

turns out to admit a local decomposition

f(x) = \sum_{a=1}^R ψ_a(x_{S_a})

. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause

ψ_a(\cdot)

, which can be computationally much cheaper than the queries to

f(x)

itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using

\widetilde{O}(\sqrtκd)

local queries, where

κ

is the condition number. This improves the prior best classical result

\widetilde{O}(κd)

due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result

\widetilde{O}(\sqrtκ d^2)

implied by Childs et al. (NeurIPS 2022). Our quantum sampler applies to a broad class of locally structured models from statistical computing and machine learning, with representative examples including Gaussian Markov random fields, finite-element latent Gaussian models, and sparse generalized linear models. These results demonstrate that local structure is not merely an implementation detail, but a quantum algorithmic resource for high-dimensional sampling.

Related papers

Quantum Algorithms for Gibbs Expectation of Non-log-concave and Heavy-tailed Distributions

Xinmiao Li, Jin-Peng Liu

We establish a systematic framework of unbiased quantum sampling and estimation protocols for the classical Gibbs expectation. This framework generalizes existing approaches to the partition function estimation and has broader applications in various fields. We consider sampling and estimation for a wide class of non-log-concave distributions, particularly heavy-tailed ones, under relaxed assumptions beyond strong convexity, such as dissipativity. We develop an unbiased extension of quantum-accelerated multilevel Monte Carlo (QA-MLMC) to eliminate all biases from discretization and time truncation, together with introducing a change-of-measure approach and the Girsanov theorem via Radon-Nikodym derivatives. As a result, our approach achieves quantum complexity $\widetilde{\mathcal{O}}(ε^{-1})$ within error $ε$ , whereas the classical MLMC requires $\widetilde{\mathcal{O}}(ε^{-2})$ and existing quantum algorithms yield biased estimators under stronger assumptions. Furthermore, our unified framework enables unbiased quantum sampling and estimation for certain heavy-tailed distributions after transformation. We provide several concrete applications of our approach in statistics, machine learning, and finance, towards more practical scenarios of the quantum acceleration of stochastic processes.We establish a systematic framework of unbiased quantum sampling and estimation protocols for the classical Gibbs expectation. This framework generalizes existing approaches to the partition function estimation and has broader applications in various fields. We consider sampling and estimation for a wide class of non-log-concave distributions, particularly heavy-tailed ones, under relaxed assumptions beyond strong convexity, such as dissipativity. We develop an unbiased extension of quantum-accelerated multilevel Monte Carlo (QA-MLMC) to eliminate all biases from discretization and time truncation, together with introducing a change-of-measure approach and the Girsanov theorem via Radon-Nikodym derivatives. As a result, our approach achieves quantum complexity $\widetilde{\mathcal{O}}(ε^{-1})$ within error $ε$, whereas the classical MLMC requires $\widetilde{\mathcal{O}}(ε^{-2})$ and existing quantum algorithms yield biased estimators under stronger assumptions. Furthermore, our unified framework enables unbiased quantum sampling and estimation for certain heavy-tailed distributions after transformation. We provide several concrete applications of our approach in statistics, machine learning, and finance, towards more practical scenarios of the quantum acceleration of stochastic processes.

quant-pharXiv:2604.00656Apr 2, 20260 citations

Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants

Andrew M. Childs, Tongyang Li, Jin-Peng Liu +2 more

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 $κ$ 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 $ε$ . Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity $\widetilde{O}(κ^{1/2}d)$ and $\widetilde{O}(κ^{1/2}d^{3/2}/ε)$ for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in $κ,d,ε$ over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/ε^{1-o(1)}$ quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in $ε$ .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 $κ$ 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 $ε$. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity $\widetilde{O}(κ^{1/2}d)$ and $\widetilde{O}(κ^{1/2}d^{3/2}/ε)$ for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in $κ,d,ε$ over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a $1/ε^{1-o(1)}$ quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in $ε$.

arXiv:2210.06539neural information processing systemsJan 1, 20220 citations

Quantum algorithm for Markov random fields structure learning

Liming Zhao, Ming-Xing Luo, Lin‐Chun Wan

Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. We propose a quantum algorithm for structure learning of an r-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.Abstract Probabilistic graphical models play a crucial role in machine learning and have wide applications across various fields. A pivotal subset within this realm is undirected graphical models, also known as Markov random fields. In this work, we explore the application of quantum computing to the field of machine learning, specifically focusing on the task of structure learning in Markov random fields. We propose a quantum algorithm for structure learning of an r-wise Markov Random Field with a bounded degree underlying graph, based on a nearly optimal classical greedy algorithm. Our quantum algorithm provides a polynomial speed-up over the classical counterpart, with a runtime of O ˜ 2 L M n r + 1 log ( 1 / w ) compared to the classical O ˜ M n r , where n is the number of variables. It is nearly a quadratic speedup in terms of n. Through this research, we aim to showcase the potential advantages of quantum computation in tackling complex machine-learning problems. Furthermore, the sample complexity O ˜ 2 2 L τ 2 δ 2 L ( log ( 1 / w ) + log n ) remains consistent between classical and quantum approaches, ensuring the efficiency and robustness of our method. By demonstrating the efficiency and scalability of our quantum algorithm for structure learning, we contribute to the growing body of work that highlights the role of quantum computing in advancing the field of machine learning and probabilistic graphical models.

Physica ScriptaJun 26, 20251 citation

An Optimal Quantum Linear Systems Algorithm

Carlos Bravo-Prieto, Aram W. Harrow, Robin Kothari

In the quantum linear systems problem (QLSP), we are given query access to a $d$ -sparse $N\times N$ matrix $A$ with condition number $κ$ , and the ability to prepare a quantum state proportional to a vector $\vec b$ . The goal is to output an $ε$ -approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$ . Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$ , while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$ . We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$ . We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.In the quantum linear systems problem (QLSP), we are given query access to a $d$-sparse $N\times N$ matrix $A$ with condition number $κ$, and the ability to prepare a quantum state proportional to a vector $\vec b$. The goal is to output an $ε$-approximation to the quantum state proportional to the solution $\vec x$ of $A\vec{x}=\vec{b}$. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities $O(κd\log(1/ε))$ and $κ\sqrt d(κd/ε)^{o(1)}$, while the best known lower bounds were $Ω(κ\log(1/ε))$ and $Ω(κ\sqrt d)$. We improve these bounds and show that the complexity of the QLSP is $Θ(κ\sqrt d\log(1/ε))$. We also resolve an open problem of Berry and Childs by showing that any $N\times N$ unitary can be implemented with bounded error using $O(\sqrt N)$ queries to its matrix entries.

quant-pharXiv:2609.35660Sep 29, 20260 citations

Sample-efficient learning of quantum many-body systems

Anurag Anshu, Srinivasan Arunachalam, Tomotaka Kuwahara +1 more

We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.We study the problem of learning the Hamiltonian of a quantum many-body system given samples from its Gibbs (thermal) state. The classical analog of this problem, known as learning graphical models or Boltzmann machines, is a well-studied question in machine learning and statistics. In this work, we give the first sample-efficient algorithm for the quantum Hamiltonian learning problem. In particular, we prove that polynomially many samples in the number of particles (qudits) are necessary and sufficient for learning the parameters of a spatially local Hamiltonian in l_2-norm. Our main contribution is in establishing the strong convexity of the log-partition function of quantum many-body systems, which along with the maximum entropy estimation yields our sample-efficient algorithm. Classically, the strong convexity for partition functions follows from the Markov property of Gibbs distributions. This is, however, known to be violated in its exact form in the quantum case. We introduce several new ideas to obtain an unconditional result that avoids relying on the Markov property of quantum systems, at the cost of a slightly weaker bound. In particular, we prove a lower bound on the variance of quasi-local operators with respect to the Gibbs state, which might be of independent interest. Our work paves the way toward a more rigorous application of machine learning techniques to quantum many-body problems.

Annual Symposium on Foundations of Computer ScienceNov 1, 202010 citations

Quantum algorithm for the gradient of a logarithm-determinant

Thomas E. Baker, Jaimie Greasley

The logarithm-determinant is a widely-present operation in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the pseudo-inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N^2$ elements of the input operator--can be accomplished in $O(k/\varepsilon^2)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix with precision $\varepsilon$ . A practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O((k\log_2 N)/\varepsilon^2)$ . The method applies widely and converges super-linearly in $k$ when the condition number is high. The best classical method we are aware of scales as $N$ . Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as $O(\log_2 N/\varepsilon^2)$ . The output is given in $O(1)$ queries of an oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning.The logarithm-determinant is a widely-present operation in many areas of physics and computer science. Derivatives of the logarithm-determinant compute physically relevant quantities in statistical physics models, quantum field theories, as well as the inverses of matrices. A multi-variable version of the quantum gradient algorithm is developed here to evaluate the derivative of the logarithm-determinant. From this, the pseudo-inverse of a sparse-rank input operator may be determined efficiently. Measuring an expectation value of the quantum state--instead of all $N^2$ elements of the input operator--can be accomplished in $O(k/\varepsilon^2)$ time in the idealized case for $k$ relevant eigenvectors of the input matrix with precision $\varepsilon$. A practical implementation of the required operator will likely need $\log_2N$ overhead, giving an overall complexity of $O((k\log_2 N)/\varepsilon^2)$. The method applies widely and converges super-linearly in $k$ when the condition number is high. The best classical method we are aware of scales as $N$. Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as $O(\log_2 N/\varepsilon^2)$. The output is given in $O(1)$ queries of an oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning.

arXiv:2501.09413Jan 16, 20250 citations

For a convex function

f \colon \mathbb{R}^d \to \mathbb{R}

, the problem of sampling from a distribution proportional to

e^{-f(x)}

is called log-concave sampling. In many practical scenarios, the function

f(x)

turns out to admit a local decomposition

f(x) = \sum_{a=1}^R ψ_a(x_{S_a})

. In this paper, we consider log-concave sampling using local queries, i.e., evaluation and gradient queries to each clause

ψ_a(\cdot)

, which can be computationally much cheaper than the queries to

f(x)

itself. We show that if each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using

\widetilde{O}(\sqrtκd)

local queries, where

κ

is the condition number. This improves the prior best classical result

\widetilde{O}(κd)

due to Ascolani, Lavenant, and Zanella (Ann. Probab. 2026) and the quantum result

\widetilde{O}(\sqrtκ d^2)

\widetilde{\mathcal{O}}(ε^{-1})

within error

ε

, whereas the classical MLMC requires

\widetilde{\mathcal{O}}(ε^{-2})

and existing quantum algorithms yield biased estimators under stronger assumptions. Furthermore, our unified framework enables unbiased quantum sampling and estimation for certain heavy-tailed distributions after transformation. We provide several concrete applications of our approach in statistics, machine learning, and finance, towards more practical scenarios of the quantum acceleration of stochastic processes.

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

κ

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

ε

. Second, we develop quantum Metropolis-adjusted Langevin algorithms with query complexity

\widetilde{O}(κ^{1/2}d)

and

\widetilde{O}(κ^{1/2}d^{3/2}/ε)

for log-concave sampling and normalizing constant estimation, respectively, achieving polynomial speedups in

κ,d,ε

over the best known classical algorithms by exploiting quantum analogs of the Monte Carlo method and quantum walks. We also prove a

1/ε^{1-o(1)}

quantum lower bound for estimating normalizing constants, implying near-optimality of our quantum algorithms in

ε

In the quantum linear systems problem (QLSP), we are given query access to a

d

-sparse

N\times N

matrix

A

with condition number

κ

, and the ability to prepare a quantum state proportional to a vector

\vec b

. The goal is to output an

ε

-approximation to the quantum state proportional to the solution

\vec x

A\vec{x}=\vec{b}

. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities

O(κd\log(1/ε))

and

κ\sqrt d(κd/ε)^{o(1)}

, while the best known lower bounds were

Ω(κ\log(1/ε))

and

Ω(κ\sqrt d)

. We improve these bounds and show that the complexity of the QLSP is

Θ(κ\sqrt d\log(1/ε))

. We also resolve an open problem of Berry and Childs by showing that any

N\times N

unitary can be implemented with bounded error using

O(\sqrt N)

queries to its matrix entries.

N^2

elements of the input operator--can be accomplished in

O(k/\varepsilon^2)

time in the idealized case for

k

relevant eigenvectors of the input matrix with precision

\varepsilon

. A practical implementation of the required operator will likely need

\log_2N

overhead, giving an overall complexity of

O((k\log_2 N)/\varepsilon^2)

. The method applies widely and converges super-linearly in

k

when the condition number is high. The best classical method we are aware of scales as

N

. Given the same resource assumptions as other algorithms, such that an equal superposition of eigenvectors is available efficiently, the algorithm is evaluated in the practical case as

O(\log_2 N/\varepsilon^2)

. The output is given in

O(1)

queries of an oracle, which is given explicitly here and only relies on time-evolution operators that can be implemented with arbitrarily small error. The algorithm is envisioned for fully error-corrected quantum computers but may be implementable on near-term machines. We discuss how this algorithm can be used for kernel-based quantum machine-learning.