⚛️ quantum physics

DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians

This paper establishes that estimating the normalized trace of functions of log-local Hamiltonians is DQC1-complete for continuous functions with high approximate degree, thereby identifying the approximate degree as the key parameter governing both the quantum efficiency and conditional classical hardness of the problem.

Original authors: Zhengfeng Ji, Tongyang Li, Changpeng Shao, Xinzhao Wang, Yuxin Zhang

Published 2026-04-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zhengfeng Ji, Tongyang Li, Changpeng Shao, Xinzhao Wang, Yuxin Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "One Clean Qubit" Puzzle

Imagine you are trying to solve a massive, complex math problem, but you only have one perfect, shiny coin (a "clean qubit") and a giant bag of 1,000,000 coins that are all completely mixed up and useless (the "maximally mixed" state).

This is the DQC1 model (Deterministic Quantum Computation with One Qubit). It's a very restricted way of doing quantum math. Most people think this model is too weak to do anything useful, but it turns out it's actually a "Goldilocks" zone: it's too weak to solve everything a full quantum computer can, but it's still strong enough to solve some problems that are impossible for classical computers (like your laptop).

The main job of this model is to calculate the Normalized Trace.

The Analogy: Imagine a giant, chaotic dance floor with millions of dancers (the quantum state). The "Trace" is like asking, "On average, how much are the dancers facing the same direction?"
The Problem: Sometimes, instead of just asking about the dancers' current direction, we want to know about a function of their movement. Maybe we want to know the "average sine wave" of their dance, or the "average logarithm" of their speed.

The paper asks: When does calculating these "average functions" become impossible for a regular computer, but easy for our "One Clean Qubit" machine?

The Secret Ingredient: The "Approximate Degree"

The authors discovered that the difficulty of the problem depends entirely on how "wiggly" or "complex" the function is. They call this the Approximate Degree.

Simple Function (Low Degree): Think of a function like $f(x) = x$ $f (x) = x$ or $f(x) = x^2$ $f (x) = x^{2}$ . These are smooth, gentle curves. You can draw them with a simple ruler or a basic polynomial.
- Result: A regular computer can easily estimate the average of these. No magic needed.
Complex Function (High Degree): Think of a function like $e^x$ $e^{x}$ (exponential growth), $\sin(x)$ $sin (x)$ (wiggly waves), or $\log(x)$ $lo g (x)$ . These are very "wiggly." To draw them accurately with a simple polynomial, you need a formula with hundreds or thousands of terms.
- Result: If the function is "wiggly" enough (has a high approximate degree), a regular computer gets stuck. It would need to check an astronomical number of possibilities. But the "One Clean Qubit" machine can do it instantly.

The Main Discovery: The paper proves that if a function is "wiggly" enough (specifically, if its approximate degree grows with the size of the problem), then calculating its average is DQC1-complete. This means it is the hardest possible problem this specific type of quantum computer can solve.

How They Proved It: The "Periodic Roller Coaster"

To prove this, the authors built a clever bridge between quantum circuits and math.

The Circuit-to-Hamiltonian Trick: They took a quantum circuit (a sequence of logic gates) and turned it into a giant mathematical object called a Hamiltonian (a matrix representing energy).
The Periodic Jacobi Matrix: They noticed that this giant matrix looked like a Periodic Jacobi Matrix.
- The Analogy: Imagine a roller coaster track that loops back on itself. The shape of the track depends on the "wiggles" of the function you are trying to measure.
The Chebyshev Connection: They used a famous math theorem (Chebyshev Equioscillation) which says that the best way to approximate a wiggly function is to make it oscillate (go up and down) just as much as possible.
- They showed that the "wiggles" in the roller coaster track perfectly match the "wiggles" in the function.
- If the function is too wiggly (high degree), the roller coaster becomes so complex that a classical computer can't simulate the ride, but the quantum computer can "feel" the average height of the track instantly.

The Classical vs. Quantum Showdown

The paper also looked at how hard this is for a classical computer (a normal laptop).

