Researchers from the Hefei National Laboratory for Physical Sciences at Microscale, University of Science and Technology of China, and Shanghai Research Center for Quantum Sciences have developed a quantum algorithm that can solve the ground states of classically hard Hamiltonians in polynomial time. The algorithm uses a unique mechanism of exponential speedup and employs density matrices to represent pure states. The team also provided a polynomial-time classical procedure to solve whether there exists a Liouvillian operator that equals the Hamiltonian with known ground energy. This development could have significant applications in quantum chemistry, machine learning, and optimization problems.
Quantum Algorithm for Solving Ground States of Classically Hard Hamiltonians
A team of researchers from the Hefei National Laboratory for Physical Sciences at Microscale and Department of Modern Physics, University of Science and Technology of China, Shanghai Branch CAS Centre for Excellence and Synergetic Innovation Centre in Quantum Information and Quantum Physics, and Shanghai Research Center for Quantum Sciences have developed a polynomial-time quantum algorithm for solving the ground states of classically hard Hamiltonians.
The algorithm’s mechanism of exponential speedup is different from all existing quantum algorithms. The researchers introduced a mapping fρ ρ to use density matrices to represent pure states. They demonstrated that this mapping makes sense by providing an efficient method to obtain the information of ρ from measurements on ρ. Under this mapping, the Lindblad master equation (LME) becomes a Schrödinger equation with a non-Hermitian Hamiltonian, which contains natural imaginary time evolution.
The steady state of the LME corresponds to the ground state of LL, with L being the Liouvillian operator of the LME. The researchers showed that the runtime of the LME has the O(logζ^-1) scaling with ζ, the overlap between the initial state and the ground state, compared with the O(polyζ^-1) scaling in other algorithms. The Hamiltonians LL are guaranteed to be difficult for classical computers if we believe the simulation of LME is difficult.
For any given local Hamiltonian H with known ground energy E0, the researchers provided a polynomial-time classical procedure to judge and solve whether there exists L such that HE0=LL. They further discussed and analyzed several important aspects of the algorithm, including the nonlinear dynamics that appeared in the algorithm.
Quantum Computers and Quantum Algorithms
Quantum computers can utilize properties of quantum mechanics like superposition and entanglement to solve problems faster than their classical counterparts. Over the past decades, there have been vast studies on quantum algorithms and many important ones have been found. Among the studies, quantum algorithms for solving quantum ground states are of particular interest due to their potential vast applications in many-body systems, quantum chemistry, classical combinatorial optimization problems, and machine learning.
The Structure of the Algorithm
The structure of the algorithm involves a Hamiltonian H with known ground energy E0. The judgment on whether there exists L makes HE0=LL is done by the XL algorithm. If the XL algorithm gives a solution L, then a quantum system can be generated whose dynamics are governed by an LME whose corresponding Liouvillian generator is LL. The system can then evolve freely to the steady state ρssρss of the LME if the steady state exists. Measurements for the Hadamard test and the Swap test can be done and the magic formula Eq5 can be used to obtain ground state information such as ρssAρss.
The Dynamics of Open Quantum Systems
The first component of the algorithm comes from the dynamics of open quantum systems. When a system is put in an environment that is large enough such that the Markovian approximation is valid, the dynamics of the system is governed by the Lindblad master equation (LME).
A research article titled “A polynomial-time quantum algorithm for solving the ground states of a class of classically hard Hamiltonians” was published on January 25, 2024. The authors of the study are Zhongxia Shang, Zihan Chen, Ming-Cheng Chen, Chao‐Yang Lu, and Jian-Wei Pan. The article was sourced from arXiv, a repository of electronic preprints approved for publication after moderation, hosted by Cornell University. The article can be accessed through its DOI reference https://doi.org/10.48550/arxiv.2401.13946.