Lower Bounds on Quantum Annealing Times

• URL: http://arxiv.org/abs/2210.15687v3
• Date: Wed, 5 Apr 2023 18:20:12 GMT
• Title: Lower Bounds on Quantum Annealing Times
• Authors: Luis Pedro Garc\'ia-Pintos, Lucas T. Brady, Jacob Bringewatt, Yi-Kai Liu
• Abstract summary: The adiabatic theorem provides sufficient conditions for the time needed to prepare a target ground state. We provide such a result, deriving lower bounds on the time needed to successfully perform quantum annealing. Our results also show that rapid annealing requires coherent superpositions of energy eigenstates, singling out quantum coherence as a computational resource.
• Score: 1.4528756508275618
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The adiabatic theorem provides sufficient conditions for the time needed to prepare a target ground state. While it is possible to prepare a target state much faster with more general quantum annealing protocols, rigorous results beyond the adiabatic regime are rare. Here, we provide such a result, deriving lower bounds on the time needed to successfully perform quantum annealing. The bounds are asymptotically saturated by three toy models where fast annealing schedules are known: the Roland and Cerf unstructured search model, the Hamming spike problem, and the ferromagnetic p-spin model. Our bounds demonstrate that these schedules have optimal scaling. Our results also show that rapid annealing requires coherent superpositions of energy eigenstates, singling out quantum coherence as a computational resource.

Related papers

• Controlled Diagonal Catalyst Improves the Efficiency of Quantum Annealing [1.342834401139078]
  We propose a method for efficiently solving instances with small energy gaps by introducing additional local terms to the Hamiltonian. The proposed method achieves an approximate square speed up in time-to-solution compared to the conventional quantum annealing.
  arXiv  Detail & Related papers  (2025-03-19T14:20:38Z)
• Adiabatic quantum unstructured search in parallel [0.0]
  We present an optimized adiabatic quantum schedule for unstructured search building. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time. Our findings suggest that quantum advantage may still be achievable under constrained coherence times.
  arXiv  Detail & Related papers  (2025-02-12T17:32:27Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Constant-Time Quantum Search with a Many-Body Quantum System [39.58317527488534]
  We consider a many-body quantum system that naturally effects parallel queries. We show that its parameters can be tuned to search a database in constant time.
  arXiv  Detail & Related papers  (2024-08-09T22:57:59Z)
• Quantum computational advantage with constant-temperature Gibbs sampling [1.1930434318557157]
  A quantum system coupled to a bath at some fixed, finite temperature converges to its Gibbs state. This thermalization process defines a natural, physically-motivated model of quantum computation. We consider sampling from the measurement outcome distribution of quantum Gibbs states at constant temperatures.
  arXiv  Detail & Related papers  (2024-04-23T00:29:21Z)
• Spatiotemporal Quenches for Efficient Critical Ground State Preparation in Two-Dimensional Quantum Systems [0.0]
  We show the effectiveness of quenches in rapidly preparing ground states in critical phases. Our simulations reveal the existence of an optimal quench front velocity at the emergent speed of light. These findings emphasize the potential of quenchtemporal quenches efficient ground state preparation in quantum systems.
  arXiv  Detail & Related papers  (2024-04-03T18:00:01Z)
• State Preparation in a Jaynes-Cummings Lattice with Quantum Optimal Control [2.8063310156671477]
  We study a quantum optimal control (QOC) approach for fast generation of quantum ground states in a finite-sized Jaynes-Cummings lattice with unit filling. Our result shows that the QOC approach can generate quantum many-body states with high fidelity when the evolution time is above a threshold time.
  arXiv  Detail & Related papers  (2023-06-21T01:44:57Z)
• Robust Extraction of Thermal Observables from State Sampling and Real-Time Dynamics on Quantum Computers [49.1574468325115]
  We introduce a technique that imposes constraints on the density of states, most notably its non-negativity, and show that this way, we can reliably extract Boltzmann weights from noisy time series. Our work enables the implementation of the time-series algorithm on present-day quantum computers to study finite temperature properties of many-body quantum systems.
  arXiv  Detail & Related papers  (2023-05-30T18:00:05Z)
• Quantum Thermal State Preparation [39.91303506884272]
  We introduce simple continuous-time quantum Gibbs samplers for simulating quantum master equations. We construct the first provably accurate and efficient algorithm for preparing certain purified Gibbs states. Our algorithms' costs have a provable dependence on temperature, accuracy, and the mixing time.
  arXiv  Detail & Related papers  (2023-03-31T17:29:56Z)
• Sparse random Hamiltonians are quantumly easy [105.6788971265845]
  A candidate application for quantum computers is to simulate the low-temperature properties of quantum systems. This paper shows that, for most random Hamiltonians, the maximally mixed state is a sufficiently good trial state. Phase estimation efficiently prepares states with energy arbitrarily close to the ground energy.
  arXiv  Detail & Related papers  (2023-02-07T10:57:36Z)
• Probing finite-temperature observables in quantum simulators of spin systems with short-time dynamics [62.997667081978825]
  We show how finite-temperature observables can be obtained with an algorithm motivated from the Jarzynski equality. We show that a finite temperature phase transition in the long-range transverse field Ising model can be characterized in trapped ion quantum simulators.
  arXiv  Detail & Related papers  (2022-06-03T18:00:02Z)
• Quantum and classical annealing in a continuous space with multiple local minima [0.0]
  We show that quantum annealing yields a power law convergence, thus an exponential improvement over simulated annealing. We also reveal how diabatic quantum dynamics, quantum tunneling in particular, steers the systems toward the global minimum.
  arXiv  Detail & Related papers  (2022-03-22T02:02:23Z)
• Performance Evaluation of Adiabatic Quantum Computation via Quantum Speed Limits and Possible Applications to Many-Body Systems [0.0]
  We find a bound of the fidelity between the adiabatic state and the time-evolved state. The bound is characterized by the counterdiabatic Hamiltonian. We derive a different type of quantum speed limits that is meaningful even when we take the thermodynamic limit.
  arXiv  Detail & Related papers  (2019-12-27T04:12:49Z)

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.