Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation

This paper proposes a quantum algorithm that leverages the eigenstate thermalization hypothesis and full ergodicity to generate an equal superposition of eigenstates, thereby enabling the solution of linear algebra problems in poly-logarithmic time without the need for elaborate wavefunction preparation.

The Gist

The Big Idea: Letting the System "Stir Itself"

Imagine you have a cup of tea and a splash of milk. In the old days of quantum computing, if you wanted to solve a math problem using this tea, you had to carefully pour the milk in a very specific, perfect pattern before you could start. This "pouring" step (called wavefunction preparation) was slow, difficult, and often took so much time that it canceled out the speed benefits of using a quantum computer.

This paper proposes a completely different approach. Instead of carefully pouring the milk, the author suggests: Just drop the milk in and stir it.

The paper argues that if you let a quantum system evolve naturally over time (like the milk mixing into the tea), it will eventually reach a state of "thermal equilibrium." In this state, the system has "forgotten" exactly how the milk was dropped in. It has become a perfect, uniform mixture where every possible state is equally likely.

The author calls this process thermalization. By relying on this natural mixing process, we can skip the difficult "pouring" step entirely and get straight to the math.

The Core Ingredients

To make this work, the paper combines three main concepts:

1. The "Stirring" (Eigenstate Thermalization Hypothesis)
In physics, there is a rule called the Eigenstate Thermalization Hypothesis (ETH). Think of it like this: If you have a chaotic system (like a busy dance floor), and you watch it for a long time, the dancers will eventually move in a way that looks completely random and uniform. No matter where you started on the dance floor, after enough time, you are just as likely to be anywhere else.
The paper claims that if we run a quantum circuit long enough, it will naturally "stir" itself into this uniform, random state. This state is an equal superposition of all possible answers.

2. The "Labeling" (Quantum Phase Estimation)
Once the system is mixed up, we have a problem: we have all the answers, but we don't know which answer is which. It's like having a jar of mixed-up puzzle pieces where you can't tell which piece goes where.
To fix this, the paper uses a tool called Quantum Phase Estimation (QPE). Imagine QPE as a magical label maker. It looks at the mixed-up system and attaches a tiny tag to every piece that says, "I am piece number 5," or "I am piece number 100." Now, even though the pieces are mixed, we know exactly what each one represents.

3. The "Math Trick" (Linear Algebra)
Now that we have a jar of mixed pieces, all labeled, we can do math on them.

• If we want to find the inverse of a number (like $1/x$), we just tell the label maker to change the label from "$x$" to "$1/x$."
• If we want the determinant (a specific summary number for a matrix), we multiply all the labels together.
• If we want the trace (the sum of the diagonal), we just add the labels up.

Because the system is already mixed (thermalized), we don't need to build a specific starting state. We just let the system mix, label the pieces, and then measure the result.

Why This is a Big Deal

The Old Way (Wavefunction Preparation):
Imagine trying to solve a puzzle by carefully placing every single piece in the right spot one by one before you can even look at the picture. This takes a long time (exponential time) and is very hard to do perfectly.

The New Way (ETH-Σ):
Imagine throwing all the puzzle pieces into a blender, letting them spin until they are a perfect, uniform cloud, and then using a scanner to read the labels on the pieces as they fly by. You didn't have to place them; the "blender" (thermalization) did the work for you.

The paper claims this method allows us to solve complex linear algebra problems (like finding the inverse of a giant matrix) in poly-logarithmic time. This means the time it takes grows very slowly as the problem gets bigger, which is the "holy grail" of quantum computing speed.

The Catch (What the Paper Says)

The paper is careful to note a few conditions:

• The System Must Be Chaotic: The "stirring" only works if the system is naturally chaotic. If the system is too orderly (a state called "Many-Body Localization"), it won't mix, and the milk will stay in a clump. The paper assumes we are working with systems that do mix well.
• Precision Matters: The "label maker" (QPE) needs to be precise. If the numbers are very small or very large, it might take extra effort to read the tiny details on the labels.
• It's a Conjecture: The method relies on the Eigenstate Thermalization Hypothesis, which is a widely accepted idea in physics but hasn't been mathematically proven for every single case yet. The paper treats it as a solid foundation to build a new algorithm.

Summary

The paper proposes a new way to do math on quantum computers. Instead of spending hours carefully preparing a specific starting state, we let the quantum system "thermalize" (mix itself up) naturally. Once it's mixed, we use a labeling tool to read the values, allowing us to calculate things like matrix inverses, determinants, and logarithms much faster than before. It turns the quantum computer from a precise sculptor into a powerful blender that does the heavy lifting for us.

Technical Summary

Technical Summary: Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation

Problem Statement

The paper addresses a significant bottleneck in quantum algorithms for solving linear algebra problems of the form $\hat{A}x = b$. While quantum computers are conjectured to solve such problems in poly-logarithmic time, current methods often rely on wavefunction preparation to initialize a specific input state $|\Psi\rangle$. The author argues that preparing a general wavefunction on a quantum computer is exponentially costly, typically requiring $O(N)$ operations (where $N$ is the Hilbert space dimension), which negates the potential exponential speedup of quantum algorithms. The core problem is to find a method to compute linear algebra quantities (such as matrix inverses, traces, or determinants) that circumvents the need for elaborate, state-specific wavefunction preparation.

Methodology

The proposed solution, termed ETH-Σ (Eigenstate Thermalization Hypothesis - Summation), replaces the standard wavefunction preparation step with a thermalization process driven by the Eigenstate Thermalization Hypothesis (ETH). The methodology consists of three main components:

