WorksPhysics and Astronomy
DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians
Abstract
We study the computational complexity of estimating the normalized trace for a log-local Hamiltonian acting on qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions . We show that if is a continuous function with approximate degree , then estimating up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of . This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
Introduction
Introduced by Knill and Laflamme in 1998 [22], the One-Clean-Qubit model, also known as Deterministic Quantum Computation with One Qubit (DQC1), is a restricted model of quantum computation in which the input consists of a single pure qubit tensored with a maximally mixed -qubit state. The computation starts from
followed by a polynomial-size unitary circuit, after which the first qubit is measured in the computational basis. Despite its limited purity, DQC1 can efficiently solve certain problems for which no efficient classical algorithms are known. Moreover, it is believed to be strictly weaker than BQP, and cannot be efficiently simulated classically unless the polynomial hierarchy collapses to the third level [27]. These features make DQC1 a natural framework for studying intermediate quantum computational power.
A central computational task in this model is estimating the normalized trace of a polynomial-size quantum circuit [22, 34], which is DQC1-complete. A range of other DQC1-complete problems can be viewed as variants of this task, including approximating the Jones polynomial [36], estimating partition functions [7], and computing spectral quantities such as , [9, 13], and [32], among others [10, 11, 21, 28, 39]. These examples suggest that normalized trace estimation lies at the core of DQC1 complexity.
This perspective naturally leads to a general formulation: estimating spectral sums of the form , where is defined on the spectrum of . This raises the following fundamental question:
What property of a function makes the estimation of computationally hard in the DQC1 model?
Existing hardness results [7, 9, 11, 13, 32] are largely tailored to specific choices of , and a general characterization remains elusive.
Addressing this question is important from several perspectives. On the complexity-theoretic side, it identifies the key structural features of functions that govern DQC1-hardness, and moves beyond function-specific analyses toward a unified understanding based on a single parameter of . From a broader viewpoint, the DQC1 model captures the power of quantum computation with only a single clean qubit and is widely regarded as a minimal model exhibiting nontrivial quantum advantage; thus, understanding normalized trace estimation sheds light on the fundamental capabilities and limitations of this model. On the practical side, spectral sums of the form arise ubiquitously in numerical linear algebra and machine learning. For instance, the log-determinant plays a central role in marginal likelihood estimation in kernel methods and in training Gaussian processes or Gaussian graphical models [12, 30]. More broadly, such quantities underpin tasks including trace estimation, partition function approximation, and matrix function evaluation. Efficient classical [6, 13, 20, 29] and quantum [9, 17, 24, 41] algorithms have been developed for these problems. Consequently, understanding when normalized spectral sum estimation becomes computationally hard helps delineate the fundamental limits of efficient classical computation, as well as the boundary between classical and quantum advantage.
Main results
Regarding the above fundamental problem, we approach it from two viewpoints: (i) establishing a general result for DQC1-completeness; and (ii) proving a lower bound on the classical query complexity. From our results, we see that the approximate degree is a key parameter in determining the computational complexity of normalized trace estimation.
To start, we define the following problem.
Problem 1.1 (Normalized trace estimation problem). Let be a continuous function, and let be a log-local Hamiltonian acting on qubits. In the normalized trace estimation problem, we aim to decide whether
Equivalently, we aim to approximate up to an additive error of at most .
Let be a continuous function. For any integer , we define
to be the best polynomial approximation error of degree at most over .
Theorem 1.2 (DQC1-completeness). Assume that is a continuous function. Suppose there exists a constant such that and . Then the “normalized trace estimation problem” is DQC1-complete.
We now briefly discuss the assumptions and implications of Theorem 1.2. Formal definitions of DQC1-completeness and approximate degree are given in Definitions 2.1 and 2.6.
First, the restriction that the spectrum of lies in is without loss of generality, as we usually handle bounded/unitary operators on quantum computers. More generally, the theorem applies whenever the domain of contains the spectrum of . In addition, after an affine rescaling, the domain can be mapped to .
Second, the log-locality assumption on is natural and necessary in the DQC1 setting. By definition, a log-local Hamiltonian is a sum of terms, each acting nontrivially on at most qubits. This matches the computational power of DQC1, since DQC1 is equivalent to DQC for clean qubits [36]. In particular, quantum algorithms for estimating in the DQC1 model typically require ancillas when is log-local [9].
Third, the approximate-degree condition is natural and, although not stated explicitly, appears implicitly in prior works [7, 9, 13, 32]. Indeed, since can always be approximated by a polynomial of degree , a small approximate degree (e.g., ) would allow to be computed efficiently by direct expansion, given that is log-local with terms, e.g., see the classical algorithm given in [13].
Finally, the condition arises in our analysis via a result from classical polynomial approximation theory (see Theorem 2.10). It reflects a geometric separation between successive best-approximation errors and is satisfied by a broad class of functions commonly encountered in practice, including exponentials , trigonometric function , logarithms , and inverse functions whenever the parameters are bounded away from degenerate regimes; see the discussion below Remark 2.11. While this assumption is sufficient for our reduction, we do not expect it to be intrinsic. Indeed, in [31], with the assistance of GPT, we relaxed this condition to Lipschitz continuity, thereby establishing DQC1-completeness for all Lipschitz continuous functions within our framework. Since the proof is already presented clearly in [31], we do not reproduce it here.
As another result, we study the hardness from the viewpoint of query complexity. We now assume that is an -sparse Hermitian matrix, i.e., each row has at most nonzero entries. We also assume standard oracle access to via the following two oracles:
Given indices , oracle returns the -th entry of ;
Given an index , for any , oracle returns the position of the -th nonzero entry in the -th row.
In the course of proving a classical query lower bound, we need a lower bound for an analogue of the -Forrelation problem [1] in the DQC1 query model. More precisely, we consider an extension of the -Forrelation problem [1] in the DQC1 query model, defined as follows, where :
Here and are oracles. In this problem, we aim to estimate up to constant additive accuracy. This quantity can be viewed as a natural DQC1 analogue of the -Forrelation problem, where acceptance probabilities are replaced by normalized traces.
In the DQC1 query model, we can estimate to constant accuracy using quantum queries. Regarding the classical hardness, we have the following result.
Proposition 1.3. Estimating up to constant additive accuracy is DQC1-complete.
Concerning the lower bound on classical query complexity, we currently have only limited observations. On one hand, let denote the unitary in (4). Then , i.e., it is the average of the diagonal entries of . In contrast, the -Forrelation problem corresponds to estimating a single matrix element such as , for which a lower bound of is known [2]. While involves an average over such terms, these quantities are highly correlated through the shared oracle access, and it is unclear how to exploit this averaging to substantially reduce query complexity. This suggests that estimating remains hard. On the other hand, combining [2 Theorem 3.4] and [18 Theorem 1.5], we obtain that for , the -norm of the level- Fourier coefficients satisfies up to lower-order factors. By [2 Corollary 3.5], any decision tree of depth satisfies . Comparing these bounds suggests that for all , which in turn yields . Finally, using a similar technique [2], one can easily prove a lower bound of , with the exception that the additive error is of order , which is too small.
The above motivates the following conjecture.
Conjecture 1.4. Estimating up to an additive error (depending only on ) requires classical queries.
Regarding Conjecture 1.4, Shepherd made the following partial progress in [35 Proposition 3.3.6].
Proposition 1.5. Estimating up to a constant additive error requires classical queries.
With the above proposition, we have the following result.
Theorem 1.6 (Classical lower bound on query complexity). *Let be an integer. Assume that is a continuous function. Suppose there exists a constant
such that and . Then there is an -sparse, log-local Hamiltonian for which
classical queries are required to estimate the normalized trace of up to a constant accuracy.
As discussed in the abstract, the condition can be relaxed to Lipschitz condition in Theorems 1.2 and 1.6. Taken together, Theorems 1.2 and 1.6 identify the approximate degree of as the fundamental parameter governing the computational hardness of normalized trace estimation in the DQC1 model. More broadly, approximate degree has long played a central role in characterizing computational complexity, particularly for Boolean functions [3, 8, 26], and our result extends this perspective to the setting of quantum spectral sum estimation.
Technical overview
Our proof departs fundamentally from previous approaches, which are based on refinements of Brandão’s framework [7] using Taylor expansions together with delicate error control on spectral sums (see, e.g., [13, 32]). While these works combine circuit-to-Hamiltonian constructions with function-specific and technically involved analyses, our approach provides a unified and conceptually clean framework that applies to a broad class of functions through a single structural mechanism.
The starting point of our construction is still the circuit-to-Hamiltonian paradigm, but with the introduction of tunable parameters. Given an -qubit quantum circuit such that and each acts on qubits, we consider the log-local Hamiltonian
where , are free parameters and . This Hamiltonian is log-local and consists of terms. The dimension of is .
A key observation is that for any eigenpair of , the restriction of to the invariant subspace spanned by
is a periodic Jacobi matrix of the form
As a consequence, the trace decomposes as
Since estimating is DQC1-complete, to establish the DQC1 completeness of estimating the normalized trace , it suffices to relate to for any fixed . This connection is established through classical results on periodic Jacobi matrices and the Chebyshev equioscillation theorem.
More precisely, the characteristic polynomial of admits the representation
where , known as the discriminant, is independent of . A direct calculation shows that . Moreover, for any , the equation has real zeros, which are the eigenvalues of .
A natural intuition is that if closely approximates , then will correlate with . However, this intuition must be refined: is an oscillatory polynomial that intersects any horizontal line at exactly real points, a property that a generic function usually does not possess. To exploit this structure, we invoke the Chebyshev equioscillation theorem [19], which characterizes optimal min–max polynomial approximations. Roughly speaking, if is the best uniform polynomial approximation of of degree , then oscillates with alternating points, see Theorem 2.4 below.
We show that, after appropriate normalization, there is a discriminant that can be identified with an oscillatory approximation of , where . Through , we can reconstruct a periodic Jacobi matrix of the form (1.8). Moreover, , which implies that is independent of and can be computed efficiently in time. Together with (1.9), we obtain the desired correspondence between and .
In this process, we can choose the degree of as the approximate degree for a fixed precision . In addition, we establish a connection between Chebyshev equioscillation theorem and the approximate degree of , revealing approximate degree as the fundamental parameter governing DQC1-hardness of normalized trace estimation.
Regarding the query complexity lower bound, we extend the -Forrelation problem [1] to the DQC1 model. Specifically, we consider the problem of estimating the normalized trace of , where is the Hadamard gate and are oracle operators. Combining the lower bound for estimating with the connection established above between and , we obtain a lower bound for estimating .
Comparison with previous work [13]
Theorem 4.8 in [13] establishes DQC1-hardness for estimating in the block-encoding model. Concretely, it assumes the existence of a unitary with ancillas such that its top-left corner approximates , and that and on admit polynomial approximations of degree , with being Lipschitz continuous with Lipschitz constant . Under these assumptions, estimating is DQC1-hard.
While this result provides a valuable characterization, the block-encoding assumption is somewhat restrictive for natural Hamiltonians. For instance, when is a linear combination of Paulis, the LCU technique gives , and the block encoding requires ancilla qubits. When is sparse, equals the maximal number of non-zero entries in any row or column, and the block encoding uses ancillas. In both cases, achieving is nontrivial, even if is known, e.g., see [26], page 23, arXiv version. Moreover, the requirement of appears primarily as a technical condition in the proof, rather than reflecting an intrinsic hardness property of the problem. Finally, in this model, estimating is already DQC1-complete (see [13], Theorem 4.6), whereas this is not automatically the case for log-local Hamiltonians.
In contrast, apart from the restriction , our Theorem 1.2 establishes DQC1-hardness for log-local Hamiltonians under a natural and simple condition based solely on the approximate degree of , without requiring or additional assumptions. This yields a unified and broadly applicable framework for understanding the hardness of normalized trace estimation.
Additionally, in [13 Theorem 1.1], the authors provide a classical algorithm for estimating the normalized trace of for any -sparse matrix . Specifically, if is a degree- polynomial satisfying for all , then there exists a classical algorithm with query complexity that outputs an -approximation of the normalized trace of . This result extends naturally to continuous functions via polynomial approximation. Since the complexity depends on the polynomial degree, one aims to approximate by a polynomial of minimal degree, i.e., its approximate degree. In contrast, Theorem 1.6 establishes an exponential lower bound in terms of the approximate degree. Although a gap remains between the upper and lower bounds, both results indicate that the approximate degree is a key parameter governing the computational complexity of this problem.
Preliminaries
In this section, we list and also prove some results that are useful throughout this work.
One clean qubit model
The one clean qubit model (DQC1) is a restricted model of quantum computation that captures nontrivial quantum computational power with minimal quantum resources. In this model, the input consists of a single pure qubit (the “clean” qubit) together with a collection of qubits in the maximally mixed state. A polynomial-size quantum circuit is then applied, and only the clean qubit is measured at the end of the computation, see Figure 1.

