Quantum advantage from random geometrically-two-local Hamiltonian dynamics

• URL: http://arxiv.org/abs/2510.06321v1
• Date: Tue, 07 Oct 2025 18:00:02 GMT
• Title: Quantum advantage from random geometrically-two-local Hamiltonian dynamics
• Authors: Yihui Quek,
• Abstract summary: We develop the first worst-to-average-case reduction for approximating output probabilities of geometrically-2-local Hamiltonian evolutions.<n>We also contribute an algorithmic version of Berlekamp-Welch to deal with errored evaluations.
• Score: 1.3537117504260623
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classical hardness-of-sampling results are largely established for random quantum circuits, whereas analog simulators natively realize time evolutions under geometrically local Hamiltonians. Does a typical such Hamiltonian already yield classically-intractable dynamics? We answer this question in the affirmative for the ensemble of geometrically-2-local Hamiltonians with Gaussian coefficients, evolved for constant time. This naturally leads to a quantum advantage scheme with clear prospects for experimental realization, necessitating only course-grained control. We give strong evidence of hardness for this physically-relevant ensemble. We develop the first worst-to-average-case reduction for approximating output probabilities of (time-independent) geometrically-2-local Hamiltonian evolutions. Our reduction proceeds by nonstandard means: while we also leverage polynomial interpolation, unlike previous works, we reduce directly to an evaluator for the exact distribution over Hamiltonians, from which we are trying to prove that sampling is hard. Previous works instead sampled from various perturbations of the true distribution, introducing additional constraints meant to keep the perturbation, measured in total variation distance, under control. We dispense with this step. Our reduction consists in a robust multivariate polynomial interpolation, reduced to sequential robust univariate interpolations via the symmetries of the Gaussian. We circumvent the fact that random Hamiltonians lack a hiding symmetry, a key property in previous proofs. We also contribute an algorithmic version of Berlekamp-Welch to deal with errored evaluations, solving an open problem from the RCS literature. We expect the machinery we develop to find use in average-case Hamiltonian complexity, filling in a gap in this literature which has thus far focussed on worst-case hardness results.

Related papers

• Ancilla-Free Fast-Forwarding Lindbladian Simulation Algorithms by Hamiltonian Twirling [2.8802622551493773]
  We show that the time-$t$ evolution map can be expressed exactly a Gaussian twirl over the unitary orbit $mathrme-mathrmi Hs_sinmathbbR$.<n>This structural insight allows us to design a fast-forwarding algorithm for Lindbladian simulation.
  arXiv  Detail & Related papers  (2025-11-13T12:39:18Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Optimizing fermionic Hamiltonians with classical interactions [0.0509780930114934]
  We consider the optimization problem (ground energy search) for fermionic Hamiltonians with classical interactions.<n>We prove that fermionic Gaussian states achieve an approximation ratio of at least 1/3 for such Hamiltonians, independent of sparsity.
  arXiv  Detail & Related papers  (2025-10-02T15:31:55Z)
• Lower Bounds for Learning Hamiltonians from Time Evolution [5.118083299467833]
  We consider the problem of learning Hamiltonians from time evolution.<n>We show that any learning algorithm with inverse time resolution requires super-polynomial total evolution time.
  arXiv  Detail & Related papers  (2025-09-25T01:50:55Z)
• 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)
• Shot-noise reduction for lattice Hamiltonians [0.7852714805965528]
  Efficiently estimating energy expectation values of lattice Hamiltonians on quantum computers is a serious challenge. We introduce geometric partitioning as a scalable alternative. We show how the sampling number improvement translates to imperfect eigenstate improvements.
  arXiv  Detail & Related papers  (2024-10-28T17:50:28Z)
• Bayesian Circular Regression with von Mises Quasi-Processes [57.88921637944379]
  In this work we explore a family of expressive and interpretable distributions over circle-valued random functions.<n>For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Gibbs sampling.<n>We present experiments applying this model to the prediction of wind directions and the percentage of the running gait cycle as a function of joint angles.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Spectral form factor in a minimal bosonic model of many-body quantum chaos [1.3793594968500609]
  We study spectral form factor in periodically-kicked bosonic chains. We numerically find a nontrivial systematic system-size dependence of the Thouless time.
  arXiv  Detail & Related papers  (2022-03-10T15:56:24Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Hamiltonian simulation with random inputs [74.82351543483588]
  Theory of average-case performance of Hamiltonian simulation with random initial states. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models.
  arXiv  Detail & Related papers  (2021-11-08T19:08:42Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  Unitary evolution under a time dependent Hamiltonian is a key component of simulation on quantum hardware. We present an algorithm that compresses the Trotter steps into a single block of quantum gates. This results in a fixed depth time evolution for certain classes of Hamiltonians.
  arXiv  Detail & Related papers  (2021-08-06T19:38:01Z)

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.