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
- 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) - Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent [37.59299233291882]
We propose Q-Newton, a hybrid quantum-classical scheduler for accelerating neural network training with Newton's GD.
Q-Newton utilizes a streamlined scheduling module that coordinates between quantum and classical linear solvers.
Our evaluation showcases the potential for Q-Newton to significantly reduce the total training time compared to commonly used quantum machines.
arXiv Detail & Related papers (2024-04-30T23:55:03Z) - 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) - Parent Hamiltonian Reconstruction via Inverse Quantum Annealing [0.0]
Finding a local Hamiltonian $hatmathcalH$ having a given many-body wavefunction $|psirangle$ as its ground state, i.e. a parent Hamiltonian, is a challenge of fundamental importance in quantum technologies.
We introduce a numerical method that efficiently performs this task through an artificial inverse dynamics.
We illustrate the method on two paradigmatic models: the Kitaev fermionic chain and a quantum Ising chain in longitudinal and transverse fields.
arXiv Detail & Related papers (2023-03-20T15:32:51Z) - 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) - Some Remarks on the Regularized Hamiltonian for Three Bosons with
Contact Interactions [77.34726150561087]
We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions.
In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed.
We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
arXiv Detail & Related papers (2022-07-01T10:01:14Z) - 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) - Exponentially faster implementations of Select(H) for fermionic
Hamiltonians [0.0]
We present a framework for constructing quantum circuits that implement the multiply-controlled unitary $textSelect(H) equiv sum_ell.
$textSelect(H)$ is one of the main subroutines of several quantum algorithms.
arXiv Detail & Related papers (2020-04-08T18:00: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.