Figure 1. The DQC1 computational model.
A simple calculation shows that the probability of measuring zero is . So the real part of the normalized trace can be estimated up to accuracy by repeating the procedure times. The imaginary part can be estimated similarly. This is a class of central problems that can be efficiently solved by the DQC1 model, and is believed to be classically hard.
The study of DQC1 has led to the definition of the complexity class DQC1, which consists of problems efficiently solvable within this model. Understanding the power and limitations of DQC1 provides insight into the role of quantum coherence and entanglement in quantum computation, and helps clarify which quantum resources are essential for achieving quantum speedups.
Definition 2.1 (DQC1 complexity class). A language is in DQC1 if and only if, for any -bit string , there exists a polynomial-time generated quantum circuit acting on qubits such that for some specified polynomial ,
where
is the probability of measuring the clean qubit at 1.
In DQC1, we are allowed to repeat the computation a polynomial number of times, which is done outside the model, so the above is equivalent to the setting with when and when . This is because by repeating the experiment times and taking the majority vote, one can achieve high probability of correctness [36].
Proposition 2.2 (Theorem 2 of [22]). Let , which can be a constant, and let be a unitary acting on qubits. Then determining or is DQC1-complete. Equivalently, estimating is DQC1-complete.
Proposition 2.3 (Corollary 6 of [9]). Assume that is a log-local Hamiltonian acting on qubits and is Lipschitz continuous with Lipschitz constant , then there is a DQC1 algorithm to estimate , where .
The quantum algorithm in the above theorem is mainly based on quantum phase estimation, so the cost is linear in . When , we can choose a smaller such that is small. The key point here is that , have order . For bounded Lipschitz continuous functions, we have via Markov brothers’ inequality [25], where is the approximate degree, see Definition 2.6.
Periodic Jacobi matrices
We consider the following special type of Jacobi matrices, which is known as periodic Jacobi matrices, e.g., see [4, 5, 14, 38]:
where , and . Obviously, is Hermitian, and so all the eigenvalues are real.
Let be the tridiagonal matrix of dimension with subdiagonal entries (i.e., setting in ) and let be the tridiagonal matrix of dimension with subdiagonal entries (i.e., removing the first and last row/column in ), then it is easy to compute that the characteristic polynomial of is (e.g., see [5])
where
The polynomial is known as the discriminant of and plays an important role in the study of . For example, assume , for all , then a simple calculation shows that , where is the -th Chebyshev polynomial of the first kind. From (15) and the property that is Hermitian, we know that always has real zeros for any . Based on this, it is not hard to see that is an oscillating function and it intersects any horizontal line for times exactly. This is a property similar to the Chebyshev Equioscillation Theorem described below.
Chebyshev Equioscillation Theorem and approximate degree
The Chebyshev Equioscillation Theorem is a central result in minimax approximation theory. It characterizes exactly when a polynomial is the unique minimax approximation to a continuous function.
Theorem 2.4 (Chebyshev Equioscillation Theorem [19]). Let be a continuous function. Among all the polynomials of degree , the polynomial minimizes the uniform norm of the difference if and only if there are points such that
where is either or . That is, the polynomial oscillates above and below at the interpolation points, and does so to the same degree.
Remark 2.5. Figure 2 is a simple illustration of the Chebyshev Equioscillation Theorem. The minimax polynomial is unique. The alternation property also determines and uniquely. But the points need not be unique and depend on and . For certain classical systems (e.g., Chebyshev polynomials), they are known explicitly; in general, they can be computed numerically (e.g., by the Remez algorithm [15], which costs at most ).
Figure 2. Illustration of the Chebyshev Equioscillation Theorem.
Polynomial approximation provides a fundamental approach to representing functions. For a given function , one may study the best degree- polynomial approximation in the uniform norm, a classical problem in approximation theory. From the perspective of computational complexity, a more relevant quantity is the approximate degree: the minimal degree of a polynomial that approximates within error in the uniform norm (see the definition below). This quantity captures the intrinsic complexity of approximating and plays a central role in various computational models.
Computing the approximate degree is generally challenging, as it involves optimization over an integer-valued parameter rather than a continuous one. A powerful technique for analyzing approximate degree is the dual polynomial method [8], which provides certificates for lower bounds and has been widely used in complexity theory.
Since quantum algorithms typically involve unitary or bounded operators whose spectra lie in , we restrict our attention to functions defined on subintervals of .
Definition 2.6 (Approximate degree). Let be a function and let . We define the approximate degree of as
We establish below a connection between the dual polynomial method and the Chebyshev Equioscillation Theorem, which might be of independent interest. For any fixed , the dual polynomial method considers the following linear semi-infinite program (LSIP):
By known results from LSIP [23, 33], there exist such that (20) is equivalent to the following linear program (here refers to the number of free parameters in the LSIP (20)):
Proposition 2.7. The points are exactly the equioscillation points in the Chebyshev Equioscillation Theorem.
Proof. See Appendix § 7.
This result implies that in the Chebyshev Equioscillation Theorem, we can fix the degree as the approximate degree for any desired accuracy , e.g., , we then will obtain a min-max polynomial approximation of with error .
Constructing periodic Jacobi matrices from prescribed spectra
In this part, we establish a connection between periodic Jacobi matrices and polynomial approximation. The following is a known result about periodic Jacobi matrices.
Proposition 2.8 (Theorem 4.2 of [14]). Let be a polynomial of degree . Then there is a periodic Jacobi matrix such that its discriminant is if and only if
the coefficient of in is positive, and
has distinct local extrema with for all .
Moreover, there is also an efficient algorithm to construct when given .
From (15), suppose is the discriminant of , then it is also the discriminant of for all . Moreover, is the leading coefficient of . It is easy to check that the second property in Proposition 2.8 is easily satisfied once has the oscillating property similar to the Chebyshev Equioscillation Theorem. This means that if where , , are the same as those in the Chebyshev Equioscillation Theorem, then will be a discriminant of some periodic Jacobi matrix. In the Chebyshev Equioscillation Theorem, is the polynomial with minimal degree that approximates up to error , so to ensure a nontrivial approximation, we have to choose such that .
To continue, we recall the following concept from polynomial approximation theory.
Definition 2.9. Let be a continuous function. For any integer , define
to be the best uniform (minimax) polynomial approximation error of degree at most over . When there is no risk of confusion, we sometimes simply write it as . The polynomial of degree at most that attains this minimum is denoted as .
In practice, we start from , then compute the approximate degree , finally we have and . Equality holds when . We indeed have . Moreover, for any , we always have .
Theorem 2.10. Let be a continuous function and with . For any , there is a periodic Jacobi matrix of the form (14) with , dimension and discriminant , such that
Proof. Let denote the degree polynomial in computing . Without loss of generality, we assume that the leading coefficient of is positive; otherwise, below should be multiplied by the sign of this leading coefficient. Denote
then it satisfies
By Theorem 2.4, there exist points and such that . Without loss of generality, we also set . Since , by (29) the sign of satisfies
and hence oscillates between and . By the Intermediate Value Theorem, there exist points satisfying and . By Rolle’s theorem,
there exist points satisfying and . Since is a polynomial with degree and has at most zeros, there are no other zeros other than . Therefore, has oscillating signs on a sequence of intervals . On each interval , attains the maximal/minimal value at , so we have
as . In conclusion, has extrema points with oscillating signs and . Now order the critical points from right to left by setting for . Then . Since the leading coefficient of is positive, for all . So for all . By Proposition 2.8, there exists a periodic Jacobi matrix with discriminant . The claim (27) follows directly from (2.19}.
Finally, it remains to show . For any , since the values alternate in sign and satisfy , we have for all . Hence, each closed interval contains a root of . Because has degree , these are all its roots, and all of them lie in . Taking , we conclude that every eigenvalue of lies in .
Remark 2.11. The above result is a key ingredient in the proofs of our main theorems. We need to choose and as small constants, so that is also a constant. However, the bound for is not clear. The ideal situation for us is . In this case, we can always find a constant such that is a small constant. Even in the worst case, is still a small constant, then as long as , we then have , which is a small constant.
Many functions in practice satisfy the condition when is reasonably large. Asymptotically, when is analytic and can be analytically continued to the open Bernstein ellipse , then ; see [37 Theorem 8.2]. Hence, heuristically, . So the condition is expected to hold when .
To be more exact, we consider three typical functions below as examples. Recall that for continuous functions, the Chebyshev expansion provides (up to logarithmic factors) near-best polynomial approximation; see [37 Theorem 16.1]. In particular,
where is the degree- truncated Chebyshev expansion. Below, we use this to calculate . We denote , and so .
Exponential function: The function for appears in partition function computations [7]. For this function, from the Chebyshev expansion, we have , where is the modified Bessel function of the first kind. Using the standard asymptotic behavior of Bessel functions, asymptotically, when we have , which is smaller than when .
Trigonometric function: The function appears as the imaginary part of in Hamiltonian simulation [16], where and . It is an entire function with Chebyshev expansion , where are Bessel functions of the first kind. So if is odd. So when , we asymptotically have , which is smaller than when . A similar result holds for .
Logarithmic function: The function with in the interval , is commonly used in the calculation of log-determinant [20]. For this function, we have , where . Thus when .
Inverse-type function: The function over the interval is used in solving linear systems [16], where . Now . In this case, we have , and so when .
Proof of Theorem 1.2
Theorem 3.1 (Restatement of Theorem 1.2). Let be a small constant. Assume that is a continuous function with and . Then the “normalized trace estimation problem” is DQC1-complete.
Proof. By Proposition 2.3, the problem is in DQC1. Next, we show that it is DQC1-hard. Let be a unitary acting on qubits such that each acts on at most qubits, with . In the proof below, we first assume exactly, and will discuss how to remove this assumption at the end of the proof.
Consider
where we set . Let be an eigenstate of , i.e., , and let
Then it is easy to check that
Thus in the basis , the operator is a periodic Jacobi operator of the following form
Due to the orthogonality of , we have that
By Theorem 2.10, we can construct a periodic Jacobi matrix such that the dimension is and discriminant . So the characteristic polynomial is , where . By (27), we choose such that is a constant and
By Remark 2.11, without loss of generality, we assume that is a small constant when . The above implies that
As a discriminant polynomial, we have that , i.e., . So we have
Since has degree , which is smaller than the size of , we have that is independent of and can be computed efficiently and exactly. Thus, we can simply denote it as by setting . One simple way to see this is using random walks. Indeed, can be viewed as the adjacency matrix of a circle of nodes. So, when doing random walks of length less than , summing all the weights to compute the trace, the overall weight for vertex is the sum of weights of all walks that pass through the edge between vertex 1 and vertex for even times, back and forth.
As a result of (42) and (45), we have
Notice that the dimension of is , it follows that
Thus, if we can estimate for some small constant , we then can estimate with . Since , are constants smaller than 1, we can choose small enough to ensure that is also a constant smaller than 1. By Proposition 2.2, estimating is DQC1-hard, so estimating is also DQC1-hard.
In the above proof, we used the property that . But is only determined by , this condition can be easily satisfied if we have because we can add identities into . This is why we assumed that in the theorem.
Lower bound on classical query complexity
In this section, we apply the connection established above to prove an exponential lower bound on the classical query complexity for estimating the normalized trace of . This establishes an exponential quantum–classical separation.
Recall that in [13 Theorem 1.1], given sparse access to an -sparse Hermitian matrix with , and a degree- polynomial satisfying for all , there exists a classical algorithm with query complexity that outputs an -approximation of the normalized trace of . The oracles are standard: one oracle returns the nonzero entries of , while the other returns the positions of the nonzero entries in each row. Basically, their algorithm works as follows: for each matrix monomial , sparsity allows us to estimate one diagonal entry efficiently (for example, using the definition, which costs ). Since the normalized trace is the expectation value of the diagonal entries, samples are enough to approximate it up to an additive error .
The result of [13] also holds when is continuous on . In this case, one may first approximate by a degree- polynomial and then apply their result. Since the complexity depends on the degree, it is desirable that this approximation has low degree. The minimum degree required for such an approximation is known as the approximate degree , defined in (19). In Theorem 4.1, we prove a lower bound showing that the exponential dependence on the approximate degree is necessary.
To prove the lower bound, we first extend the -Forrelation problem [1] to the DQC1 query model and prove an exponential lower bound, which we then use to obtain the desired result.
The DQC1 query model has a structure similar to the BQP query model; see Figure 3. Let be an oracle defined by an input via
Figure 3. A -query DQC1 algorithm.
where . The goal is to compute a function of using as few oracle queries as possible. In a -query DQC1 algorithm, we apply a unitary
where are independent of . A natural quantity that can be computed in this model is the normalized trace . We can also consider a more general setting in which different oracles are used, with inputs .
We now consider an extension of the -Forrelation problem in the DQC1 query model. Define the normalized trace function
where is the Hadamard gate. Recall that the function studied in the -Forrelation problem corresponds to a single entry of the unitary . Thus, the above function can be viewed as a natural generalization of the -Forrelation problem.
With Proposition 1.5, we now prove the classical lower bound of normalized trace estimation.
Theorem 4.1 (Restatement of Theorem 1.6). Let be an integer, and be a small constant. Assume that is a continuous function with and . Then there is an -sparse, -local Hamiltonian such that
classical queries are required to estimate the normalized trace of up to a constant accuracy.
Proof. We consider in . Now we have
For convenience, we assume the sparsity and . The analysis below does not change too much if is not a factor of .
We decompose as (this is the only place we used the result )
There are factors in the above decomposition. Each factor is -sparse. As a result, can be rewritten as a product of -sparse unitaries and -sparse unitaries. Namely, there are unitaries in the decomposition of .
Following the proof of Theorem 3.1, we can construct a Hamiltonian , which is -sparse and -local, such that (see (48))
Thus, if we can estimate for some small constant , we then can estimate with a constant. Moreover, , i.e., and . By Proposition 1.5, we obtain a lower bound of estimating , which is
This completes the proof.
In comparison, the quantum algorithm only costs , see [40]. As a result, there is an exponential separation between quantum and classical algorithms for normalized trace estimation.
Finally, inspired by the BQP-completeness of the forrelation problem in [1], we show the following result, which might be of independent interest.
Proposition 4.2 (Restatement of Proposition 1.3). Estimating up to a constant accuracy is DQC1-complete.
Proof. From the proof of [1 Theorem 5.2], Aaronson and Ambainis indeed obtained the following strong result: Let be a -qubit quantum circuit over the universal gate set , where CCSIGN is a three-qubit gate that maps to . Assume there are Hadamard gates in . Then there exist with such that , where is either or depending on the number of appearance of the one dummy qubit in the construction. This implies that
Since comes from a universal gate set, estimating is DQC1-complete. As a result, estimating is also DQC1-complete.
Conclusions
In this work, we provide a general characterization of when estimating the normalized trace of functions of log-local Hamiltonians is DQC1-complete. We also prove an exponential classical lower bound for this problem. Together, these results provide a near-complete characterization of the computational hardness of normalized trace estimation in the DQC1 model. Moreover, both results identify the approximate degree as a key parameter governing the complexity of this problem.
We conclude with several interesting directions for future investigation:
The DQC1 algorithm proposed in [9] for estimating the normalized trace of applies to any -Lipschitz function with . This Lipschitz condition arises from the use of quantum phase estimation. Can the assumptions on the function in our main DQC1-hardness theorem Theorem 1.2 be weakened? For example, can the result be extended to all continuous functions? We conjecture that this is the case. However, resolving this question would likely require new techniques to improve the approximation result in Theorem 2.10, in particular to remove the condition .
It remains interesting to determine the optimal classical query complexity of . Proposition 1.5 gives an lower bound for , which is sufficient for establishing our exponential quantum–classical separation. However, this bound does not match the conjectured bound from Conjecture 1.4. More generally, resolving Conjecture 1.4 remains an interesting open problem.
As studied in [31], with the help of GPT 5.6 Sol, the condition can be relaxed to a Lipschitz condition. From our point of view, this means that the first question above is solved now. Regarding the second question, the lower bound in [35] is not tight, but strong enough for our quantum-classical separation. Resolving Conjecture 1.4 is still an interesting open problem for general , even for .
Acknowledgements
ZJ is supported by the National Key Research Project of China (Grant No. 2023YFA1009403), the National Natural Science Foundation of China (Grant No. 12347104), and Beijing Science and Technology Planning Project (Grant No. Z25110100810000). CS and YZ are supported by the National Key Research Project of China (Grant No. 2023YFA1017200). YZ is also supported by the European Research Council (ERC) via the Starting Grant QuanThermal (101222179). TL and XZ are supported by the National Natural Science Foundation of China (Grant No. 62372006). CS would like to thank Kewen Wu for helpful discussions on Conjecture 1.4 and for suggesting the paper [35].
Proof of Proposition 2.7
This claim shows that in the Chebyshev Equioscillation Theorem, . We now prove this claim. Note that the dual form of (23) is
The dual solution is
where is a free parameter, which is determined by the constraint (A.3). To recover the optimal solution of the primal LP, we assume that . Let with . Then in matrix form, (24) is
The objective function can be written as
Therefore, the dual form has an objective function
The constraints are described by the following
Namely,
Denote , then we obtain the dual LP (A.1). WLOG, we assume that and , then
From the complementary slackness between LP and dual LP, we know that if (or ), then the corresponding constraint of the primal LP is tight, i.e., it is an equality in (A.5). We now assume is even for convenience. Then we obtain the following linear system:
Using , we can simplify the above as follows:
The above defines a linear system of with a unique solution. For , we have from (A.13). This coincides with the Chebyshev Equioscillation Theorem, and the Remez algorithm can find the points efficiently.
Remark A.1. In [26], Theorem 1.10 of the arXiv version, it was proved that the “entry estimation problem”, i.e., estimating an entry of a function of a matrix, is BQP-complete. This result depends on the construction of a certain tridiagonal matrix from its spectra. The efficiency of the construction, which further depends on the finding of described in the LP (23), is not discussed in that paper. From Proposition 2.7, we see that these points can be computed efficiently by the Remez algorithm. This guarantees the efficiency of the construction of the tridiagonal matrix in the proof of the BQP-completeness.
References
- [1]Scott Aaronson and Andris Ambainis. Forrelation: A problem that optimally separates quantum from classical computing. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 307–316, 2015.arxiv.org/abs/1411.5729
- [2]Nikhil Bansal and Makrand Sinha. k-Forrelation optimally separates quantum and classical query complexity. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1303–1316, 2021.arxiv.org/abs/2008.07003
- [3]Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pages 352–361, 1998.
- [4]Daniel Boley and Gene H Golub. A modified method for reconstructing periodic Jacobi matrices. Mathematics of Computation, 42(165):143–150, 1984.
- [5]DL Boley and Gene Howard Golub. The matrix inverse eigenvalue problem for periodic Jacobi matrices. Technical report, Computer Science Department, Stanford University, 1978.
- [6]Christos Boutsidis, Petros Drineas, Prabhanjan Kambadur, Eugenia-Maria Kontopoulou, and Anastasios Zou zias. A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix. Linear Algebra and its Applications, 533:95–117, 2017.arxiv.org/abs/1503.00374
- [7]Fernando GSL Brandão. Entanglement theory and the quantum simulation of many-body physics. arXiv:0810.0026, 2008.
- [8]Mark Bun, Justin Thaler, et al. Approximate degree in classical and quantum computing. Foundations and Trends® in Theoretical Computer Science, 15(3-4):229–423, 2022.
- [9]Chris Cade and Ashley Montanaro. The Quantum Complexity of Computing Schatten p-norms. In Stacey Jeffery, editor, 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018), volume 111 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:20, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.arxiv.org/abs/1706.09279
- [10]Marco Cerezo, Alexander Poremba, Lukasz Cincio, and Patrick J Coles. Variational quantum fidelity estimation. Quantum, 4:248, 2020.
- [11]Anirban N Chowdhury, Rolando D Somma, and Yiğit Subaşı. Computing partition functions in the one-clean-qubit model. Physical Review A, 103(3):032422, 2021.DOI
- [12]Kun Dong, David Eriksson, Hannes Nickisch, David Bindel, and Andrew G Wilson. Scalable log determinants for Gaussian process kernel learning. Advances in Neural Information Processing Systems, 30, 2017.arxiv.org/abs/1711.03481
- [13]Roman Edenhofer, Atsuya Hasegawa, and François Le Gall. Dequantization and hardness of spectral sum estimation. arXiv:2509.20183, 2025.arxiv.org/abs/2509.20183
- [14]Warren E Ferguson. The construction of Jacobi and periodic Jacobi matrices with prescribed spectra. Mathematics of Computation, 35(152):1203–1220, 1980.
- [15]W Fraser. A survey of methods of computing minimax and near-minimax polynomial approximations for functions of a single independent variable. Journal of the ACM (JACM), 12(3):295–314, 1965.DOI
- [16]András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019. arXiv:1806.01838.DOI
- [17]Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. A quantum algorithm for estimating the determinant. arXiv:2504.11049, 2025.arxiv.org/abs/2504.11049
- [18]Uma Girish. Fourier spectrum of noisy quantum algorithms. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 305–313, 2026.arxiv.org/abs/2510.06385
- [19]Michael Golomb. Lectures on Theory of Approximation. Argonne National Laboratory, Applied Mathematics Division, 1962.
- [20]Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin. Approximating spectral sums of large-scale matrices using stochastic chebyshev approximations. SIAM Journal on Scientific Computing, 39(4):A1558–A1585, 2017.arxiv.org/abs/1606.00942
- [21]Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cinčio, Andrew T Sornborger, and Patrick J Coles. Quantum-assisted quantum compiling. Quantum, 3:140, 2019.DOI
- [22]Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. Physical Review Letters, 81(25):5672, 1998.DOI
- [23]Hang-Chin Lai and Soon-Yi Wu. On linear semi-infinite programming problems: An algorithm. Numerical Functional Analysis and Optimization, 13(3-4):287–304, 1992.DOI
- [24]Alessandro Luongo and Changpeng Shao. Quantum algorithms for spectral sums. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 24178–24188, 2026.
- [25]A. Markov. On a question by D. I. Mendeleev. Zap. Imp. Akad. Nauk. St. Petersburg, 62:1–24, 1890.
- [26]Ashley Montanaro and Changpeng Shao. Quantum and classical query complexities of functions of matrices. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), pages 573–584, 2024.
- [27]Tomoyuki Morimae, Keisuke Fujii, and Joseph F Fitzsimons. Hardness of classically simulating the one-clean-qubit model. Physical Review Letters, 112(13):130502, 2014.pubmed.ncbi.nlm.nih.gov/24745398
- [28]Subhayan Roy Moulik and Sergii Strelchuk. DQC1-hardness of estimating correlation functions. arXiv:2411.05208, 2024.arxiv.org/abs/2411.05208
- [29]Cameron Musco, Praneeth Netrapalli, Aaron Sidford, Shashanka Ubaru, and David P. Woodruff. Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:21, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.arxiv.org/abs/1704.04163
- [30]Carl Edward Rasmussen and Hannes Nickisch. Gaussian processes for machine learning (GPML) toolbox. The Journal of Machine Learning Research, 11:3011–3015, 2010.DOI
- [31]Changpeng Shao. Two Routes Beyond the Successive-Error Gap in DQC1 Normalized Trace Estimation. Available at https://changpeng-shao.github.io/DQC1_trace_estimation_beyond_gap.pdf.
- [32]Changpeng Shao and Xinzhao Wang. DQC1-hardness of estimating log-determinants. Available at https://changpeng-shao.github.io/complexity_logdet.pdf.
- [33]Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 58(2):133–161, 2009.DOI
- [34]Dan Shepherd. Computation with unitaries and one pure qubit. arXiv preprint quant-ph/0608132, 2006.DOI
- [35]Daniel James Shepherd. Quantum complexity: restrictions on algorithms and architectures. arXiv:1005.1425, 2010.arxiv.org/abs/1005.1425
- [36]Peter W Shor and Stephen P Jordan. Estimating jones polynomials is a complete problem for one clean qubit. Quantum Information & Computation, 8(8):681–714, 2008.
- [37]Lloyd N. Trefethen. Approximation Theory and Approximation Practice, Extended Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019.DOI
- [38]Pierre van Moerbeke. The spectrum of Jacobi matrices. Inventiones Mathematicae, 37(1):45–81, 1976.DOI
- [39]Qisheng Wang, Ji Guan, Junyi Liu, Zhicheng Zhang, and Mingsheng Ying. New quantum algorithms for computing quantum entropies and distances. IEEE Transactions on Information Theory, 70(8):5653–5680, 2024.
- [40]Yuxin Zhang and Changpeng Shao. Quantum space-depth tradeoffs for coherent block encodings. arXiv:2607.01843v2, 2026.arxiv.org/abs/2607.01843
- [41]Zhikuan Zhao, Jack K Fitzsimons, Michael A Osborne, Stephen J Roberts, and Joseph F Fitzsimons. Quantum algorithms for training Gaussian processes. Physical Review A, 100(1):012304, 2019.DOI

