We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-\beta E}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $\alpha=e^{\beta\Delta}$, where $\Delta = \max E-\min E$, every classical algorithm querying the value, gradient, or any higher-order derivatives of the log-density requires $\Omega(\alpha)$ queries to sample at constant accuracy in total variation distance, while a quantum algorithm based on quantum singular value thresholding and temperature annealing samples with $\tilde{O}\left(\sqrt{\alpha}\right)$ queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, $e^{\Omega(d)}$, at low temperature. The classical bound is information-theoretic, holding for every classical algorithm with query access to the Gibbs potential and its derivatives at any order.
If each coordinate appears in only a small number of clauses, there is a quantum algorithm for strongly log-concave sampling using local queries using $\widetilde{O}(\sqrt{\kappa}d)$ local queries, where $\kappa$ is the condition number.
The argument reduces any $N$-query circuit to the approximation of $e^{it\theta}$ by a trigonometric polynomial with degree bounded by $O(N)$ by a trigonometric polynomial with degree bounded by $O(N)$ together with Remez inequality to establish a matching lower bound for arbitrary query algorithms.
A. Liu, Adam Wesołowski, Jayne Thompson et al.· 0 citations
Let $\pi(\mathrm{d} x)\propto e^{-U(x)}\, \mathrm{d} x$ on $\mathbb{R}^d$, where $U$ is continuously differentiable and $m$-strongly convex with a globally $L$-Lipschitz gradient, $0<m\leq L<\infty$, and $\kappa=L/m$. Fixed-step Metropolis-adjusted Langevin algorithm (MALA) has known warm-start mixing-time upper bounds...
We prove a $\beta^{2}$ area law for the quantum mutual information of thermal states of local lattice Hamiltonians: for any bipartitioning $A|B$ and all inverse temperatures $\beta$ below a critical value $\beta^{*}$, we show $\mathcal{I}_{\beta}(A,B) \leqslant \tilde{f}(\beta)\, \beta^{2}\,|\partial_{AB}|$, where $|\p...
An upper bound of $\tilde{O}\!\big(\frac{\rho}}{\Delta\epsilon}+\frac{1}{\Delta\sqrt{\epsilon}}\big)$ queries is proved for quantum counting with bounded-error oracles, achieving a quadratic speedup over the classical sample complexity.
A one-query transducer that implements a product of rational approximations to short-time evolution when supplied with a catalyst, and bound the error from omitting the catalyst by exploiting orthogonality between different sequences of Kraus labels.
Bo-Yang Chen, Min-Bo Gao, Xin-Zhao Wang et al.· 6 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.