A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians

• URL: http://arxiv.org/abs/2401.13946v8
• Date: Tue, 12 Nov 2024 10:10:45 GMT
• Title: A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians
• Authors: Zhong-Xia Shang, Zi-Han Chen, Chao-Yang Lu, Jian-Wei Pan, Ming-Cheng Chen,
• Abstract summary: 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.
• Score: 4.500918096201963
• License:
• Abstract: In this work, we give a polynomial-time quantum algorithm for solving the ground states of a class of classically hard Hamiltonians. The mechanism of the exponential speedup that appeared in our algorithm comes from dissipation in open quantum systems. To utilize the dissipation, we introduce a new idea of treating vectorized density matrices as pure states, which we call the vectorization picture. By doing so, the Lindblad master equation (LME) becomes a Schr\"odinger equation with non-Hermitian Hamiltonian. The steady state of the LME, therefore, corresponds to the ground states of a special class of Hamiltonians. The runtime of the LME has no dependence on the overlap between the initial state and the ground state. For the input part, given a Hamiltonian, under plausible assumptions, we give a polynomial-time classical procedure to judge and solve whether there exists LME with the desired steady state. For the output part, we propose a novel measurement strategy to extract information about the ground state from the original steady density matrix. We show that the Hamiltonians that can be efficiently solved by our algorithms contain classically hard instances assuming $\text{P}\neq \text{BQP}$. We also discuss possible exponential complexity separations between our algorithm and previous quantum algorithms without using the vectorization picture.

Related papers

• Quantum random power method for ground state computation [0.0]
  We present a quantum-classical hybrid random power method that approximates a Hamiltonian ground state. We show that our method converges to an approximation of a ground state of the Hamiltonian.
  arXiv  Detail & Related papers  (2024-08-16T06:41:16Z)
• Local Hamiltonian Problem with succinct ground state is MA-Complete [0.788657961743755]
  Finding the ground energy of a quantum system is a fundamental problem in condensed matter physics and quantum chemistry. Existing classical algorithms for tackling this problem often assume that the ground state has a succinct classical description. We study the complexity of the local Hamiltonian problem with succinct ground state and prove it is MA-Complete.
  arXiv  Detail & Related papers  (2023-09-18T21:08:51Z)
• Vectorization of the density matrix and quantum simulation of the von Neumann equation of time-dependent Hamiltonians [65.268245109828]
  We develop a general framework to linearize the von-Neumann equation rendering it in a suitable form for quantum simulations. We show that one of these linearizations of the von-Neumann equation corresponds to the standard case in which the state vector becomes the column stacked elements of the density matrix. A quantum algorithm to simulate the dynamics of the density matrix is proposed.
  arXiv  Detail & Related papers  (2023-06-14T23:08:51Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• 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)
• Hamiltonian learning from time dynamics using variational algorithms [3.3269356210613656]
  Hamiltonian of a quantum system governs the dynamics of the system via the Schrodinger equation. In this paper, the Hamiltonian is reconstructed in the Pauli basis using measurables on random states forming a time series dataset. We show results on Hamiltonians involving XX, ZZ couplings along with transverse field Ising Hamiltonians and propose an analytical method for the learning of Hamiltonians consisting of generators of the SU(3) group.
  arXiv  Detail & Related papers  (2022-12-28T05:22:57Z)
• 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)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• Inverse iteration quantum eigensolvers assisted with a continuous variable [0.0]
  We propose inverse iteration quantum eigensolvers, which exploit the power of quantum computing for the classical inverse power iteration method. A key ingredient is constructing an inverse Hamiltonian as a linear combination of coherent Hamiltonian evolution. We demonstrate the quantum algorithm with numerical simulations under finite squeezing for various physical systems.
  arXiv  Detail & Related papers  (2020-10-07T07:31:11Z)
• A variational quantum algorithm for Hamiltonian diagonalization [5.207748672230163]
  We propose a variational algorithm for Hamiltonians diagonalization (VQHD) of quantum systems. The thermal states of the system encode the information of eigenvalues and eigenstates of the system Hamiltonian. Our VQHD algorithm sheds new light on the applications of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-08-22T15:20:00Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

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.