A Sublinear-Time Quantum Algorithm for High-Dimensional Reaction Rates

• URL: http://arxiv.org/abs/2601.15523v1
• Date: Wed, 21 Jan 2026 23:20:46 GMT
• Title: A Sublinear-Time Quantum Algorithm for High-Dimensional Reaction Rates
• Authors: Tyler Kharazi, Ahmad M. Alkadri, Kranthi K. Mandadapu, K. Birgitta Whaley,
• Abstract summary: We introduce an algorithm that overcomes the exponential decay in success probability of quantum algorithms for non-dimensional dynamics.<n>We also use this technique to directly estimate matrix elements without exponential decay.<n>While specialized classical dissipative algorithms may outperform these bounds in practice, this demonstrates a rigorous route toward quantum advantage.
• Score: 0.06524460254566902
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Fokker-Planck equation models rare events across sciences, but its high-dimensional nature challenges classical computers. Quantum algorithms for such non-unitary dynamics often suffer from exponential {decay in} success probability. We introduce a quantum algorithm that overcomes this for computing reaction rates. Using a sum-of-squares representation, we develop a Gaussian linear combination of Hamiltonian simulations (Gaussian-LCHS) to represent the non-unitary propagator with $O\left(\sqrt{t\|H\|\log(1/ε)}\right)$ queries to its block encoding. Crucially, we pair this with {a} novel technique to directly estimate matrix elements without exponential decay. For $η$ pairwise interacting particles discretized with $N$ plane waves per degree of freedom, we estimate reactive flux to error $ε$ using $\widetilde{O}\left((η^{5/2}\sqrt{tβ}α_V + η^{3/2}\sqrt{t/β}N)/ε\right)$ quantum gates, where $α_V = \max_{r}|V'(r)/r|$. For non-convex potentials, the {sharpest classical} worst-case analytical bounds to simulate the related overdamped Langevin {equation} scale as $O(te^{Ω(η)}/ε^4)$. This {implies} an exponential separation in particle number $η$, a quartic speedup in $ε$, and quadratic speedup in $t$. While specialized classical heuristics may outperform these bounds in practice, this demonstrates a rigorous route toward quantum advantage for high-dimensional dissipative dynamics.

Related papers

• Quantum Brownian motion with non-Gaussian noises: Fluctuation-Dissipation Relation and nonlinear Langevin equation [0.0]
  We consider the quantum Brownian motion (QBM) model with one oscillator as the system.<n>The influence action $S_IF$ is calculated using a perturbative expansion in $$.<n>The non-Gaussian noise kernel gives rise to non-zero three-point correlation function of the corresponding force.
  arXiv  Detail & Related papers  (2026-02-11T02:03:26Z)
• Transmutation based Quantum Simulation for Non-unitary Dynamics [35.35971148847751]
  We present a quantum algorithm for simulating dissipative diffusion dynamics generated by positive semidefinite operators of the form $A=Ldagger L$.<n>Our main tool is the Kannai transform, which represents the diffusion semigroup $e-TA$ as a Gaussian-weighted superposition of unitary wave propagators.
  arXiv  Detail & Related papers  (2026-01-07T05:47:22Z)
• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  In this work, we present a quantum algorithm which approximates values up to additive error $epsilonDelta_k$ using a logarithmic number of qubits.<n>A key technical step in the analysis is the preparation of a suitable random initial state, which ultimately allows us to efficiently count the number of eigenvalues that are smaller than a threshold.
  arXiv  Detail & Related papers  (2025-08-28T17:04:18Z)
• Quantum simulation of a noisy classical nonlinear dynamics [2.0065923589074735]
  We present an end-to-end quantum algorithm for simulating nonlinear dynamics described by a system of dissipative differential equations with a quadratic nonlinearity.<n>Our algorithm can approximate the expected value of any correlation function that depends on $O(1)$ variables with rigorous approximation error.<n>To the best of our knowledge, this is the first rigorous quantum algorithm capable of simulating strongly nonlinear systems with $Jgg lambda$ at the cost poly-logarithmic in $N$ and in $t$.
  arXiv  Detail & Related papers  (2025-07-08T17:25:40Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Quantum Simulation of Lindbladian Dynamics via Repeated Interactions [0.5097809301149342]
  We make use of an approximate correspondence between Lindbladian dynamics and evolution based on Repeated Interaction (RI) CPTP maps.<n>We show that the number of interactions needed to simulate the Liouvillian $etmathcalL$ within error $epsilon$ scales in a weak coupling limit.
  arXiv  Detail & Related papers  (2023-12-08T21:17:16Z)
• Quantum simulation of real-space dynamics [7.143485463760098]
  We conduct a systematic study of quantum algorithms for real-space dynamics. We give applications to several computational problems, including faster real-space simulation of quantum chemistry.
  arXiv  Detail & Related papers  (2022-03-31T13:01:51Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Anharmonic oscillator: a solution [77.34726150561087]
  The dynamics in $x$-space and in $(gx)-space corresponds to the same energy spectrum with effective coupling constant $hbar g2$. A 2-classical generalization leads to a uniform approximation of the wavefunction in $x$-space with unprecedented accuracy.
  arXiv  Detail & Related papers  (2020-11-29T22:13:08Z)
• Linear Time Sinkhorn Divergences using Positive Features [51.50788603386766]
  Solving optimal transport with an entropic regularization requires computing a $ntimes n$ kernel matrix that is repeatedly applied to a vector. We propose to use instead ground costs of the form $c(x,y)=-logdotpvarphi(x)varphi(y)$ where $varphi$ is a map from the ground space onto the positive orthant $RRr_+$, with $rll n$.
  arXiv  Detail & Related papers  (2020-06-12T10:21:40Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.