The Conjecture: They assume a specific mathematical guess (related to a problem called "k-Forrelation") is true.
The Result: If that guess is true, then for these "wiggly" functions, a classical computer would need to ask exponentially more questions than a quantum computer.
- Analogy: Imagine trying to guess the average height of a mountain range.
  - Quantum: Takes one giant leap and lands right in the middle, sensing the average height instantly.
  - Classical: Has to climb every single peak and valley one by one. If the mountains are "wiggly" enough, the classical computer would have to climb more peaks than there are atoms in the universe.

Why Should You Care?

It Defines the Boundary: This paper draws a clear line in the sand. It tells us exactly which mathematical functions are too hard for classical computers but easy for even a "weak" quantum computer.
Real-World Applications: These "wiggly" functions (like logarithms and exponentials) are everywhere in real life.
- Machine Learning: Calculating the "log-determinant" is crucial for training AI models.
- Physics: Calculating "partition functions" helps us understand how materials behave at different temperatures.
- Chemistry: Simulating molecules often requires these specific math operations.
The "Approximate Degree" is King: The paper elevates a specific math concept (approximate degree) to be the "boss" of complexity. It's not just about how big the numbers are; it's about how "wiggly" the shape of the problem is.

Summary in One Sentence

This paper proves that if you try to calculate the average of a "wiggly" mathematical function using a restricted quantum computer, you are solving a problem that is impossible for classical computers to do efficiently, and the "wiggliness" (approximate degree) of the function is the exact reason why.

1. Problem Statement

The paper investigates the computational complexity of estimating the normalized trace of a function of a Hamiltonian, specifically the quantity:
$\frac{1}{2^n} \text{Tr}[f(A)]$
where:

$A$ is a log-local Hamiltonian acting on $n$ qubits (a sum of terms, each acting on at most $O(\log n)$ qubits).
$f(x)$ is a continuous function defined on the spectrum of $A$ (typically mapped to $[-1, 1]$ ).
The goal is to approximate this value up to a constant additive error.

This problem is central to the One-Clean-Qubit (DQC1) model of quantum computation. While specific instances (like estimating partition functions or Jones polynomials) are known to be DQC1-complete, a general characterization of which functions $f(x)$ make the problem hard has been elusive. The authors aim to identify the structural property of $f(x)$ that governs this hardness.

2. Methodology

The authors develop a unified framework that bridges quantum circuit complexity, spectral theory of periodic Jacobi matrices, and polynomial approximation theory.

A. Circuit-to-Hamiltonian Construction with Tunable Parameters

Unlike previous approaches that relied on Taylor expansions and specific error controls, the authors construct a log-local Hamiltonian $A$ from a quantum circuit $U = U_m \cdots U_1$ .

They define $A$ as a sum of terms involving the circuit unitaries and free parameters $a_t, b_t$ .
Crucially, when restricted to the invariant subspace spanned by the evolution of an eigenstate $|\phi_\theta\rangle$ of $U$ (with eigenvalue $e^{i\theta}$ ), the Hamiltonian $A$ reduces to a periodic Jacobi matrix $A_\theta$ .
This matrix $A_\theta$ has a specific tridiagonal structure where the boundary terms depend on $e^{i\theta}$ and $e^{-i\theta}$ .

B. Connection to Periodic Jacobi Matrices and Discriminants

The authors utilize the spectral properties of periodic Jacobi matrices:

The characteristic polynomial of $A_\theta$ is given by $\det(xI - A_\theta) = e(\Delta(x) - \cos \theta)$ , where $\Delta(x)$ is the discriminant (a polynomial independent of $\theta$ ).
This implies that the eigenvalues of $A_\theta$ are the roots of $\Delta(x) = \cos \theta$ .
Consequently, $\text{Tr}[f(A_\theta)]$ can be related to $\cos \theta$ if $f(x)$ can be approximated by the discriminant $\Delta(x)$ .

C. Chebyshev Equioscillation Theorem and Approximate Degree

To link $f(x)$ to the discriminant $\Delta(x)$ , the authors employ the Chebyshev Equioscillation Theorem:

