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.13946v5
• Date: Thu, 4 Jul 2024 04:27:33 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 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.
• Score: 4.500918096201963
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this work, 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. To utilize the dissipation, the central idea is to treat $n$-qubit density matrices $\rho$ as $2n$-qubit pure states $|\rho\rangle$ by vectorization and normalization. By doing so, the Lindblad master equation (LME) becomes a Schr\"odinger equation with non-Hermitian Hamiltonian $L$. The steady-state $\rho_{ss}$ of the LME, therefore, corresponds to the ground states $|\rho_{ss}\rangle$ of Hamiltonians with the form $L^\dag L$. The runtime of the LME has no dependence on $\zeta$ the overlap between the initial state and the ground state compared with the Heisenberg scaling $\mathcal{O}(\zeta^{-1})$ in other algorithms. For the input part, given a Hamiltonian $H$, under plausible assumptions, we give a polynomial-time classical procedure to judge and solve whether there exists $L$ such that $H-E_0=L^\dag L$. For the output part, we define the mission as estimating expectation values of arbitrary operators with respect to the ground state $|\rho_{ss}\rangle$, which can be done surprisingly by an efficient measurement protocol on $\rho_{ss}$ with no need to prepare $|\rho_{ss}\rangle$. We give several pieces of evidence on the quantum hardness of really preparing $|\rho_{ss}\rangle$, which indicates a potential complexity separation between our algorithm and those projection-based quantum algorithms such as quantum phase estimation. Further, we show that the Hamiltonians that can be efficiently solved by our algorithms contain classically hard instances assuming $\text{P}\neq \text{BQP}$. Later, we discuss and analyze several important aspects of the algorithm including generalizing to other types of Hamiltonians and the "non-linear`` dynamics in the algorithm.

Related papers

• Multi-level quantum signal processing with applications to ground state preparation using fast-forwarded Hamiltonian evolution [0.8359711817610189]
  Preparation of the ground state of a Hamiltonian $H$ with a large spectral radius has applications in many areas. We develop a multi-level Quantum Signal Processing (QSP)-based algorithm that exploits the fast-forwarding feature.
  arXiv  Detail & Related papers  (2024-06-04T08:09:51Z)
• 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)
• Do you know what q-means? [50.045011844765185]
  Clustering is one of the most important tools for analysis of large datasets. We present an improved version of the "$q$-means" algorithm for clustering. We also present a "dequantized" algorithm for $varepsilon which runs in $Obig(frack2varepsilon2(sqrtkd + log(Nd))big.
  arXiv  Detail & Related papers  (2023-08-18T17:52:12Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• How to simulate quantum measurement without computing marginals [3.222802562733787]
  We describe and analyze algorithms for classically computation measurement of an $n$-qubit quantum state $psi$ in the standard basis. Our algorithms reduce the sampling task to computing poly(n)$ amplitudes of $n$-qubit states.
  arXiv  Detail & Related papers  (2021-12-15T21:44:05Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)
• 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)
• 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.