Nearly-frustration-free ground state preparation
- URL: http://arxiv.org/abs/2108.03249v2
- Date: Thu, 27 Jul 2023 18:26:22 GMT
- Title: Nearly-frustration-free ground state preparation
- Authors: Matthew Thibodeau, Bryan K. Clark
- Abstract summary: Solving for quantum ground states is important for understanding the properties of quantum many-body systems.
Recent work has presented a nearly optimal scheme that prepares ground states on a quantum computer for completely generic Hamiltonians.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Solving for quantum ground states is important for understanding the
properties of quantum many-body systems, and quantum computers are potentially
well-suited for solving for quantum ground states. Recent work has presented a
nearly optimal scheme that prepares ground states on a quantum computer for
completely generic Hamiltonians, whose query complexity scales as
$\delta^{-1}$, i.e. inversely with their normalized gap. Here we consider
instead the ground state preparation problem restricted to a special subset of
Hamiltonians, which includes those which we term "nearly-frustration-free": the
class of Hamiltonians for which the ground state energy of their block-encoded
and hence normalized Hamiltonian $\alpha^{-1}H$ is within $\delta^y$ of -1,
where $\delta$ is the spectral gap of $\alpha^{-1}H$ and $0 \leq y \leq 1$. For
this subclass, we describe an algorithm whose dependence on the gap is
asymptotically better, scaling as $\delta^{y/2-1}$, and show that this new
dependence is optimal up to factors of $\log \delta$. In addition, we give
examples of physically motivated Hamiltonians which live in this subclass.
Finally, we describe an extension of this method which allows the preparation
of excited states both for generic Hamiltonians as well as, at a similar
speedup as the ground state case, for those which are nearly frustration-free.
Related papers
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
We present a quantum generalization of these tools through a generic bottleneck lemma.
This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.
Even with sublinear barriers, we use Feynman-Kac techniques to lift classical to quantum ones establishing tight lower bound $T_mathrmmix = 2Omega(nalpha)$.
arXiv Detail & Related papers (2024-11-06T22:51: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) - Quasi-quantum states and the quasi-quantum PCP theorem [0.21485350418225244]
We show that solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP.
Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result.
arXiv Detail & Related papers (2024-10-17T13:43:18Z) - Preparing angular momentum eigenstates using engineered quantum walks [1.0232954388448414]
We develop a quantum-walk scheme that does not require inputting $O(j)$ nonzero Clebsch-Gordan (CG) coefficients classically.
Our scheme prepares angular momentum eigenstates using a sequence of Hamiltonians to move an initial state deterministically to desired final states.
We test our state preparation scheme on classical computers, reproducing CG coefficients, and implement small test problems on current quantum hardware.
arXiv Detail & Related papers (2024-08-26T23:20:00Z) - Beating Grover search for low-energy estimation and state preparation [0.23034630097498876]
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics.
In this work, we give quantum algorithms which, given any $k$-body Hamiltonian $H$, compute an estimate for the ground state energy.
arXiv Detail & Related papers (2024-07-03T12:47:06Z) - 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) - A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
We give a quantum algorithm for solving the ground states of a class of Hamiltonians.
The mechanism of the exponential speedup that appeared in our algorithm comes from dissipation in open quantum systems.
arXiv Detail & Related papers (2024-01-25T05:01:02Z) - 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) - Complexity of the Guided Local Hamiltonian Problem: Improved Parameters
and Extension to Excited States [0.0]
We show that the so-called guided local Hamiltonian problem remains BQP-complete when the Hamiltonian is 2-local.
We improve upon this result by showing that it remains BQP-complete when i) the Hamiltonian is 2-local, ii) the overlap between the guiding state and target eigenstate is as large as $1.
arXiv Detail & Related papers (2022-07-20T18: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)
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.