They define the approximate degree $\tilde{\text{deg}}_\varepsilon(f)$ as the minimum degree of a polynomial that approximates $f(x)$ within error $\varepsilon$ .
They construct a discriminant $\Delta(x)$ that acts as an oscillatory approximation of the "error term" $(f(x) - P^*(x))/E$ , where $P^*$ is the best polynomial approximation of lower degree and $E$ is the approximation error.
By ensuring the degree of $\Delta(x)$ is higher than the approximate degree of $f$ , they show that $\text{Tr}[f(A)]$ correlates directly with $\text{Re}(\text{Tr}[U])$ , which is known to be DQC1-complete.

D. Classical Query Complexity Lower Bound

To establish classical hardness, the authors:

Extend the $k$ -Forrelation problem to the DQC1 query model, defining a "Trace- $k$ " problem involving the normalized trace of a product of oracle operators and Hadamard gates.
Propose Conjecture 1.4: Estimating Trace- $k$ requires exponential classical queries ( $e^{\Omega(N^{1-2/k})}$ ).
Combine this conjecture with their circuit-to-Hamiltonian reduction to prove that estimating $\text{Tr}[f(A)]$ for sparse matrices requires exponential classical queries if the approximate degree of $f$ is high.

3. Key Contributions and Results

Main Theorem: DQC1-Completeness (Theorem 1.2)

The problem of estimating $\frac{1}{2^n} \text{Tr}[f(A)]$ is DQC1-complete if:

$f(x)$ is a continuous function.
The approximate degree $\tilde{\text{deg}}_\varepsilon(f) = \Omega(\text{poly}(n))$ .
A technical condition holds: $E_d / E_{d-1} < 1/2$ , where $E_d$ is the best uniform polynomial approximation error of degree $d$ .

Implication: This condition holds for a broad class of functions, including:

Exponentials ( $e^{-\beta x}$ )
Trigonometric functions ( $\sin(tx), \cos(tx)$ )
Logarithms ( $\log(1+\beta x)$ )
Inverse-type functions ( $1/(\kappa x)$ )

This result generalizes previous specific hardness results to a unified characterization based on the approximate degree.

Classical Lower Bound (Theorem 1.5)

Assuming Conjecture 1.4 (on the hardness of Trace- $k$ ), the authors prove that for an $s$ -sparse log-local Hamiltonian $A$ , estimating the normalized trace of $f(A)$ requires:
$e^{\Omega((s/2)(\tilde{\text{deg}}_\varepsilon(f)-3)/9)}$
classical queries.

Quantum vs. Classical Separation

Quantum: The problem can be solved with $O(s \cdot \tilde{\text{deg}}_\varepsilon(f))$ queries using DQC1 algorithms (based on Quantum Singular Value Transformation or Phase Estimation).
Classical: Requires exponential queries in the approximate degree.
Result: This establishes an exponential quantum-classical separation for normalized trace estimation, governed entirely by the approximate degree of the function.

4. Significance

Unified Framework: The paper moves beyond function-specific analyses (e.g., only for polynomials or specific exponentials) to provide a general structural criterion (approximate degree) for DQC1-hardness.
Foundational Understanding: It clarifies the computational power of the DQC1 model, showing that even with only one clean qubit, the model can efficiently estimate spectral sums for functions that are classically intractable, provided the functions have high approximate degree.
Practical Relevance: The results apply to fundamental problems in numerical linear algebra and machine learning, such as log-determinant estimation ( $\text{Tr}[\log A]$ ) and partition function approximation, delineating the boundary where quantum advantage is possible.
Technical Innovation: The combination of periodic Jacobi operators with the Chebyshev equioscillation theorem provides a novel toolset for analyzing spectral sums, potentially applicable to other areas of quantum complexity and approximation theory.

5. Conclusion

The authors successfully identify the approximate degree as the fundamental parameter determining the complexity of normalized trace estimation in the DQC1 model. They prove that for functions with high approximate degree, the problem is DQC1-complete and exponentially hard for classical algorithms (under a plausible conjecture), while remaining efficiently solvable by quantum algorithms. This work offers a near-complete characterization of the computational hardness landscape for this class of problems.