1. Thermalization to an Equal Superposition:
   Instead of preparing a specific state, the algorithm starts with an arbitrary, non-eigenstate $|r\rangle$ and evolves it under a time-evolution operator $e^{-i\hat{A}t}$. The paper posits that for non-integrable (chaotic) systems, the time-averaged state of this evolution approximates an equal superposition of all eigenstates of $\hat{A}$.

   • This relies on the ETH, which suggests that individual eigenstates of chaotic systems act as thermal ensembles.
   • To ensure "full ergodicity" (equal probability across the entire Hilbert space, not just a symmetry sector), the author suggests modifying the operator $\hat{A}$ with "kicks" (perturbations) to break symmetries and induce quantum chaos, ensuring the system explores the full space.

2. Quantum Phase Estimation (QPE) for Weighting:
   Once the system is thermalized (on average), the algorithm applies the Quantum Phase Estimation subroutine. This maps the eigenstates $|k\rangle$ of $\hat{A}$ to an auxiliary register containing their corresponding eigenvalues $E_k$.

   • The QPE allows the algorithm to access the eigenvalues in superposition.
   • A diagonal operator $\hat{\Upsilon}$ is applied to the auxiliary register to weight these eigenvalues by a function $f(E_k)$. For example, to compute the inverse matrix, $f(E_k) = 1/E_k$.

3. Dual Formulation (Operator vs. Vector):
   The paper presents the algorithm in two forms:

   • Vector Form: Requires an initial state $|r\rangle$ and a target vector $|\Phi\rangle$. It computes the overlap $|\langle \Phi | \psi \rangle|^2$.
   • Operator Form (Primary Proposal): Recasts the problem using density matrices. The input is treated as an operator $\hat{\Delta} = |\Phi\rangle\langle\Phi|$ (or a general operator). The algorithm computes the expectation value $\langle \hat{\Delta} \otimes \hat{\Upsilon} \rangle$ over the time-averaged ensemble. This form avoids the need to prepare specific wavefunctions on the quantum computer, as the "input" is defined classically or via simple operators (like the identity or Hadamard gates).

Key Contributions

• ETH-Σ Algorithm: The proposal of a new algorithmic framework that utilizes the natural thermalization of quantum circuits to generate an equal superposition of eigenstates, effectively replacing the $O(N)$ wavefunction preparation step.
• Dual Formulation: The derivation of a method to compute linear algebra functions (like $\hat{A}^{-1}$, $\text{Tr}(\hat{A})$, $\log \det(\hat{A})$) by treating the input as an operator $\hat{\Delta}$ rather than a state vector, thereby reducing the overhead of state initialization.
• Full Ergodicity via Kicks: The suggestion that "kicking" the system (adding perturbations to break symmetries) ensures the thermalization covers the entire Hilbert space, satisfying the condition of full ergodicity required for the algorithm to function as a general linear algebra solver.
• Recovery of Micro-Canonical Ensemble: The argument that finite precision in the QPE effectively recovers a micro-canonical ensemble (summing over a window of states), justifying the use of ETH in a computational context where exact infinite-time limits are not physically realizable.

Results and Examples

The paper provides theoretical derivations and numerical examples (using the DMRjulia library) to demonstrate the feasibility of the approach:

• Small Operator Thermalization: A numerical test with $\hat{A} = \sigma_z$ showed that a random state thermalized to the expected value of the trace over the ensemble, verified across 100+ initial states.
• Linear Algebra Applications: The paper outlines how ETH-Σ can compute:
  • The trace of a matrix ($\text{Tr}(\hat{A})$).
  • The inverse of a matrix ($\hat{A}^{-1}$).
  • The logarithm of the determinant ($\log \det(\hat{A})$).
  • The gradient of the logarithm-determinant (relevant for thermodynamics and partition functions).
• Complexity: The algorithm is claimed to scale as $O(\frac{\tau}{\epsilon^\gamma} \log^2 N)$, where $\tau$ is the thermalization time, $\epsilon$ is the precision, and $N$ is the Hilbert space size. The thermalization time $\tau$ is conjectured to be poly-logarithmic for non-integrable systems.

Significance and Claims

The paper claims that this approach offers a poly-logarithmic time solution for a broad class of linear algebra problems by removing the "glaring issue" of wavefunction preparation.

• Modesty on Proof: The author explicitly states that the Eigenstate Thermalization Hypothesis (ETH) is a conjecture, not a proven theorem for general systems. Consequently, the main result (Proposition 1) is presented as a proposition based on ETH, supported by Random Matrix Theory (RMT) justification, rather than a rigorous mathematical proof.
• Limitations: The paper acknowledges that the algorithm relies on the system being non-integrable. It notes that Many-Body Localized (MBL) systems, which do not thermalize, would prevent the algorithm from working. However, the author suggests MBL is not the general case for physical systems of interest.
• Error Sources: The paper identifies the condition number of the matrix and the precision of the QPE as primary sources of error. It notes that while the initial state preparation is removed, the QPE still requires significant resources for high precision, particularly for matrices with large condition numbers (small eigenvalues).

In summary, the paper proposes a paradigm shift in quantum linear algebra: rather than preparing a specific state to solve a problem, one allows the quantum circuit to thermalize to a "maximally mixed" state of eigenstates and uses QPE to extract the desired linear algebraic function. This approach aims to bypass the exponential cost of state preparation, provided the system satisfies the Eigenstate Thermalization Hypothesis.