Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods

• URL: http://arxiv.org/abs/2406.03222v2
• Date: Tue, 23 Jul 2024 06:41:11 GMT
• Title: Solving Sharp Bounded-error Quantum Polynomial Time Problem by Evolution methods
• Authors: Zhen Guo, Li You,
• Abstract summary: Counting ground state degeneracy of a $k$-local Hamiltonian is important in many fields of physics. Finding ground states of a $k$-local Hamiltonian is an easier problem of Quantum Merlin Arthur.
• Score: 10.891099517614037
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counting ground state degeneracy of a $k$-local Hamiltonian is important in many fields of physics. Its complexity belongs to the problem of sharp bounded-error quantum polynomial time (#BQP) class and few methods are known for its solution. Finding ground states of a $k$-local Hamiltonian, on the other hand, is an easier problem of Quantum Merlin Arthur (QMA) class, for which many efficient methods exist. In this work, we propose an algorithm of mapping a #BQP problem into one of finding a special ground state of a $k$-local Hamiltonian. We prove that all traditional methods, which solve the QMA problem by evolution under a function of a Hamiltonian, can be used to find the special ground state from a well-designed initial state, thus can solve the #BQP problem. We combine our algorithm with power method, Lanczos method, and quantum imaginary time evolution method for different systems to illustrate the detection of phase boundaries, competition between frustration and quantum fluctuation, and potential implementations with quantum circuits.

Related papers

• A Dequantized Algorithm for the Guided Local Hamiltonian Problem [2.891413712995642]
  The guided local Hamiltonian (GLH) problem can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. We introduce a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm.
  arXiv  Detail & Related papers  (2024-11-25T07:38:16Z)
• 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)
• Efficient Quantum Pseudorandomness from Hamiltonian Phase States [41.94295877935867]
  We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem. We show that our assumption is plausibly fully quantum; meaning, it cannot be used to construct one-way functions. We show that our assumption and its variants allow us to efficiently construct many pseudorandom quantum primitives.
  arXiv  Detail & Related papers  (2024-10-10T16:10:10Z)
• A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians [4.500918096201963]
  We give a complexity-time quantum algorithm for solving the ground states of a class of classically hard Hamiltonians. We show that the Hamiltonians that can be efficiently solved by our algorithms contain classically hard instances.
  arXiv  Detail & Related papers  (2024-01-25T05:01:02Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Optimizing local Hamiltonians for the best metrological performance [0.0]
  We discuss efficient methods to optimize the metrological performance over local Hamiltonians in a bipartite quantum system. We present the quantum Fisher information in a bilinear form and maximize it by iterating a see-saw. We consider a number of other problems in quantum information theory that can be solved in a similar manner.
  arXiv  Detail & Related papers  (2022-06-06T18:01:03Z)
• Quantum Davidson Algorithm for Excited States [42.666709382892265]
  We introduce the quantum Krylov subspace (QKS) method to address both ground and excited states. By using the residues of eigenstates to expand the Krylov subspace, we formulate a compact subspace that aligns closely with the exact solutions. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems.
  arXiv  Detail & Related papers  (2022-04-22T15:03:03Z)
• 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)
• Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
  Evolution in imaginary time is a prominent technique for finding the ground state of quantum many-body systems. We propose an algorithm to implement imaginary time propagation on a quantum computer.
  arXiv  Detail & Related papers  (2021-02-24T12:48:00Z)
• Theoretical survey of unconventional quantum annealing methods applied to adifficult trial problem [2.2209333405427585]
  We consider a range of unconventional modifications to Quantum Annealing (QA) In this problem, inspired by "transverse field chaos" in larger systems, classical and quantum methods are steered toward a false local minimum. We numerically study this problem by using a variety of new methods from the literature.
  arXiv  Detail & Related papers  (2020-11-12T05:54:57Z)
• Iterative Quantum Assisted Eigensolver [0.0]
  We provide a hybrid quantum-classical algorithm for approximating the ground state of a Hamiltonian. Our algorithm builds on the powerful Krylov subspace method in a way that is suitable for current quantum computers.
  arXiv  Detail & Related papers  (2020-10-12T12:25:16Z)

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.