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

Zhong-Xia Shang, Zihan Chen, Ming-Cheng Chen, Chao‐Yang Lu, Jian-Wei PanarXiv 2024 · DOI · arXiv

Finding the ground state of a quantum system—the state with the lowest possible energy—is one of the most fundamental challenges in physics and chemistry. It is also notoriously difficult. For general "local" Hamiltonians, the problem is QMA-hard (the quantum equivalent of NP-hard), meaning even quantum computers are expected to struggle with it in the general case.

A new paper by Zhong-Xia Shang and colleagues from the University of Science and Technology of China (USTC) proposes a novel way around this wall. By leveraging dissipation—the process by which a system loses energy to its environment—they’ve developed a polynomial-time quantum algorithm for a specific class of Hamiltonians that are otherwise classically "hard" to solve.

TL;DR

The authors introduce a quantum algorithm that uses open-system dissipation to find ground states in polynomial time, bypassing the "initial overlap" bottleneck that plagues standard algorithms. By mapping density matrices to pure states (the "vectorization picture"), they show that certain classically hard problems can be solved efficiently on a quantum processor.

What Problem Does This Paper Address?

Most quantum algorithms for ground-state preparation (like Quantum Phase Estimation) rely on "projecting" an initial guess onto the true ground state. The catch? The time required scales inversely with the overlap ($\zeta$) between your guess and the target. In high-dimensional Hilbert spaces, this overlap is often exponentially small, leading to an exponential runtime.

While recent "dissipative" algorithms have tried to use environmental coupling to drive a system toward its ground state, proving their complexity is difficult. This paper seeks to formalize a class of Hamiltonians that can be solved in polynomial time by exploiting the natural "mixing" behavior of open quantum systems.

Methods

The researchers combine three distinct components into a unified workflow:

  1. The Vectorization Picture: Instead of treating a quantum state as a density matrix $\rho$, they treat it as a vector $|\rho\rangle$. Under this mapping, the Lindblad Master Equation (LME)—which describes how open systems evolve—looks exactly like a Schrödinger equation, but with a non-Hermitian Hamiltonian (a Liouvillian, $L$).
  2. Hamiltonian Correspondence: They show that the steady state of an LME corresponds to the ground state of a Hermitian Hamiltonian of the form $H = L^\dagger L$.
  3. The XL Algorithm (Input): To solve a specific Hamiltonian $H$, you first need to find the operator $L$ such that $H - E_0 = L^\dagger L$. The authors use a classical pre-processing technique called the XL algorithm to solve the resulting system of multivariate quadratic equations in polynomial time for local Hamiltonians.
  4. Substitute Operators (Output): To extract information (like expectation values) from the steady state without actually "preparing" the vectorized state as a physical pure state, they introduce "substitute operators." This allows them to use standard Hadamard and Swap tests on the physical density matrix to get the desired results.

Datasets

The paper does not use external datasets. Instead, it validates the algorithm through:

  • Complexity Analysis: Rigorous proofs of runtime scaling.
  • Numerical Simulations: They tested the classical XL algorithm's performance on a 1D XXZ model (a standard benchmark in condensed matter physics) with system sizes ranging from 5 to 19 qubits to demonstrate polynomial scaling in practice.

Key Insights and Ideas

  • Overlap Independence: The most striking feature is that the LME runtime depends on the mixing time of the system rather than the initial state overlap. If the system mixes quickly, the algorithm is fast, even if your initial guess was terrible.
  • Classical Hardness via BQP-Completeness: The authors prove that the class of Hamiltonians they can solve includes instances that can encode universal quantum circuits. This means that if $P \neq BQP$, these problems are fundamentally impossible for classical computers to solve efficiently, yet this algorithm handles them in polynomial time.
  • The "Non-Linear" Bonus: The authors observe that while quantum mechanics is linear, the mapping from density matrices to "DM-states" ($f: \rho \to |\rho\rangle$) introduces an "emerging non-linearity." This suggests that dissipative dynamics might be able to solve certain problems that standard linear quantum mechanics cannot.

Key Results

  • Efficiency: For $k$-local Hamiltonians, the classical pre-processing (XL algorithm) runs in $O(poly(n))$ time (e.g., approximately $N^{5.678}$ for 4-local Hamiltonians).
  • Exponential Speedup: They demonstrate a task—estimating amplitudes in the Bell basis—where their vectorization approach provides a $2^n$ complexity reduction compared to quantum algorithms that don't use this picture.
  • Provable Separation: By constructing a Liouvillian that encodes a BQP-complete problem, they provide a concrete example of a quantum-classical separation for ground-state problems.

Limitations and Future Work

  • Not a Universal Solvent: The algorithm only works for Hamiltonians that can be decomposed into $L^\dagger L$ where $L$ is "fast-mixing." It is not yet clear how many physically interesting Hamiltonians (like those in complex chemistry) fall into this category.
  • Knowledge of $E_0$: The current version requires knowing the ground state energy $E_0$ beforehand to set up the equations, though the authors suggest this requirement might be relaxed in the future.
  • Purity Constraints: The efficiency of the measurement phase depends on the purity of the steady state ($\gamma$). If the steady state is too "mixed," the number of measurements required could grow.

The authors conclude that this "vectorization picture" opens a new door for studying non-Hermitian physics on quantum computers and suggests that dissipation is not just "noise" to be corrected, but a powerful computational resource.

Summary updated

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ödinger 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.
BibTeX
@misc{shang2024polynomial,
  author = {Zhong-Xia Shang and Zihan Chen and Ming-Cheng Chen and Chao‐Yang Lu and Jian-Wei Pan},
  title = {{A polynomial-time dissipation-based quantum algorithm for solving the ground states of a class of classically hard Hamiltonians}},
  year = {2024},
  eprint = {2401.13946},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2401.13946},
}

Loading related content...

Figure