Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation

arXiv:2504.19185 · quant-ph · Submitted 2025-04-27 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation".

Mira: A novel quantum algorithm is proposed that computes linear algebra problems in poly-logarithmic time by leveraging the eigenstate thermalization hypothesis instead of requiring elaborate wavefunction preparation.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: Building on what we discussed, let's look closer at the actual mechanics described in "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation." Essentially, the paper summarizes how they propose using time evolution to generate a state that approximates an equal superposition of eigenstates <ref:2504.19185#pg0>.

Mira: They formalize this by stating that applying time evolution to an arbitrary, non-eigenstate (t) = (-iAt r in a quantum circuit results in a state that approximates an equal superposition of eigenstates when viewed as a time-averaged ensemble <ref:2504.19185#pg0>.

Lev: So, the core mechanism is harnessing the ergodic properties of the system dynamics to achieve this superposition without needing an explicit preparation step for that state <ref:2504.19185#pg2>. That's a big conceptual leap if it holds up under practical conditions, Mira.

Kai: It really is; they then follow this by applying a quantum phase estimation subroutine to weight the eventual measurement, which allows them to compute functions of the input operator <ref:2504.19185#pg1>.

Mira: This QPE step is what actually yields the results for linear algebra problems, specifically showing how they can measure things like matrix traces, inverses, and even logarithms of determinants <ref:2504.19185#pg2>.

Lev: It sounds like the paper argues that the entire process—from thermalization to QPE—is a single unified mechanism for solving a whole class of linear algebra challenges <ref:2504.19185#pg0>. That's efficient if true, but we need to check the overhead implied by that unity.

Kai: The paper gives the specific scaling O(tau epsilon gamma two N), where tau is thermalization time and epsilon is precision, suggesting that this method aims for poly-logarithmic time complexity for solving these problems <ref:2504.19185#pg1>.

Mira: But they are careful to point out that this efficiency relies on the eigenstate thermalization hypothesis suppressing initial state dependence, which is what allows them to avoid the costly O(N) wavefunction preparation step that classical methods often require <ref:2504.19185#pg2>.

Lev: I wonder if the overhead of implementing that specific QPE subroutine adds a hidden cost that isn't fully captured by the gamma factor or the epsilon term, especially when dealing with large condition numbers <ref:2504.19185#pg1>.

Kai: The paper also details how they recover the micro-canonical ensemble during the QPE step by defining a density matrix using a specific relationship involving f(E k) and epsilon zero <ref:2504.19185#pg1>.

Mira: So, in essence, the summary is that time evolution acts as a natural sampler for the eigenstates, and QPE lets us read the properties of those sampled states efficiently to solve linear algebra problems <ref:2504.19185#pg0>.

Lev: It’s a very structured argument, moving from a physical assumption about quantum dynamics to an algorithmic procedure that uses statistical mechanics concepts to manage the measurement process <ref:2504.19185#pg2>.

The paper's summary: Kai: Now, let's talk about what the authors actually claim are the specific improvements this algorithm offers over existing methods, as detailed in "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation." The primary improvement is circumventing the need for elaborate wavefunction preparation on the quantum computer <ref:2504.19185#pg2>.

Mira: That's a huge point because preparing an initial state that encodes all necessary information for a problem can be extremely expensive and often dominates the runtime in other approaches <ref:2504.19185#pg0>. This paper suggests that using thermalization as a resource instead of preparation fundamentally changes the resource constraint <ref:2504.19185#pg2>.

Lev: If we can avoid that O(N) initial state construction, it makes the algorithm much more viable for problems with large Hilbert spaces where preparing an exact input state is infeasible <ref:2504.19185#pg2>. That's where the real hardware advantage lies if this works reliably.

Kai: Beyond just avoiding preparation, they show how this approach provides a route to compute specific functions of operators, such as matrix inverses and determinants, in poly-logarithmic time <ref:2504.19185#pg2>.

Mira: They achieve this by using the structure derived from the equal superposition of eigenstates and then applying quantum phase estimation to weight that measurement to extract those specific values <ref:2504.19185#pg0>. It’s a direct pathway for calculating those quantities without needing a full matrix inversion step first <ref:2504.19185#pg2>.

Lev: That capability to calculate the inverse matrix directly through this thermalization route is what makes me most interested from a computational standpoint <ref:2504.19185#pg2>. It suggests a path for solving systems of equations that might be much faster than current methods <ref:2504.19185#pg0>.

Kai: They also present the ability to compute gradients of the logarithm-determinant, which they call QGLD, which is useful for certain physical quantities in simulation <ref:2504.19185#pg2>.

Mira: That's an interesting extension because it shows this method isn't just limited to simple operators but can handle derivatives of more complex functions, like the logarithm of a determinant <ref:2504.19185#pg2>.

Lev: For running this on real hardware, calculating those gradients efficiently requires very precise control over the time evolution and measurement process to minimize noise propagation during the derivative calculation <ref:2504.19185#pg1>.

Kai: In summary, the improvement is a shift in resource usage—from expensive state preparation to leveraging system thermalization to generate necessary superpositions for linear algebra computation <ref:2504.19185#pg0>.

Mira: And theoretically, this suggests that the inherent ergodic nature of quantum systems under time evolution offers a way to bypass many traditional computational bottlenecks in quantum algorithms for linear algebra <ref:2504.19185#pg2>.

The paper's improvements: Kai: We’ve covered a lot about this paper, "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation," focusing on how time evolution can generate useful superpositions <ref:2504.19185#pg0>. Essentially, we've discussed bypassing expensive state preparation and using QPE to extract matrix properties like inverses and determinants <ref:2504.19185#pg2>.

Mira: The paper concludes that under the assumptions of Random Matrix Theory, this method provides a sufficient condition to explain thermalization for quantum circuits, linking it back to the micro-canonical ensemble expectation value <ref:2504.19185#pg1>.

Lev: I just want to reiterate my main concern about the practical execution: the ability of experimentalists to implement the necessary thermalization time tau robustly while keeping noise manageable remains a significant hurdle for moving this from theory to a working device <ref:2504.19185#pg2>.

Kai: So, we've seen how this algorithm uses the eigenstate thermalization hypothesis and QPE to compute linear algebra functions in poly-logarithmic time, relying on time evolution rather than elaborate initial state construction <ref:2504.19185#pg0>.

Mira: The broader implication is that if we can harness this connection between quantum dynamics and statistical mechanics, we might unlock more efficient methods for solving complex linear algebra problems in quantum computing <ref:2504.19185#pg2>.

Lev: We need to keep an eye on how researchers tackle the condition number issues when they scale up the QPE steps for these larger problems, because that seems like a key area where the current theoretical framework needs further refinement <ref:2504.19185#pg1>.

Kai: That’s our wrap-up on this paper, "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation," showing a path forward that uses thermalization for linear algebra computation <ref:2504.19185#pg0>.

Conclusion: Kai: So, to wrap up this discussion on "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation," we've seen how time evolution can generate superpositions to solve linear algebra problems in poly-logarithmic time <ref:2504.19185#pg0>.

Mira: Exactly, and the core idea is that exploiting the ergodic properties of quantum systems under thermalization allows us to bypass the need for expensive initial state preparation <ref:2504.19185#pg2>. It’s a really elegant way to frame how we can use system dynamics as a resource <ref:2504.19185#pg0>.

Lev: From an error-correction standpoint, the scaling O(tau epsilon gamma two N) is what tells me this has potential on real hardware, provided we can manage the thermalization time tau and mitigate decoherence during those long evolution steps <ref:2504.19185#pg1>.

Kai: Right, so the paper shows that we can use QPE to extract things like matrix inverses and determinants by weighting the measurement based on these thermalized states <ref:2504.19185#pg2>. That’s a tangible result for solving linear algebra tasks <ref:2504.19185#pg0>.

Mira: And the theoretical underpinning, relying on Random Matrix Theory to justify the micro-canonical ensemble recovery during that QPE step, gives this a solid statistical foundation <ref:2504.19185#pg1>. It bridges pure quantum mechanics with thermodynamics nicely <ref:2504.19185#pg2>.

Lev: I still see the challenge in the condition number kappa issue when we scale up to larger Hilbert spaces; that’s where the error propagation during QPE could become really problematic for fault-tolerant implementations <ref:2504.19185#pg1>.

Kai: So, while it’s a theoretical framework, the potential impact is significant because it points toward a fundamentally different resource strategy for quantum computation when dealing with linear algebra <ref:2504.19185#pg0>.

Mira: It suggests that the way we view time evolution in an arbitrary circuit might be more powerful than just looking at individual state preparations <ref:2504.19185#pg2>.

Lev: If we could actually engineer a physical system where thermalization happens reliably in the desired subspace, this would offer a new avenue for implementing these kinds of computations on actual quantum hardware <ref:2504.19185#pg2>.

Kai: We’ve really covered the mechanics of this paper, "Quantum computation with the eigenstate thermalization hypothesis instead of wavefunction preparation," and its potential to reshape how we approach linear algebra problems <ref:2504.19185#pg0>.

Mira: It’s a very interesting piece because it grounds some advanced quantum dynamics in established statistical mechanics concepts, which is always encouraging for the field <ref:2504.19185#pg1>.

Lev: Moving forward, we need to see how researchers tackle those condition number issues on actual hardware before this becomes a practical tool for large-scale applications <ref:2504.19185#pg2>.

University of Victoria

quant-ph

Submitted: 2025-04-27

Updated: 2026-10-06

Comments: 22 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 78/100

The gist: A novel quantum algorithm is proposed that computes linear algebra problems in poly-logarithmic time by leveraging the eigenstate thermalization hypothesis instead of requiring elaborate wavefunction

Key concepts

Eigenstate Thermalization Hypothesis (ETH): This hypothesis suggests that the time evolution of a quantum system, even starting from an arbitrary state, will cause it to thermalize. In simple terms, this means the system's properties will eventually resemble those of a thermal ensemble, suppressing dependence on the specific initial state.
Equal Superposition of Eigenstates: The algorithm aims to create a quantum state that is an equal combination of all possible energy eigenstates of the system. This is achieved by letting the circuit evolve over time, which, according to ETH, approximates this superposition in a time-averaged sense.
Quantum Phase Estimation (QPE): QPE is a quantum technique used to find the eigenvalues or properties of an operator. In this algorithm, it is applied after generating the superposition to weight the measurement results and extract the desired expectation value related to linear algebra problems.

Terminology

Eigenstate Thermalization Hypothesis — 28× in this paper
Quantum Phase Estimation — 17× in this paper
Random Matrix Theory — 16× in this paper
Core — 11× in this paper · explained in 2 episodes
Trace — 11× in this paper · explained in 2 episodes
Hilbert Space — 10× in this paper · explained in 2 episodes
Quantum Circuits — 9× in this paper · explained in 2 episodes
Quantum Physics — 8× in this paper · explained in 10 episodes
BQP — 4× in this paper · explained in 2 episodes
Quantum Phase Estimation (QPE) — 3× in this paper · explained in 3 episodes
Eigenstate Thermalization Hypothesis (ETH) — 2× in this paper · explained in 4 episodes
Random Matrix Theory (RMT) — 2× in this paper · explained in 3 episodes
Unitary Dynamics — 2× in this paper · explained in 2 episodes
Adam — 1× in this paper · explained in 2 episodes
BQP-complete — 1× in this paper · explained in 2 episodes
Fingerprinting — 1× in this paper · explained in 2 episodes
Generalization — 1× in this paper · explained in 13 episodes
Inverse Problem — 1× in this paper · explained in 2 episodes

Summary

A novel quantum algorithm is proposed that computes linear algebra problems in poly-logarithmic time by leveraging the eigenstate thermalization hypothesis instead of requiring elaborate wavefunction preparation. This approach circumvents the need for expensive initial state construction by using time evolution to generate an equal superposition of eigenstates, combined with quantum phase estimation to compute functions of the input operator.

Core Proposal and Motivation

The paper proposes that the ability for a quantum circuit to thermalize under time evolution is a valid way to compute linear algebra problems. This algorithm utilizes the eigenstate thermalization hypothesis and full ergodicity in quantum systems to produce an equal superposition of eigenstates. The motivation stems from the classical observation that processes reaching equilibrium involve a loss of initial state information, which quantum mechanics does not naturally lead to. The core development is proposing that an equal superposition can be created as an ensemble (time-average) in O(n) time for a wide class of models through thermalization.

The Algorithm: ETH-Σ

The proposed algorithm, termed ETH-Σ (ETH-summation), follows a three-step process:

Generate an equal superposition of eigenstates, as described by the conjecture that a time evolution of an arbitrary, non-eigenstate Ψ(t)⟩ = exp(-iAtˆr⟩ in a quantum circuit will approximate an equal superposition of eigenstates in a time-averaged ensemble of states.
Apply a quantum phase estimation to weight the eventual measurement.
Measure the resulting operator to obtain the desired expectation value, which is approximated by 1/N Tr ΓˆρOˆ and recovered as ⟨Ψ(t)ρˆO ˆ Ψ(t)⟩ ≈ 1/N X N k=1 f(Ek)⟨kρˆk⟩Γkk.

Theoretical Foundation: Eigenstate Thermalization Hypothesis (ETH)

The main result is based on the proposition that A time evolution of an arbitrary, non-eigenstate Ψ(t)⟩ = exp(-iAtˆr⟩ in a quantum circuit will approximate an equal superposition of eigenstates in a time-averaged ensemble of states. This is formalized as Conjecture 1: The eigenstate thermalization hypothesis suppresses the initial state dependence. The paper justifies this by appealing to Random Matrix Theory (RMT), which suggests that energy levels can be randomly spaced in a quantum system, leading to the relationship where the diagonal ensemble expectation value is equivalent to the micro-canonical ensemble under RMT.

Computational Efficiency and Recovery of Ensemble

The overall scaling for the ETH-Σ algorithm is stated as O(τ ε γ log2 N), where τ is thermalization time, n = log2 N qubits, and γ = 1 or 2. The paper notes that the time evolution will happen in poly-logarithmic time, although exceptions like many-body localization exist. Furthermore, the micro-canonical ensemble is recovered during the QPE step at finite precision ε by defining a density matrix Γ as "Γˆkk ≈ (1/f(Ek)⟨kρˆk⟩ > ε 0 otherwise." This finite precision window effectively recovers the characteristic energy window of a micro-canonical ensemble.

Applications and Results

The algorithm is shown to solve various linear algebra problems, including:

- Measuring the trace of a matrix:

The generation of an equal superposition using a form of Υ with only the ˆeigenvalues as Υ = diag(ˆE1, E2,..., EM) would give ⟨Aˆ⟩ upon measurement and averaging.

- Measuring an inverse matrix:

This is achieved by using the inverse of the eigenvalues would give the inverse matrix, Υ = diag(1/E1, 1/E2,..., 1/EM).

- Measuring the logarithm determinant:

This is found by using Υ = diag(log E1, log E2,..., log EM) then the result is the sum of the logarithmic terms.

The paper concludes that under RMT assumptions, the micro-canonical ensemble expectation value is equal to the diagonal ensemble O(⟨E⟩ ≈ OMC, demonstrating that ETH under RMT provides a sufficient condition to explain thermalization for quantum circuits. The algorithm is proposed as a potential BQP algorithm for many linear algebra problems.

Sources of Error and Mitigation

Sources of error include potential errors introduced by the thermalization itself, fluctuations in the time-average, and issues with the Quantum Phase Estimation (QPE) when dealing with large condition numbers (κ = E1/EM).

Improvements for AI systems

Based on the provided scientific paper, here are the specific improvements that can be made to Artificial Intelligence (AI) systems, along with what those improved systems could achieve:

The core improvement proposed is a new class of quantum algorithms based on the combination of Time-Evolution Thermalization and Quantum Phase Estimation (ETH-Σ). This shifts the paradigm from requiring expensive wavefunction preparation to utilizing time evolution as a resource for generating an equal superposition of eigenstates.

Here are the specific improvements and capabilities:

The ability to compute functions of input operators, such as matrix inverses, determinants, and gradients of logarithms (e.g., QGLD), in poly-logarithmic time rather than exponential or high-order polynomial time on classical computers.
The elimination of the need for elaborate wavefunction preparation on the quantum computer for solving linear algebra problems (circumventing the typically costly O(N) step).
The ability to approximate expectation values of general operators, including inverses and determinants, by leveraging an ensemble average generated via thermalization, which is equivalent to a micro-canonical ensemble under random matrix theory (RMT).

The resulting improved AI systems can perform the following specific tasks:

Precision calculation of high-dimensional linear algebra problems (e.g., solving the system of equations Aˆx = b) with a scaling of only O(T /ε2) where T is related to thermalization time and ε is the precision requested, suggesting a potential BQP-complete algorithm for these tasks.
Efficient computation of matrix inverses (as shown in Example 8.3), by using the QPE to discover all eigenvalues and applying an appropriate diagonal operator with inverse eigenvalues as weights.
Calculation of matrix determinants (Example 8.4) and their logarithms, which are equivalent to the trace of the logarithm, by using a weighting operator based on logarithmic eigenvalues.
Computation of gradients of the logarithm-determinant (QGLD) for input operators that have derivatives expressed as a matrix ∆, providing an efficient implementation for these physical quantities.
Solving problems involving large quantum circuits where thermalization time is not excessively long (i.e., systems that do not exhibit Many-Body Localization), allowing the algorithm to operate efficiently even when the system is in a non-integrable state.

Abstract

It is proposed that the ability for a quantum circuit to thermalize under time evolution is a valid way to compute linear algebra problems. The algorithm makes use of the eigenstate thermalization hypothesis and full ergodicity in quantum systems to produce an equal superposition of eigenstates. The quantum phase estimation subroutine then allows for the computations of functions of the input operator, leading to a variety of methods in linear algebra. The algorithm circumvents the need for elaborate wavefunction preparation on the quantum computer to find the solution of the linear algebra problem in poly-logarithmic time.