Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians

• URL: http://arxiv.org/abs/2004.08681v3
• Date: Wed, 21 Oct 2020 20:11:24 GMT
• Title: Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Abstract summary: We present a classical algorithm to efficiently sample from the effective subspace of a $k$-local stoquastic Hamiltonian $H$. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in $k$-local Hamiltonians.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: All known examples confirming the possibility of an exponential separation between classical simulation algorithms and stoquastic adiabatic quantum computing (AQC) exploit symmetries that constrain adiabatic dynamics to effective, symmetric subspaces. The symmetries produce large effective eigenvalue gaps, which in turn make adiabatic computation efficient. We present a classical algorithm to efficiently sample from the effective subspace of a $k$-local stoquastic Hamiltonian $H$, without a priori knowledge of its symmetries (or near-symmetries). Our algorithm maps any $k$-local Hamiltonian to a graph $G=(V,E)$ with $\lvert V \rvert = O\left(\mathrm{poly}(n)\right)$ where $n$ is the number of qubits. Given the well-known result of Babai, we exploit graph isomorphism to study the automorphisms of $G$ and arrive at an algorithm quasi-polynomial in $\lvert V\rvert$ for producing samples from the effective subspace eigenstates of $H$. Our results rule out exponential separations between stoquastic AQC and classical computation that arise from hidden symmetries in $k$-local Hamiltonians. Furthermore, our graph representation of $H$ is not limited to stoquastic Hamiltonians and may rule out corresponding obstructions in non-stoquastic cases, or be useful in studying additional properties of $k$-local Hamiltonians.

Related papers

• The Hamilton-Jacobi Theory of Deep Learning [0.0]
  Training a neural network is identified, exactly, as a search through Hamilton--Jacobi initial-value problems.<n>The correspondence is exact for log-sum-exp layers and structural for broader architectures.
  arXiv  Detail & Related papers  (2026-05-27T18:38:23Z)
• 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)
• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Second quantization for classical nonlinear dynamics [0.0]
  We propose a framework for representing the evolution of observables of measure-preserving ergodic flows through infinite-dimensional rotation systems on tori. We show that their Banach algebra spectra, $sigma(F_w(mathcal H_tau)$, decompose into a family of tori of potentially infinite dimension. Our scheme also employs a procedure for representing observables of the original system by reproducing functions on finite-dimensional tori in $sigma(F_w(mathcal H_tau)$ of arbitrarily large degree.
  arXiv  Detail & Related papers  (2025-01-13T15:36:53Z)
• New random compiler for Hamiltonians via Markov Chains [0.07499722271664146]
  We develop a new compiler, similar to the first order randomized Trotter, or qDRIFT, but with an arguably simpler framework. We first present the model and derive its governing equations. We then define and analyze the simulation error for a sum of two Hamiltonians, and generalize it to a sum of $Q$ Hamiltonians.
  arXiv  Detail & Related papers  (2024-11-10T14:57:25Z)
• Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
  We use the Nauty package to identify graph automorphisms, focusing on determining edge equivalence classes. By exploiting these symmetries, we achieve a significant reduction in the complexity of the Hamiltonian. Our results show that using automorphism-based symmetries to reduce the Pauli terms in the Hamiltonian can significantly decrease computational overhead without compromising the quality of the solutions obtained.
  arXiv  Detail & Related papers  (2024-10-29T17:10:25Z)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
  arXiv  Detail & Related papers  (2024-05-28T18:00:32Z)
• Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
  We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
  arXiv  Detail & Related papers  (2024-04-04T17:58:01Z)
• Composite QDrift-Product Formulas for Quantum and Classical Simulations in Real and Imaginary Time [0.18374319565577155]
  Recent work has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian $H$ for a given simulation problem into subsets. We show that this approach holds in imaginary time, making it a candidate classical algorithm for quantum Monte-Carlo calculations. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form $e-iH_j t$ and $e-H_j beta$ to meet a certain error tolerance.
  arXiv  Detail & Related papers  (2023-06-28T21:31:26Z)
• Learning quantum symmetries with interactive quantum-classical variational algorithms [0.0]
  A symmetry of a state $vert psi rangle$ is a unitary operator of which $vert psi rangle$ is an eigenvector. symmetries provide key physical insight into the quantum system. We develop a variational hybrid quantum-classical learning scheme to systematically probe for symmetries of $vert psi rangle$.
  arXiv  Detail & Related papers  (2022-06-23T20:41:26Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• 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)
• Hybridized Methods for Quantum Simulation in the Interaction Picture [69.02115180674885]
  We provide a framework that allows different simulation methods to be hybridized and thereby improve performance for interaction picture simulations. Physical applications of these hybridized methods yield a gate complexity scaling as $log2 Lambda$ in the electric cutoff. For the general problem of Hamiltonian simulation subject to dynamical constraints, these methods yield a query complexity independent of the penalty parameter $lambda$ used to impose an energy cost.
  arXiv  Detail & Related papers  (2021-09-07T20:01:22Z)
• Quantum algorithm for time-dependent Hamiltonian simulation by permutation expansion [6.338178373376447]
  We present a quantum algorithm for the dynamical simulation of time-dependent Hamiltonians. We demonstrate that the cost of the algorithm is independent of the Hamiltonian's frequencies.
  arXiv  Detail & Related papers  (2021-03-29T05:02:02Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)
• Learning Halfspaces with Tsybakov Noise [50.659479930171585]
  We study the learnability of halfspaces in the presence of Tsybakov noise. We give an algorithm that achieves misclassification error $epsilon$ with respect to the true halfspace.
  arXiv  Detail & Related papers  (2020-06-11T14:25:02Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  We provide the first non-asymptotic analysis for finding stationary points of nonsmooth, nonsmooth functions. In particular, we study Hadamard semi-differentiable functions, perhaps the largest class of nonsmooth functions.
  arXiv  Detail & Related papers  (2020-02-10T23:23:04Z)

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.