An efficient and exact noncommutative quantum Gibbs sampler
- URL: http://arxiv.org/abs/2311.09207v1
- Date: Wed, 15 Nov 2023 18:51:24 GMT
- Title: An efficient and exact noncommutative quantum Gibbs sampler
- Authors: Chi-Fang Chen, Michael J. Kastoryano, Andr\'as Gily\'en
- Abstract summary: We construct the first efficiently implementable and exactly detailed-balanced Lindbladian for Gibbs states of arbitrary noncommutative Hamiltonians.
Our construction can also be regarded as a continuous-time quantum analog of the Metropolis-Hastings algorithm.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Preparing thermal and ground states is an essential quantum algorithmic task
for quantum simulation. In this work, we construct the first efficiently
implementable and exactly detailed-balanced Lindbladian for Gibbs states of
arbitrary noncommutative Hamiltonians. Our construction can also be regarded as
a continuous-time quantum analog of the Metropolis-Hastings algorithm. To
prepare the quantum Gibbs state, our algorithm invokes Hamiltonian simulation
for a time proportional to the mixing time and the inverse temperature $\beta$,
up to polylogarithmic factors. Moreover, the gate complexity reduces
significantly for lattice Hamiltonians as the corresponding Lindblad operators
are (quasi-) local (with radius $\sim\beta$) and only depend on local
Hamiltonian patches. Meanwhile, purifying our Lindbladians yields a
temperature-dependent family of frustration-free "parent Hamiltonians",
prescribing an adiabatic path for the canonical purified Gibbs state (i.e., the
Thermal Field Double state). These favorable features suggest that our
construction is the ideal quantum algorithmic counterpart of classical Markov
chain Monte Carlo sampling.
Related papers
- Mixing time of quantum Gibbs sampling for random sparse Hamiltonians [0.23020018305241333]
A newly developed quantum Gibbs sampling algorithm by Chen, Kastoryano, and Gily'en provides an efficient simulation of non-commutative quantum systems.
We establish a polylog(n) upper bound on its mixing time for various families of random n by n sparse Hamiltonians at any constant temperature.
Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.
arXiv Detail & Related papers (2024-11-07T06:01:19Z) - 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) - 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) - 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) - 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) - Parallel Quantum Algorithm for Hamiltonian Simulation [9.680246554758343]
A parallel quantum algorithm is proposed for simulating the dynamics of a large class of Hamiltonians.
The running time of our parallel quantum simulation algorithm measured by the quantum circuit depth has a doubly (poly-)logarithmic dependence.
We show that the total gate depth of our algorithm has a $operatornamepolyloglog (1/epsilon)$ dependence in the parallel setting.
arXiv Detail & Related papers (2021-05-25T12:46:33Z) - Dynamical Self-energy Mapping (DSEM) for quantum computing [0.0]
For noisy intermediate-scale quantum (NISQ) devices only a moderate number of qubits with a limited coherence is available.
We present how to bypass this challenge in practical molecular chemistry simulations on NISQ devices by employing a classical-quantum hybrid algorithm.
arXiv Detail & Related papers (2020-10-12T04:12:21Z) - 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.