betaFeedback

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 2−nTr[f(A)]2^{-n}\mathrm{Tr}[f(A)] for a log-local Hamiltonian AA acting on nn qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x)f(x). We show that if f(x)f(x) is a continuous function with approximate degree Ω(poly(n))Ω(\mathrm{poly}(n)), then estimating 2−nTr[f(A)]2^{-n}\mathrm{Tr}[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x)f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when AA 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 nn-qubit state. The computation starts from

ρ=∣0⟩⟨0∣⊗In2n,(1)\rho= |0\rangle\langle0| \otimes\frac{I_n}{2^n}, \tag*{(1)}

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 12nTr⁡[U]\frac{1}{2^n}\operatorname{Tr}[U] 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 12nTr⁡[e−βA]\frac{1}{2^n}\operatorname{Tr}[e^{-\beta A}] [7], and computing spectral quantities such as 12nTr⁡[A−1]\frac{1}{2^n}\operatorname{Tr}[A^{-1}], 12nTr⁡[Ad]\frac{1}{2^n}\operatorname{Tr}[A^d] [9, 13], and 12nTr⁡[log⁡(A)]\frac{1}{2^n}\operatorname{Tr}[\log(A)] [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 12nTr⁡[f(A)]\frac{1}{2^n}\operatorname{Tr}[f(A)], where f(x)f(x) is defined on the spectrum of AA. This raises the following fundamental question:

What property of a function f(x)f(x) makes the estimation of 12nTr⁡[f(A)]\frac{1}{2^n}\operatorname{Tr}[f(A)] computationally hard in the DQC1 model?

Existing hardness results [7, 9, 11, 13, 32] are largely tailored to specific choices of ff, 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 f(x)f(x). 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 Tr⁡[f(A)]\operatorname{Tr}[f(A)] arise ubiquitously in numerical linear algebra and machine learning. For instance, the log-determinant log⁡det⁡(A)=Tr⁡[log⁡(A)]\log\det(A)=\operatorname{Tr}[\log(A)] 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 f(x):[a,b]⊆[−1,1]→[−1,1]f(x): [a,b] \subseteq[-1,1] \to[-1,1] be a continuous function, and let AA be a log-local Hamiltonian acting on nn qubits. In the normalized trace estimation problem, we aim to decide whether

12nTr⁡[f(A)]≥23or12nTr⁡[f(A)]≤13.(2)\frac{1}{2^n}\operatorname{Tr}[f(A)] \ge\frac{2}{3} \quad\text{or}\quad \frac{1}{2^n}\operatorname{Tr}[f(A)] \le\frac{1}{3}. \tag*{(2)}

Equivalently, we aim to approximate 12nTr⁡[f(A)]\frac{1}{2^n}\operatorname{Tr}[f(A)] up to an additive error of at most 1/61/6.

Let f(x):[a,b]⊆[−1,1]→Rf(x): [a,b] \subseteq[-1,1] \to\mathbb{R} be a continuous function. For any integer dd, we define

Ed=min⁡deg⁡(P)≤dmax⁡x∈[a,b]∥f(x)−P(x)∥(3)E_d = \min_{\deg(P)\le d}\max_{x\in[a,b]}\lVert f(x)-P(x)\rVert \tag*{(3)}

to be the best polynomial approximation error of degree at most dd over [a,b][a,b].

Theorem 1.2 (DQC1-completeness). Assume that f(x):[a,b]⊆[−1,1]→[−1,1]f(x): [a,b] \subseteq[-1,1] \to[-1,1] is a continuous function. Suppose there exists a constant ε<1\varepsilon< 1 such that d:=deg⁡ε(f)=Ω(poly⁡(n))d := \deg_{\varepsilon}(f) = \Omega(\operatorname{poly}(n)) and Ed/Ed−1<1/2E_d/E_{d-1} < 1/2. 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 AA lies in [−1,1][-1,1] is without loss of generality, as we usually handle bounded/unitary operators on quantum computers. More generally, the theorem applies whenever the domain of f(x)f(x) contains the spectrum of AA. In addition, after an affine rescaling, the domain can be mapped to [−1,1][-1,1].

  • Second, the log-locality assumption on AA 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 O(log⁡n)O(\log n) qubits. This matches the computational power of DQC1, since DQC1 is equivalent to DQCkk for k=O(log⁡n)k = O(\log n) clean qubits [36]. In particular, quantum algorithms for estimating 12nTr⁡[f(A)]\frac{1}{2^n}\operatorname{Tr}[f(A)] in the DQC1 model typically require O(log⁡n)O(\log n) ancillas when AA is log-local [9].

  • Third, the approximate-degree condition deg⁡ε(f)=Ω(poly⁡(n))\deg_{\varepsilon}(f) = \Omega(\operatorname{poly}(n)) is natural and, although not stated explicitly, appears implicitly in prior works [7, 9, 13, 32]. Indeed, since f(x)f(x) can always be approximated by a polynomial of degree deg⁡ε(f)\deg_{\varepsilon}(f), a small approximate degree (e.g., O(log⁡n)O(\log n)) would allow Tr⁡[f(A)]\operatorname{Tr}[f(A)] to be computed efficiently by direct expansion, given that AA is log-local with poly⁡(n)\operatorname{poly}(n) terms, e.g., see the classical algorithm given in [13].

  • Finally, the condition Ed/Ed−1<1/2E_d/E_{d-1} < 1/2 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 e−βxe^{-\beta x}, trigonometric function sin⁡(tx),cos⁡(tx)\sin(tx),\cos(tx), logarithms log⁡(1+βx)\log(1+\beta x), and inverse functions 1/κx1/\kappa x whenever the parameters β,κ\beta,\kappa 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 AA is an ss-sparse Hermitian matrix, i.e., each row has at most ss nonzero entries. We also assume standard oracle access to AA via the following two oracles:

  1. Given indices (i,j)(i,j), oracle O1\mathcal{O}_1 returns the (i,j)(i,j)-th entry of AA;

  2. Given an index ii, for any j≤sj \le s, oracle O2\mathcal{O}_2 returns the position of the jj-th nonzero entry in the ii-th row.

In the course of proving a classical query lower bound, we need a lower bound for an analogue of the kk-Forrelation problem [1] in the DQC1 query model. More precisely, we consider an extension of the kk-Forrelation problem [1] in the DQC1 query model, defined as follows, where N=2nN = 2^n:

Trace⁡k(x):=1NTr⁡[Ox1H⊗nOx2H⊗n⋯H⊗nOxkH⊗n].(4)\operatorname{Trace}_k(x) := \frac{1}{N}\operatorname{Tr}\left[\mathcal{O}_{x_1}H^{\otimes n}\mathcal{O}_{x_2}H^{\otimes n}\cdots H^{\otimes n}\mathcal{O}_{x_k}H^{\otimes n}\right]. \tag*{(4)}

Here x1,…,xk∈{±1}Nx_1,\ldots,x_k \in\{ \pm1 \}^N and Ox1,…,Oxk\mathcal{O}_{x_1},\ldots,\mathcal{O}_{x_k} are oracles. In this problem, we aim to estimate Trace⁡k(x)\operatorname{Trace}_k(x) up to constant additive accuracy. This quantity can be viewed as a natural DQC1 analogue of the kk-Forrelation problem, where acceptance probabilities are replaced by normalized traces.

In the DQC1 query model, we can estimate Trace⁡k(x)\operatorname{Trace}_k(x) to constant accuracy using kk quantum queries. Regarding the classical hardness, we have the following result.

Proposition 1.3. Estimating Trace⁡k\operatorname{Trace}_k 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 UU denote the unitary in (4). Then Trace⁡k(x)=Ei∈[N]⟨i∣U∣i⟩\operatorname{Trace}_k(x) = \mathbb{E}_{i \in[N]}\langle i|U|i\rangle, i.e., it is the average of the diagonal entries of UU. In contrast, the kk-Forrelation problem corresponds to estimating a single matrix element such as ⟨0n∣U∣0n⟩\langle0^n|U|0^n\rangle, for which a lower bound of Ω~(N1−1/k)\widetilde{\Omega}(N^{1-1/k}) is known [2]. While Trace⁡k\operatorname{Trace}_k involves an average over NN 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 Trace⁡k\operatorname{Trace}_k remains hard. On the other hand, combining [2 Theorem 3.4] and [18 Theorem 1.5], we obtain that for f(x)=Trace⁡kf(x) = \operatorname{Trace}_k, the ℓ1\ell_1-norm of the level-ℓ\ell Fourier coefficients satisfies L1,ℓ(f)≤N(ℓ−2)/2L_{1,\ell}(f) \le N^{(\ell-2)/2} up to lower-order factors. By [2 Corollary 3.5], any decision tree of depth dd satisfies L1,ℓ≤dℓ/2L_{1,\ell} \le d^{\ell/2}. Comparing these bounds suggests that dℓ/2≳N(ℓ−2)/2d^{\ell/2} \gtrsim N^{(\ell-2)/2} for all ℓ≤k\ell\le k, which in turn yields d≳N1−2/kd \gtrsim N^{1-2/k}. Finally, using a similar technique [2], one can easily prove a lower bound of Ω~(N1−2/k)\widetilde{\Omega}(N^{1-2/k}), with the exception that the additive error is of order 1/N1/N, which is too small.

The above motivates the following conjecture.

Conjecture 1.4. Estimating Trace⁡k\operatorname{Trace}_k up to an additive error ϵk\epsilon_k (depending only on kk) requires Ω~(N1−2/k)\widetilde{\Omega}(N^{1-2/k}) classical queries.

Regarding Conjecture 1.4, Shepherd made the following partial progress in [35 Proposition 3.3.6].

Proposition 1.5. Estimating Trace⁡4\operatorname{Trace}_4 up to a constant additive error requires Ω~(N1/4)\widetilde{\Omega}(N^{1/4}) classical queries.

With the above proposition, we have the following result.

Theorem 1.6 (Classical lower bound on query complexity). *Let ss be an integer. Assume that f(x):[a,b]⊆[−1,1]→[−1,1]f(x) : [a,b] \subseteq[-1,1] \to[-1,1] is a continuous function. Suppose there exists a constant ϵ<1\epsilon< 1

such that d:=deg⁡~ϵ(f)=Ω(poly⁡(n))d := \widetilde{\deg}_{\epsilon}(f) = \Omega(\operatorname{poly}(n)) and Ed/Ed−1<1/2E_d/E_{d-1} < 1/2. Then there is an ss-sparse, log-local Hamiltonian AA for which

Ω~((s/2)(deg⁡~ϵ(f)−4)/16)(5)\widetilde{\Omega}\left((s/2)^{(\widetilde{\deg}_{\epsilon}(f)-4)/16}\right) \tag*{(5)}

classical queries are required to estimate the normalized trace of f(A)f(A) up to a constant accuracy.

As discussed in the abstract, the condition Ed/Ed−1<1/2E_d/E_{d-1} < 1/2 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 f(x)f(x) 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 nn-qubit quantum circuit U=Um⋯U2U1U = U_m \cdots U_2 U_1 such that m=poly⁡(n)m = \operatorname{poly}(n) and each UtU_t acts on O(log⁡n)O(\log n) qubits, we consider the log-local Hamiltonian

A=∑t=1mat∣t−1⟩⟨t−1∣⊗In+∑t=1mbt(∣t⟩⟨t−1∣⊗Ut+∣t−1⟩⟨t∣⊗Ut†),(6)A = \sum_{t=1}^{m} a_t \lvert t-1\rangle\langle t-1\rvert\otimes I_n + \sum_{t=1}^{m} b_t \left(\lvert t\rangle\langle t-1\rvert\otimes U_t + \lvert t-1\rangle\langle t\rvert\otimes U_t^\dagger\right), \tag*{(6)}

where at∈Ra_t \in\mathbb{R}, bt∈R∗b_t \in\mathbb{R}^* are free parameters and ∣m⟩:=∣0⟩\lvert m\rangle:= \lvert0\rangle. This Hamiltonian is log-local and consists of poly⁡(n)\operatorname{poly}(n) terms. The dimension of AA is m2nm2^n.

A key observation is that for any eigenpair (eiθ,∣ϕθ⟩)(e^{i\theta}, \lvert\phi_\theta\rangle) of UU, the restriction of AA to the invariant subspace spanned by

{∣0⟩⊗∣ϕθ⟩, ∣1⟩⊗U1∣ϕθ⟩, ∣2⟩⊗U2U1∣ϕθ⟩, …, ∣m−1⟩⊗Um−1⋯U2U1∣ϕθ⟩}(7)\left\{\lvert0\rangle\otimes\lvert\phi_\theta\rangle,\ \lvert1\rangle\otimes U_1\lvert\phi_\theta\rangle,\ \lvert2\rangle\otimes U_2U_1\lvert\phi_\theta\rangle,\ \ldots,\ \lvert m-1\rangle\otimes U_{m-1}\cdots U_2U_1\lvert\phi_\theta\rangle\right\} \tag*{(7)}

is a periodic Jacobi matrix of the form

Aθ:=(a1b1bmeiθb1a2b2b2⋱⋱⋱⋱bm−1bme−iθbm−1am).(8)A_\theta:= \begin{pmatrix} a_1 & b_1 & & b_m e^{i\theta} \\ b_1 & a_2 & b_2 & \\ & b_2 & \ddots& \ddots\\ & & \ddots& \ddots& b_{m-1} \\ b_m e^{-i\theta} & & b_{m-1} & a_m \end{pmatrix}. \tag*{(8)}

As a consequence, the trace decomposes as

Tr⁡[f(A)]=∑θ:eiθ is an eigenvalue of UTr⁡[f(Aθ)].(9)\operatorname{Tr}[f(A)] = \sum_{\theta:e^{i\theta}\text{ is an eigenvalue of }U} \operatorname{Tr}[f(A_\theta)]. \tag*{(9)}

Since estimating 12nRe⁡(Tr⁡[U])=12n∑θcos⁡θ\frac{1}{2^n}\operatorname{Re}(\operatorname{Tr}[U]) = \frac{1}{2^n}\sum_\theta\cos\theta is DQC1-complete, to establish the DQC1 completeness of estimating the normalized trace Tr⁡[f(A)]\operatorname{Tr}[f(A)], it suffices to relate Tr⁡[f(Aθ)]\operatorname{Tr}[f(A_\theta)] to cos⁡θ\cos\theta for any fixed θ\theta. This connection is established through classical results on periodic Jacobi matrices and the Chebyshev equioscillation theorem.

More precisely, the characteristic polynomial of AθA_\theta admits the representation

det⁡(xI−Aθ)=2b1⋯bm(Δ(x)−cos⁡θ),(10)\det(xI-A_\theta)=2b_1\cdots b_m\left(\Delta(x)-\cos\theta\right), \tag*{(10)}

where Δ(x)\Delta(x), known as the discriminant, is independent of θ\theta. A direct calculation shows that Tr⁡[Δ(Aθ)]=mcos⁡θ\operatorname{Tr}[\Delta(A_\theta)]=m\cos\theta. Moreover, for any θ\theta, the equation Δ(x)−cos⁡θ=0\Delta(x)-\cos\theta=0 has mm real zeros, which are the eigenvalues of AθA_\theta.

A natural intuition is that if Δ(x)\Delta(x) closely approximates f(x)f(x), then Tr⁡[f(Aθ)]\operatorname{Tr}[f(A_\theta)] will correlate with mcos⁡θm\cos\theta. However, this intuition must be refined: Δ(x)\Delta(x) is an oscillatory polynomial that intersects any horizontal line cos⁡θ∈[−1,1]\cos\theta\in[-1,1] at exactly mm real points, a property that a generic function f(x)f(x) 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 g(x)g(x) is the best uniform polynomial approximation of f(x)f(x) of degree dd, then f(x)−g(x)f(x)-g(x) oscillates with d+2d+2 alternating points, see Theorem 2.4 below.

We show that, after appropriate normalization, there is a discriminant Δ(x)\Delta(x) that can be identified with an oscillatory approximation of (f(x)−g(x))/E(f(x)-g(x))/E, where E=∥f−g∥∞E=\lVert f-g\rVert_\infty. Through Δ(x)\Delta(x), we can reconstruct a periodic Jacobi matrix of the form (1.8). Moreover, deg⁡(Δ(x))>deg⁡(g(x))\deg(\Delta(x))>\deg(g(x)), which implies that Tr⁡[g(Aθ)]\operatorname{Tr}[g(A_\theta)] is independent of cos⁡θ\cos\theta and can be computed efficiently in poly⁡(n)\operatorname{poly}(n) time. Together with (1.9), we obtain the desired correspondence between 1m2nTr⁡[f(A)]\frac{1}{m2^n}\operatorname{Tr}[f(A)] and 12nRe⁡(Tr⁡[U])\frac{1}{2^n}\operatorname{Re}(\operatorname{Tr}[U]).

In this process, we can choose the degree of g(x)g(x) as the approximate degree deg⁡~ε(f)\widetilde{\deg}_\varepsilon(f) for a fixed precision ε\varepsilon. In addition, we establish a connection between Chebyshev equioscillation theorem and the approximate degree of f(x)f(x), revealing approximate degree as the fundamental parameter governing DQC1-hardness of normalized trace estimation.

Regarding the query complexity lower bound, we extend the kk-Forrelation problem [1] to the DQC1 model. Specifically, we consider the problem of estimating the normalized trace of U=Ox1H⊗n⋯OxkH⊗nU=O_{x_1}H^{\otimes n}\cdots O_{x_k}H^{\otimes n}, where HH is the 2×22\times2 Hadamard gate and Ox1,…,OxkO_{x_1},\ldots,O_{x_k} are oracle operators. Combining the lower bound for estimating 12nTr⁡[U]\frac{1}{2^n}\operatorname{Tr}[U] with the connection established above between 1m2nTr⁡[f(A)]\frac{1}{m2^n}\operatorname{Tr}[f(A)] and 12nRe⁡(Tr⁡[U])\frac{1}{2^n}\operatorname{Re}(\operatorname{Tr}[U]), we obtain a lower bound for estimating 1m2nTr⁡[f(A)]\frac{1}{m2^n}\operatorname{Tr}[f(A)].

Comparison with previous work [13]

Theorem 4.8 in [13] establishes DQC1-hardness for estimating 12nTr⁡[f(A)]\frac{1}{2^n}\operatorname{Tr}[f(A)] in the block-encoding model. Concretely, it assumes the existence of a unitary UU with O(log⁡n)O(\log n) ancillas such that its top-left corner approximates AA, and that ff and f−1f^{-1} on [−1/2,1/2][-1/2,1/2] admit polynomial approximations of degree O(poly⁡(n/ε))O(\operatorname{poly}(n/\varepsilon)), with ff being Lipschitz continuous with Lipschitz constant poly⁡(n)\operatorname{poly}(n). Under these assumptions, estimating 12nTr⁡[f(A)]\frac{1}{2^n}\operatorname{Tr}[f(A)] is DQC1-hard.

While this result provides a valuable characterization, the block-encoding assumption is somewhat restrictive for natural Hamiltonians. For instance, when A=∑j=1LαjPjA=\sum_{j=1}^{L}\alpha_jP_j is a linear combination of Paulis, the LCU technique gives α=∑j=1L∣αj∣\alpha=\sum_{j=1}^{L}|\alpha_j|, and the block encoding requires O(log⁡L)O(\log L) ancilla qubits. When AA is sparse, α\alpha equals the maximal number of non-zero entries in any row or column, and the block encoding uses O(n)O(n) ancillas. In both cases, achieving α=1\alpha=1 is nontrivial, even if ∥A∥≤1\lVert A\rVert\le1 is known, e.g., see [26], page 23, arXiv version. Moreover, the requirement of f−1f^{-1} appears primarily as a technical condition in the proof, rather than reflecting an intrinsic hardness property of the problem. Finally, in this model, estimating 12nTr⁡[A]\frac{1}{2^n}\operatorname{Tr}[A] 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 Ed/Ed−1<1/2E_d/E_{d-1} < 1/2, our Theorem 1.2 establishes DQC1-hardness for log-local Hamiltonians under a natural and simple condition based solely on the approximate degree of ff, without requiring f−1f^{-1} 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 f(A)f(A) for any ss-sparse matrix AA. Specifically, if f(x)f(x) is a degree-dd polynomial satisfying ∣f(x)∣≤1|f(x)| \le1 for all x∈[−1,1]x \in[-1,1], then there exists a classical algorithm with query complexity O(sd/ε2)O(s^d/\varepsilon^2) that outputs an ε\varepsilon-approximation of the normalized trace of f(A)f(A). This result extends naturally to continuous functions via polynomial approximation. Since the complexity depends on the polynomial degree, one aims to approximate f(x)f(x) 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.

The DQC1 computational model

Figure 1. The DQC1 computational model.

A simple calculation shows that the probability of measuring zero is 12+12Re⁡(Tr⁡[U])2n\frac{1}{2} + \frac{1}{2}\frac{\operatorname{Re}(\operatorname{Tr}[U])}{2^n}. So the real part of the normalized trace can be estimated up to accuracy ε\varepsilon by repeating the procedure O(1/ε2)O(1/\varepsilon^2) 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 LL is in DQC1 if and only if, for any nn-bit string xx, there exists a polynomial-time generated quantum circuit UxU_x acting on q(n)=poly⁡(n)q(n) = \operatorname{poly}(n) qubits such that for some specified polynomial p(n)p(n),

μYES≥12+1p(n),if x∈L,(11)\mu_{\mathrm{YES}} \ge\frac{1}{2} + \frac{1}{p(n)}, \quad\text{if } x \in L, \tag*{(11)}
μYES≤12−1p(n),if x∉L.(12)\mu_{\mathrm{YES}} \le\frac{1}{2} - \frac{1}{p(n)}, \quad\text{if } x \notin L. \tag*{(12)}

where

μYES:=Tr⁡[Ux(∣0⟩⟨0∣⊗Iq(n)−12q(n)−1)Ux†(∣1⟩⟨1∣⊗Iq(n)−1)](13)\mu_{\mathrm{YES}} := \operatorname{Tr}\left[U_x\left(|0\rangle\langle0| \otimes\frac{I_{q(n)-1}}{2^{q(n)-1}}\right)U_x^\dagger\left(|1\rangle\langle1| \otimes I_{q(n)-1}\right)\right] \tag*{(13)}

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 μYES≥2/3\mu_{\mathrm{YES}} \ge2/3 when x∈Lx \in L and μYES≤1/3\mu_{\mathrm{YES}} \le1/3 when x∉Lx \notin L. This is because by repeating the experiment poly⁡(r)\operatorname{poly}(r) times and taking the majority vote, one can achieve high probability of correctness [36].

Proposition 2.2 (Theorem 2 of [22]). Let ε∈(1/poly⁡(n),1)\varepsilon\in(1/\operatorname{poly}(n),1), which can be a constant, and let UU be a unitary acting on nn qubits. Then determining 12nRe⁡(Tr⁡[U])>ε\frac{1}{2^n}\operatorname{Re}(\operatorname{Tr}[U]) > \varepsilon or 12nRe⁡(Tr⁡[U])<−ε\frac{1}{2^n}\operatorname{Re}(\operatorname{Tr}[U]) < -\varepsilon is DQC1-complete. Equivalently, estimating 12nRe⁡(Tr⁡[U])±ε\frac{1}{2^n}\operatorname{Re}(\operatorname{Tr}[U]) \pm\varepsilon is DQC1-complete.

Proposition 2.3 (Corollary 6 of [9]). Assume that AA is a log-local Hamiltonian acting on nn qubits and f(x):[−1,1]→[−1,1]f(x):[-1,1]\to[-1,1] is Lipschitz continuous with Lipschitz constant KK, then there is a DQC1 algorithm to estimate 12nTr⁡[f(A)]±ε(K+1)\frac{1}{2^n}\operatorname{Tr}[f(A)] \pm\varepsilon(K+1), where ε=1/O(poly⁡(n))\varepsilon=1/O(\operatorname{poly}(n)).

The quantum algorithm in the above theorem is mainly based on quantum phase estimation, so the cost is linear in 1/ε1/\varepsilon. When K=O(poly⁡(n))K=O(\operatorname{poly}(n)), we can choose a smaller ε\varepsilon such that εK\varepsilon K is small. The key point here is that 1/ε1/\varepsilon, KK have order O(poly⁡(n))O(\operatorname{poly}(n)). For bounded Lipschitz continuous functions, we have K=O(deg⁡ε(f)2)K=O(\deg_{\varepsilon}(f)^2) via Markov brothers’ inequality [25], where deg⁡ε(f)\deg_{\varepsilon}(f) 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]:

Aθ:=[a1b1bmeiθb1a2b2b2⋱⋱⋱⋱bm−1bme−iθbm−1am],(14)A_\theta:= \begin{bmatrix} a_1 & b_1 & & & b_m e^{i\theta}\\ b_1 & a_2 & b_2 & & \\ & b_2 & \ddots& \ddots& \\ & & \ddots& \ddots& b_{m-1}\\ b_m e^{-i\theta} & & & b_{m-1} & a_m \end{bmatrix}, \tag*{(14)}

where a1,…,am∈Ra_1,\ldots,a_m\in\mathbb{R}, b1,…,bm∈R+b_1,\ldots,b_m\in\mathbb{R}^{+} and θ∈[0,2π)\theta\in[0,2\pi). Obviously, AθA_\theta is Hermitian, and so all the eigenvalues are real.

Let BB be the tridiagonal matrix of dimension mm with subdiagonal entries b1,…,bm−1b_1,\ldots,b_{m-1} (i.e., setting bm=0b_m=0 in AθA_\theta) and let CC be the tridiagonal matrix of dimension m−2m-2 with subdiagonal entries b2,…,bm−2b_2,\ldots,b_{m-2} (i.e., removing the first and last row/column in AθA_\theta), then it is easy to compute that the characteristic polynomial of AθA_\theta is (e.g., see [5])

det⁡(xI−Aθ)=h(x)−ecos⁡θ,(15)\det(xI-A_\theta)=h(x)-e\cos\theta, \tag*{(15)}

where

h(x)=det⁡(xI−B)−bm2det⁡(xI−C),(16)h(x)=\det(xI-B)-b_m^2\det(xI-C), \tag*{(16)}
e=2b1b2⋯bm.(17)e = 2b_1b_2\cdots b_m. \tag*{(17)}

The polynomial Δ(x):=h(x)/e\Delta(x) := h(x)/e is known as the discriminant of AθA_\theta and plays an important role in the study of AθA_\theta. For example, assume ai=0a_i = 0, bi=1/2b_i = 1/2 for all ii, then a simple calculation shows that Δ(x)=Tm(x)\Delta(x) = T_m(x), where Tm(x)T_m(x) is the mm-th Chebyshev polynomial of the first kind. From (15) and the property that AθA_\theta is Hermitian, we know that Δ(x)−cos⁡(θ)=0\Delta(x) - \cos(\theta) = 0 always has mm real zeros for any θ\theta. Based on this, it is not hard to see that Δ(x)\Delta(x) is an oscillating function and it intersects any horizontal line y=cos⁡(θ)y = \cos(\theta) for mm 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 f:[a,b]→Rf : [a, b] \to\mathbb{R} be a continuous function. Among all the polynomials of degree ≤d\le d, the polynomial gg minimizes the uniform norm of the difference E:=∥f−g∥∞:=max⁡a≤x≤b∣f(x)−g(x)∣E := \lVert f - g\rVert_\infty:= \max_{a\le x\le b} \lvert f(x) - g(x)\rvert if and only if there are d+2d + 2 points a≤x1<x2<⋯<xd+2≤ba \le x_1 < x_2 < \cdots< x_{d+2} \le b such that

f(xi)−g(xi)=σ(−1)iE(18)f(x_i) - g(x_i) = \sigma(-1)^i E \tag*{(18)}

where σ\sigma is either −1-1 or +1+1. That is, the polynomial gg oscillates above and below ff 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 gg is unique. The alternation property also determines gg and EE uniquely. But the points x1,x2,…,xd+2x_1, x_2, \ldots, x_{d+2} need not be unique and depend on ff and dd. 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 O(d3)O(d^3)).

Figure 2. Illustration of the Chebyshev Equioscillation Theorem.

Polynomial approximation provides a fundamental approach to representing functions. For a given function f:[−1,1]→Rf : [-1, 1] \to\mathbb{R}, one may study the best degree-dd 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 ff within error ε\varepsilon in the uniform norm (see the definition below). This quantity captures the intrinsic complexity of approximating ff 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 [−1,1][-1,1], we restrict our attention to functions defined on subintervals of [−1,1][-1,1].

Definition 2.6 (Approximate degree). Let f(x):[a,b]⊆[−1,1]→[−1,1]f(x):[a,b]\subseteq[-1,1]\to[-1,1] be a function and let ε∈(0,1]\varepsilon\in(0,1]. We define the approximate degree of ff as

deg⁡~ε(f)=min⁡{d∈N:∣f(x)−g(x)∣≤ε for all x∈[a,b], deg⁡(g)=d}.(19)\widetilde{\deg}_{\varepsilon}(f)=\min\{d\in\mathbb{N}:|f(x)-g(x)|\leq\varepsilon\text{ for all }x\in[a,b],\ \deg(g)=d\}. \tag*{(19)}

We establish below a connection between the dual polynomial method and the Chebyshev Equioscillation Theorem, which might be of independent interest. For any fixed dd, the dual polynomial method considers the following linear semi-infinite program (LSIP):

min⁡g,δδ(20)\begin{aligned} \min_{g,\delta}\quad&\delta \tag*{(20)} \end{aligned}
s.t.∣f(x)−g(x)∣≤δ,∀x∈[a,b],(21)\begin{aligned} \text{s.t.}\quad&|f(x)-g(x)|\leq\delta,\quad\forall x\in[a,b], \tag*{(21)} \end{aligned}
deg⁡(g)≤d.(22)\deg(g)\leq d. \tag*{(22)}

By known results from LSIP [23, 33], there exist {x1,…,xd+2}\{x_1,\ldots,x_{d+2}\} such that (20) is equivalent to the following linear program (here d+2d+2 refers to the number of free parameters in the LSIP (20)):

min⁡g,δδ(23)\begin{aligned} \min_{g,\delta}\quad&\delta \tag*{(23)} \end{aligned}
s.t.∣f(xi)−g(xi)∣≤δ,∀i=1,…,d+2,(24)\begin{aligned} \text{s.t.}\quad&|f(x_i)-g(x_i)|\leq\delta,\quad\forall i=1,\ldots,d+2, \tag*{(24)} \end{aligned}
deg⁡(g)≤d.(25)\deg(g)\leq d. \tag*{(25)}

Proposition 2.7. The points {x1,…,xd+2}\{x_1,\ldots,x_{d+2}\} 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 d=deg⁡~ε(f)d=\widetilde{\deg}_{\varepsilon}(f) for any desired accuracy ε\varepsilon, e.g., ε=1/3\varepsilon=1/3, we then will obtain a min-max polynomial approximation of f(x)f(x) with error ε\varepsilon.

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 Δ(x)\Delta(x) be a polynomial of degree mm. Then there is a periodic Jacobi matrix A0A_0 such that its discriminant is Δ(x)\Delta(x) if and only if

  • the coefficient of xmx^m in Δ(x)\Delta(x) is positive, and

  • Δ(x)\Delta(x) has m−1m-1 distinct local extrema ν1>⋯>νm−1\nu_1 > \cdots> \nu_{m-1} with (−1)jΔ(νj)≥1(-1)^j\Delta(\nu_j) \ge1 for all jj.

Moreover, there is also an efficient algorithm to construct A0A_0 when given Δ(x)\Delta(x).

From (15), suppose Δ(x)\Delta(x) is the discriminant of A0A_0, then it is also the discriminant of AθA_\theta for all θ\theta. Moreover, 1/e1/e is the leading coefficient of Δ(x)\Delta(x). It is easy to check that the second property in Proposition 2.8 is easily satisfied once Δ(x)\Delta(x) has the oscillating property similar to the Chebyshev Equioscillation Theorem. This means that if Δ(x)≈(f(x)−g(x))/E\Delta(x) \approx(f(x)-g(x))/E where f(x)f(x), g(x)g(x), EE are the same as those in the Chebyshev Equioscillation Theorem, then Δ(x)\Delta(x) will be a discriminant of some periodic Jacobi matrix. In the Chebyshev Equioscillation Theorem, g(x)g(x) is the polynomial with minimal degree dd that approximates f(x)f(x) up to error EE, so to ensure a nontrivial approximation, we have to choose Δ(x)\Delta(x) such that m=deg⁡(Δ(x))>deg⁡(g)m = \deg(\Delta(x)) > \deg(g).

To continue, we recall the following concept from polynomial approximation theory.

Definition 2.9. Let f(x):[a,b]⊆[−1,1]→Rf(x) : [a,b] \subseteq[-1,1] \to\mathbb{R} be a continuous function. For any integer mm, define

Em(f;[a,b]):=min⁡deg⁡(P)≤mmax⁡x∈[a,b]∣f(x)−P(x)∣(26)E_m(f;[a,b]) := \min_{\deg(P)\le m}\max_{x\in[a,b]} |f(x)-P(x)| \tag*{(26)}

to be the best uniform (minimax) polynomial approximation error of degree at most mm over [a,b][a,b]. When there is no risk of confusion, we sometimes simply write it as EmE_m. The polynomial of degree at most mm that attains this minimum is denoted as Pm∗(x)P_m^*(x).

In practice, we start from ε\varepsilon, then compute the approximate degree d=deg⁡~ε(f)d = \widetilde{\deg}_{\varepsilon}(f), finally we have Ed−1>ε≥EdE_{d-1} > \varepsilon\ge E_d and d≤deg⁡~Ed(f)d \le\widetilde{\deg}_{E_d}(f). Equality holds when ε=Ed\varepsilon= E_d. We indeed have deg⁡~ε(f)=min⁡{d:Ed≤ε}\widetilde{\deg}_{\varepsilon}(f) = \min\{d : E_d \le\varepsilon\}. Moreover, for any η∈[Ed,Ed−1)\eta\in[E_d,E_{d-1}), we always have d=deg⁡~η(f)d = \widetilde{\deg}_{\eta}(f).

Theorem 2.10. Let f(x):[a,b]⊆[−1,1]→Rf(x) : [a,b] \subseteq[-1,1] \to\mathbb{R} be a continuous function and ε∈(0,1)\varepsilon\in(0,1) with d=deg⁡~ε(f)d = \widetilde{\deg}_{\varepsilon}(f). For any η∈[Ed,Ed−1)\eta\in[E_d,E_{d-1}), there is a periodic Jacobi matrix AθA_\theta of the form (14) with ∥Aθ∥≤1\lVert A_\theta\rVert\le1, dimension dd and discriminant Δ(x)\Delta(x), such that

∣Δ(x)−f(x)−Pd−1∗(x)Ed−1−η∣≤ηEd−1−η.(27)\left|\Delta(x)-\frac{f(x)-P_{d-1}^*(x)}{E_{d-1}-\eta}\right| \le\frac{\eta}{E_{d-1}-\eta}. \tag*{(27)}

Proof. Let g(x)g(x) denote the degree dd polynomial in computing d=deg⁡~η(f)d = \widetilde{\deg}_{\eta}(f). Without loss of generality, we assume that the leading coefficient of g(x)g(x) is positive; otherwise, Δ(x)\Delta(x) below should be multiplied by the sign of this leading coefficient. Denote

Δ(x)=g(x)−Pd−1∗(x)Ed−1−η,(28)\Delta(x) = \frac{g(x)-P_{d-1}^*(x)}{E_{d-1}-\eta}, \tag*{(28)}

then it satisfies

f(x)=(Ed−1−η)Δ(x)+Pd−1∗(x)+(f(x)−g(x)).(29)f(x) = (E_{d-1}-\eta)\Delta(x) + P_{d-1}^*(x) + (f(x)-g(x)). \tag*{(29)}

By Theorem 2.4, there exist d+1d+1 points a≤x1<⋯<xd+1≤ba \le x_1 < \cdots< x_{d+1} \le b and σ∈{−1,1}\sigma\in\{-1,1\} such that f(xi)−Pd−1∗(xi)=σ(−1)iEd−1f(x_i)-P_{d-1}^*(x_i) = \sigma(-1)^i E_{d-1}. Without loss of generality, we also set σ=1\sigma= 1. Since ∣g(xi)−f(xi)∣≤η<Ed−1|g(x_i)-f(x_i)| \le\eta< E_{d-1}, by (29) the sign of Δ(xi)\Delta(x_i) satisfies

sgn⁡(Δ(xi))=sgn⁡((−1)iEd−1+g(xi)−f(xi))=(−1)i,(30)\operatorname{sgn}(\Delta(x_i)) = \operatorname{sgn}\left((-1)^i E_{d-1}+g(x_i)-f(x_i)\right) = (-1)^i, \tag*{(30)}

and hence oscillates between −1-1 and 11. By the Intermediate Value Theorem, there exist dd points {ξi}i=1d\{\xi_i\}_{i=1}^d satisfying Δ(ξi)=0\Delta(\xi_i)=0 and x1<ξ1<x2<ξ2<⋯<ξd<xd+1x_1 < \xi_1 < x_2 < \xi_2 < \cdots< \xi_d < x_{d+1}. By Rolle’s theorem,

there exist d−1d-1 points {yi}i=1d−1\{y_i\}_{i=1}^{d-1} satisfying Δ′(yi)=0\Delta'(y_i)=0 and ξ1<y1<ξ2<y2<⋯<yd−1<ξd\xi_1<y_1<\xi_2<y_2<\cdots<y_{d-1}<\xi_d. Since Δ′(x)\Delta'(x) is a polynomial with degree d−1d-1 and has at most d−1d-1 zeros, there are no other zeros other than {yi}i=1d−1\{y_i\}_{i=1}^{d-1}. Therefore, Δ(x)\Delta(x) has oscillating signs on a sequence of intervals (−∞,ξ1),(ξ1,ξ2),…,(ξd,∞)(-\infty,\xi_1),(\xi_1,\xi_2),\ldots,(\xi_d,\infty). On each interval (ξi,ξi+1)(\xi_i,\xi_{i+1}), Δ(x)\Delta(x) attains the maximal/minimal value at yiy_i, so we have

∣Δ(yi)∣≥∣Δ(xi+1)∣≥Ed−1−∣g(xi)−f(xi)∣Ed−1−η≥Ed−1−ηEd−1−η=1(31)|\Delta(y_i)|\geq|\Delta(x_{i+1})|\geq\frac{E_{d-1}-|g(x_i)-f(x_i)|}{E_{d-1}-\eta}\geq\frac{E_{d-1}-\eta}{E_{d-1}-\eta}=1 \tag*{(31)}

as xi+1∈(ξi,ξi+1)x_{i+1}\in(\xi_i,\xi_{i+1}). In conclusion, Δ(x)\Delta(x) has d−1d-1 extrema points {yi}i=1d−1\{y_i\}_{i=1}^{d-1} with oscillating signs and ∣Δ(yi)∣≥1|\Delta(y_i)|\geq1. Now order the critical points from right to left by setting νj=yd−j\nu_j=y_{d-j} for j=1,2,…,d−1j=1,2,\ldots,d-1. Then ν1>⋯>νd−1\nu_1>\cdots>\nu_{d-1}. Since the leading coefficient of Δ(x)\Delta(x) is positive, Δ(x)>0\Delta(x)>0 for all x∈(ξd,∞)x\in(\xi_d,\infty). So (−1)jΔ(νj)≥1(-1)^j\Delta(\nu_j)\geq1 for all jj. By Proposition 2.8, there exists a periodic Jacobi matrix A0A_0 with discriminant Δ(x)\Delta(x). The claim (27) follows directly from (2.19}.

Finally, it remains to show ∥Aθ∥≤1\|A_\theta\|\leq1. For any c∈[−1,1]c\in[-1,1], since the values Δ(xi)\Delta(x_i) alternate in sign and satisfy ∣Δ(xi)∣≥1|\Delta(x_i)|\geq1, we have (Δ(xi)−c)(Δ(xi+1)−c)≤0(\Delta(x_i)-c)(\Delta(x_{i+1})-c)\leq0 for all ii. Hence, each closed interval [xi,xi+1][x_i,x_{i+1}] contains a root of Δ(x)−c\Delta(x)-c. Because Δ(x)−c\Delta(x)-c has degree dd, these are all its roots, and all of them lie in [x1,xd+1]⊆[a,b]⊆[−1,1][x_1,x_{d+1}]\subseteq[a,b]\subseteq[-1,1]. Taking c=cos⁡θc=\cos\theta, we conclude that every eigenvalue of AθA_\theta lies in [−1,1][-1,1].

Remark 2.11. The above result is a key ingredient in the proofs of our main theorems. We need to choose ε\varepsilon and η\eta as small constants, so that Ed−1E_{d-1} is also a constant. However, the bound for EdE_d is not clear. The ideal situation for us is Ed≪Ed−1E_d\ll E_{d-1}. In this case, we can always find a constant η\eta such that η/(Ed−1−η)\eta/(E_{d-1}-\eta) is a small constant. Even in the worst case, EdE_d is still a small constant, then as long as Ed/Ed−1<1/2E_d/E_{d-1}<1/2, we then have Ed/(Ed−1−Ed)<1E_d/(E_{d-1}-E_d)<1, which is a small constant.

Many functions in practice satisfy the condition Ed/Ed−1<1/2E_d/E_{d-1}<1/2 when dd is reasonably large. Asymptotically, when f(x)f(x) is analytic and can be analytically continued to the open Bernstein ellipse Eρ:={z=12(w+w−1):∣w∣<ρ}E_\rho:=\{z=\frac{1}{2}(w+w^{-1}):|w|<\rho\}, then Ed≈ρ−dE_d\approx\rho^{-d}; see [37 Theorem 8.2]. Hence, heuristically, Ed/Ed−1≈1/ρE_d/E_{d-1}\approx1/\rho. So the condition Ed/Ed−1<1/2E_d/E_{d-1}<1/2 is expected to hold when ρ>2\rho>2.

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,

Ed≤∥f(x)−fd(x)∥∞≤cdEd,cd=4+4π2log⁡(d+1),(32)E_d\leq\|f(x)-f_d(x)\|_\infty\leq c_dE_d,\qquad c_d=4+\frac{4}{\pi^2}\log(d+1), \tag*{(32)}

where fd(x)f_d(x) is the degree-dd truncated Chebyshev expansion. Below, we use this to calculate Ed/Ed−1E_d/E_{d-1}. We denote E~d:=∥f(x)−fd(x)∥∞\widetilde E_d:=\|f(x)-f_d(x)\|_\infty, and so Ed/Ed−1≤cd−1E~d/E~d−1E_d/E_{d-1}\leq c_{d-1}\widetilde E_d/\widetilde E_{d-1}.

  • Exponential function: The function f(x)=e−βxf(x)=e^{-\beta x} for β>0\beta>0 appears in partition function computations [7]. For this function, from the Chebyshev expansion, we have E~d=Θ(Id+1(β))\widetilde E_d=\Theta(I_{d+1}(\beta)), where Id+1(β)I_{d+1}(\beta) is the modified Bessel function of the first kind. Using the standard asymptotic behavior of Bessel functions, asymptotically, when d≫βd\gg\beta we have Ed/Ed−1≤cd−1E~d/E~d−1=Θ(β(log⁡d)/d)E_d/E_{d-1}\leq c_{d-1}\widetilde E_d/\widetilde E_{d-1}=\Theta(\beta(\log d)/d), which is smaller than 1/21/2 when d>Ω~(β)d>\widetilde\Omega(\beta).

  • Trigonometric function: The function f(x)=sin⁡(tx)f(x)=\sin(tx) appears as the imaginary part of eitxe^{itx} in Hamiltonian simulation [16], where t>0t>0 and x∈[−1,1]x\in[-1,1]. It is an entire function with Chebyshev expansion sin⁡(tx)=2∑k=0∞(−1)kJ2k+1(t)T2k+1(x)\sin(tx)=2\sum_{k=0}^{\infty}(-1)^kJ_{2k+1}(t)T_{2k+1}(x), where J2k+1(t)J_{2k+1}(t) are Bessel functions of the first kind. So E~d≈∑odd k>d∣Jk(t)∣≈∣Jd(t)∣\widetilde E_d\approx\sum_{\text{odd }k>d}|J_k(t)|\approx|J_d(t)| if dd is odd. So when d≫td\gg t, we asymptotically have Ed/Ed−1≤Θ(t(log⁡d)/d)E_d/E_{d-1}\leq\Theta(t(\log d)/d), which is smaller than 1/21/2 when d>Ω~(t)d>\widetilde\Omega(t). A similar result holds for cos⁡(tx)\cos(tx).

  • Logarithmic function: The function f(x)=log⁡(1+βx)f(x)=\log(1+\beta x) with 0<β<10<\beta<1 in the interval [−1,1][-1,1], is commonly used in the calculation of log-determinant [20]. For this function, we have E~d=Θ(ρ−d/d)\widetilde{E}_d=\Theta(\rho^{-d}/d), where ρ=1+1−β2β\rho=\frac{1+\sqrt{1-\beta^2}}{\beta}. Thus Ed/Ed−1≤Θ((log⁡d)/ρ)<1/2E_d/E_{d-1}\leq\Theta((\log d)/\rho)<1/2 when β<O(1/log⁡(d))\beta<O(1/\log(d)).

  • Inverse-type function: The function f(x)=1/κxf(x)=1/\kappa x over the interval [−1,−1/κ]∪[1/κ,1][-1,-1/\kappa]\cup[1/\kappa,1] is used in solving linear systems [16], where κ>1\kappa>1. Now ρ=κ+κ2−1≈2κ\rho=\kappa+\sqrt{\kappa^2-1}\approx2\kappa. In this case, we have Ed=Θ(1/(2κ)d)E_d=\Theta(1/(2\kappa)^d), and so Ed/Ed−1≤Θ(log⁡(d)/κ)<1/2E_d/E_{d-1}\leq\Theta(\log(d)/\kappa)<1/2 when κ>Ω(log⁡d)\kappa>\Omega(\log d).

Proof of Theorem 1.2

Theorem 3.1 (Restatement of Theorem 1.2). Let ϵ<1\epsilon<1 be a small constant. Assume that f(x):[a,b]⊆[−1,1]→[−1,1]f(x):[a,b]\subseteq[-1,1]\to[-1,1] is a continuous function with d:=deg⁡ϵ(f)=Ω(poly⁡(n))d:=\deg_\epsilon(f)=\Omega(\operatorname{poly}(n)) and Ed/Ed−1<1/2E_d/E_{d-1}<1/2. 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 U=Um⋯U2U1U=U_m\cdots U_2U_1 be a unitary acting on nn qubits such that each UiU_i acts on at most O(log⁡(n))O(\log(n)) qubits, with m=O(poly⁡(n))m=O(\operatorname{poly}(n)). In the proof below, we first assume m=dm=d exactly, and will discuss how to remove this assumption at the end of the proof.

Consider

A=∑t=1mat∣t−1⟩⟨t−1∣⊗I+∑t=1mbt(∣t⟩⟨t−1∣⊗Ut+∣t−1⟩⟨t∣⊗Ut†),(33)A=\sum_{t=1}^{m}a_t|t-1\rangle\langle t-1|\otimes I+\sum_{t=1}^{m}b_t\left(|t\rangle\langle t-1|\otimes U_t+|t-1\rangle\langle t|\otimes U_t^\dagger\right), \tag*{(33)}

where we set ∣m⟩=∣0⟩|m\rangle=|0\rangle. Let ∣ϕθ⟩|\phi_\theta\rangle be an eigenstate of UU, i.e., U∣ϕθ⟩=eiθ∣ϕθ⟩U|\phi_\theta\rangle=e^{i\theta}|\phi_\theta\rangle, and let

∣ψ0(θ)⟩=∣0⟩⊗∣ϕθ⟩,(34)|\psi_0(\theta)\rangle=|0\rangle\otimes|\phi_\theta\rangle, \tag*{(34)}
∣ψt(θ)⟩=∣t⟩⊗Ut⋯U1∣ϕθ⟩,t=1,…,m−1.(35)|\psi_t(\theta)\rangle=|t\rangle\otimes U_t\cdots U_1|\phi_\theta\rangle,\qquad t=1,\ldots,m-1. \tag*{(35)}

Then it is easy to check that

A∣ψ0(θ)⟩=a1∣ψ0(θ)⟩+b1∣ψ1(θ)⟩+bm∣m−1⟩⊗Um†∣ϕθ⟩(36)A|\psi_0(\theta)\rangle=a_1|\psi_0(\theta)\rangle+b_1|\psi_1(\theta)\rangle+b_m|m-1\rangle\otimes U_m^\dagger|\phi_\theta\rangle \tag*{(36)}
=a1∣ψ0(θ)⟩+b1∣ψ1(θ)⟩+bme−iθ∣ψm−1(θ)⟩,(37)=a_1|\psi_0(\theta)\rangle+b_1|\psi_1(\theta)\rangle+b_me^{-i\theta}|\psi_{m-1}(\theta)\rangle, \tag*{(37)}
A∣ψt(θ)⟩=at∣ψt(θ)⟩+bt+1∣ψt+1(θ)⟩+bt−1∣ψt−1(θ)⟩,t=1,2,…,m−2,(38)A|\psi_t(\theta)\rangle=a_t|\psi_t(\theta)\rangle+b_{t+1}|\psi_{t+1}(\theta)\rangle+b_{t-1}|\psi_{t-1}(\theta)\rangle,\qquad t=1,2,\ldots,m-2, \tag*{(38)}
A∣ψm−1(θ)⟩=am∣ψm−1(θ)⟩+bm−1∣ψm−2(θ)⟩+bm∣m⟩⊗Um⋯U1∣ϕθ⟩(39)A|\psi_{m-1}(\theta)\rangle=a_m|\psi_{m-1}(\theta)\rangle+b_{m-1}|\psi_{m-2}(\theta)\rangle+b_m|m\rangle\otimes U_m\cdots U_1|\phi_\theta\rangle \tag*{(39)}
=am∣ψm−1(θ)⟩+bm−1∣ψm−2(θ)⟩+bmeiθ∣ψ0(θ)⟩.(40)=a_m|\psi_{m-1}(\theta)\rangle+b_{m-1}|\psi_{m-2}(\theta)\rangle+b_me^{i\theta}|\psi_0(\theta)\rangle. \tag*{(40)}

Thus in the basis {∣ψt(θ)⟩:t=0,…,m−1}\{|\psi_t(\theta)\rangle:t=0,\ldots,m-1\}, the operator AA is a periodic Jacobi operator of the following form

Aθ:=(a1b1bmeiθb1a2b2b2⋱⋱⋱⋱bm−1bme−iθbm−1am).(41)A_\theta:= \begin{pmatrix} a_1 & b_1 & & b_me^{i\theta}\\ b_1 & a_2 & b_2 & \\ & b_2 & \ddots& \ddots\\ & & \ddots& \ddots& b_{m-1}\\ b_me^{-i\theta} & & & b_{m-1} & a_m \end{pmatrix}. \tag*{(41)}

Due to the orthogonality of {∣ψt(θ)⟩}t,θ\{|\psi_t(\theta)\rangle\}_{t,\theta}, we have that

Tr⁡[f(A)]=∑θ:eiθ is an eigenvalue of UTr⁡[f(Aθ)].(42)\operatorname{Tr}[f(A)]=\sum_{\theta:e^{i\theta}\text{ is an eigenvalue of }U}\operatorname{Tr}[f(A_\theta)]. \tag*{(42)}

By Theorem 2.10, we can construct a periodic Jacobi matrix AθA_\theta such that the dimension is m=dm=d and discriminant Δ(x)\Delta(x). So the characteristic polynomial is det⁡(xIm−Aθ)=e(Δ(x)−cos⁡(θ))\det(xI_m-A_\theta)=e(\Delta(x)-\cos(\theta)), where e=2∏jbje=2\prod_j b_j. By (27), we choose η∈[Ed,Ed−1)\eta\in[E_d,E_{d-1}) such that Ed−1−ηE_{d-1}-\eta is a constant and

∣Δ(x)−f(x)−Pd−1∗(x)Ed−1−η∣≤ηEd−1−η=:η′.(43)\left|\Delta(x)-\frac{f(x)-P^*_{d-1}(x)}{E_{d-1}-\eta}\right|\le\frac{\eta}{E_{d-1}-\eta}=:\eta'. \tag*{(43)}

By Remark 2.11, without loss of generality, we assume that η′\eta' is a small constant when Ed/Ed−1<1/2E_d/E_{d-1}<1/2. The above implies that

∣Tr⁡[f(Aθ)]−Tr⁡[Pd−1∗(Aθ)]−(Ed−1−η)Tr⁡[Δ(Aθ)]∣≤(Ed−1−η)η′m.(44)\left|\operatorname{Tr}[f(A_\theta)]-\operatorname{Tr}[P^*_{d-1}(A_\theta)]-(E_{d-1}-\eta)\operatorname{Tr}[\Delta(A_\theta)]\right|\le(E_{d-1}-\eta)\eta'm. \tag*{(44)}

As a discriminant polynomial, we have that Δ(Aθ)=cos⁡(θ)Im\Delta(A_\theta)=\cos(\theta)I_m, i.e., Tr⁡[Δ(Aθ)]=mcos⁡θ\operatorname{Tr}[\Delta(A_\theta)]=m\cos\theta. So we have

∣Tr⁡[f(Aθ)]−Tr⁡[Pd−1∗(Aθ)]−(Ed−1−η)mcos⁡θ∣≤(Ed−1−η)η′m.(45)\left|\operatorname{Tr}[f(A_\theta)]-\operatorname{Tr}[P^*_{d-1}(A_\theta)]-(E_{d-1}-\eta)m\cos\theta\right|\le(E_{d-1}-\eta)\eta'm. \tag*{(45)}

Since Pd−1∗(x)P^*_{d-1}(x) has degree d−1d-1, which is smaller than the size m=dm=d of AθA_\theta, we have that Tr⁡[Pd−1∗(Aθ)]\operatorname{Tr}[P^*_{d-1}(A_\theta)] is independent of θ\theta and can be computed efficiently and exactly. Thus, we can simply denote it as Tr⁡[Pd−1∗(A0)]\operatorname{Tr}[P^*_{d-1}(A_0)] by setting θ=0\theta=0. One simple way to see this is using random walks. Indeed, AθA_\theta can be viewed as the adjacency matrix of a circle of mm nodes. So, when doing random walks of length less than mm, summing all the weights to compute the trace, the overall weight for vertex ii is the sum of weights of all walks that pass through the edge between vertex 1 and vertex mm for even times, back and forth.

As a result of (42) and (45), we have

Tr⁡[f(A)]=∑θ:eiθ is an eigenvalue of U(m(Ed−1−η)(cos⁡θ±η′)+Tr⁡[Pd−1∗(A0)])(46)\operatorname{Tr}[f(A)]=\sum_{\theta:e^{i\theta}\text{ is an eigenvalue of }U}\left(m(E_{d-1}-\eta)(\cos\theta\pm\eta')+\operatorname{Tr}[P^*_{d-1}(A_0)]\right) \tag*{(46)}
=m(Ed−1−η)(Re⁡Tr⁡U±2nη′)+2nTr⁡[Pd−1∗(A0)].(47)=m(E_{d-1}-\eta)(\operatorname{Re}\operatorname{Tr}U\pm2^n\eta')+2^n\operatorname{Tr}[P^*_{d-1}(A_0)]. \tag*{(47)}

Notice that the dimension of AA is m2nm2^n, it follows that

Tr⁡[f(A)]m2n=(Ed−1−η)(Re⁡Tr⁡(U)2n±η′)+Tr⁡[Pd−1∗(A0)]m.(48)\frac{\operatorname{Tr}[f(A)]}{m2^n}=(E_{d-1}-\eta)\left(\frac{\operatorname{Re}\operatorname{Tr}(U)}{2^n}\pm\eta'\right)+\frac{\operatorname{Tr}[P^*_{d-1}(A_0)]}{m}. \tag*{(48)}

Thus, if we can estimate Tr⁡[f(A)]m2n±ξ\frac{\operatorname{Tr}[f(A)]}{m2^n}\pm\xi for some small constant ξ\xi, we then can estimate Re⁡Tr⁡(U)2n±η′′\frac{\operatorname{Re}\operatorname{Tr}(U)}{2^n}\pm\eta'' with η′′:=η′+ξEd−1−η\eta'':=\eta'+\frac{\xi}{E_{d-1}-\eta}. Since η′\eta', Ed−1−ηE_{d-1}-\eta are constants smaller than 1, we can choose ξ\xi small enough to ensure that η′′\eta'' is also a constant smaller than 1. By Proposition 2.2, estimating Re⁡Tr⁡(U)2n±η′′\frac{\operatorname{Re}\operatorname{Tr}(U)}{2^n}\pm\eta'' is DQC1-hard, so estimating Tr⁡[f(A)]m2n±ξ\frac{\operatorname{Tr}[f(A)]}{m2^n}\pm\xi is also DQC1-hard.

In the above proof, we used the property that m=dm=d. But mm is only determined by UU, this condition can be easily satisfied if we have deg⁡ε(f)>m=poly⁡(n)\deg_\varepsilon(f)>m=\operatorname{poly}(n) because we can add identities into UU. This is why we assumed that deg⁡ε(f)=Ω(poly⁡(n))\deg_\varepsilon(f)=\Omega(\operatorname{poly}(n)) 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 f(A)f(A). This establishes an exponential quantum–classical separation.

Recall that in [13 Theorem 1.1], given sparse access to an ss-sparse Hermitian matrix AA with ∥A∥≤1\lVert A\rVert\le1, and a degree-dd polynomial f(x)f(x) satisfying ∣f(x)∣≤1\lvert f(x)\rvert\le1 for all x∈[−1,1]x \in[-1,1], there exists a classical algorithm with query complexity O(sd/ε2)O(s^d/\varepsilon^2) that outputs an ε\varepsilon-approximation of the normalized trace of f(A)f(A). The oracles are standard: one oracle returns the nonzero entries of AA, while the other returns the positions of the nonzero entries in each row. Basically, their algorithm works as follows: for each matrix monomial AkA^k, sparsity allows us to estimate one diagonal entry efficiently (for example, using the definition, which costs O(sk)O(s^k)). Since the normalized trace is the expectation value of the diagonal entries, O(1/ε2)O(1/\varepsilon^2) samples are enough to approximate it up to an additive error ε\varepsilon.

The result of [13] also holds when f(x)f(x) is continuous on [−1,1][-1,1]. In this case, one may first approximate f(x)f(x) by a degree-dd 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 deg⁡~(f)\widetilde{\deg}(f), 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 kk-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 OxO_x be an oracle defined by an input x=(x1,…,xN)∈{±1}Nx=(x_1,\ldots,x_N)\in\{\pm1\}^N via

Figure 3. A kk-query DQC1 algorithm.

Ox∣i⟩=xi∣i⟩,(49)O_x\lvert i\rangle=x_i\lvert i\rangle, \tag*{(49)}

where N=2nN=2^n. The goal is to compute a function of xx using as few oracle queries as possible. In a kk-query DQC1 algorithm, we apply a unitary

U=OxUk⋯OxU2OxU1,(50)U=O_xU_k\cdots O_xU_2O_xU_1, \tag*{(50)}

where U1,…,UkU_1,\ldots,U_k are independent of OxO_x. A natural quantity that can be computed in this model is the normalized trace 1NTr⁡[U]\frac{1}{N}\operatorname{Tr}[U]. We can also consider a more general setting in which different oracles Ox1,Ox2,…,OxkO_{x_1},O_{x_2},\ldots,O_{x_k} are used, with inputs x1,…,xk∈{±1}Nx_1,\ldots,x_k\in\{\pm1\}^N.

We now consider an extension of the kk-Forrelation problem in the DQC1 query model. Define the normalized trace function

Trace⁡k(x):=1NTr⁡[Ox1H⊗nOx2H⊗n⋯H⊗nOxkH⊗n],(51)\operatorname{Trace}_k(x):=\frac{1}{N}\operatorname{Tr}\left[O_{x_1}H^{\otimes n}O_{x_2}H^{\otimes n}\cdots H^{\otimes n}O_{x_k}H^{\otimes n}\right], \tag*{(51)}

where HH is the 2×22\times2 Hadamard gate. Recall that the function studied in the kk-Forrelation problem corresponds to a single entry of the unitary H⊗nOx1H⊗n⋯H⊗nOxkH⊗nH^{\otimes n}O_{x_1}H^{\otimes n}\cdots H^{\otimes n}O_{x_k}H^{\otimes n}. Thus, the above function can be viewed as a natural generalization of the kk-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 ss be an integer, and ε<1\varepsilon< 1 be a small constant. Assume that f(x):[a,b]⊆[−1,1]→[−1,1]f(x):[a,b] \subseteq[-1,1] \to[-1,1] is a continuous function with d:=deg⁡ε(f)=Ω(poly⁡(n))d := \deg_{\varepsilon}(f) = \Omega(\operatorname{poly}(n)) and Ed/Ed−1<1/2E_d/E_{d-1} < 1/2. Then there is an ss-sparse, log⁡\log-local Hamiltonian AA such that

O~((s/2)(deg⁡ε(f)−4)/16)(52)\widetilde{O}\left((s/2)^{(\deg_{\varepsilon}(f)-4)/16}\right) \tag*{(52)}

classical queries are required to estimate the normalized trace of f(A)f(A) up to a constant accuracy.

Proof. We consider k=4k=4 in Trace⁡k\operatorname{Trace}_k. Now we have

U=Ox1H⊗nOx2H⊗nOx3H⊗nOx4H⊗n.(53)U=O_{x_1}H^{\otimes n}O_{x_2}H^{\otimes n}O_{x_3}H^{\otimes n}O_{x_4}H^{\otimes n}. \tag*{(53)}

For convenience, we assume the sparsity s=2r+1s=2^{r+1} and n=rℓn=r\ell. The analysis below does not change too much if rr is not a factor of nn.

We decompose H⊗nH^{\otimes n} as (this is the only place we used the result n=rℓn=r\ell)

H⊗n=(H⊗r⊗I⊗⋯⊗I)(I⊗H⊗r⊗⋯⊗I)⋯(I⊗I⊗⋯⊗H⊗r).(54)H^{\otimes n}=(H^{\otimes r}\otimes I\otimes\cdots\otimes I)(I\otimes H^{\otimes r}\otimes\cdots\otimes I)\cdots(I\otimes I\otimes\cdots\otimes H^{\otimes r}). \tag*{(54)}

There are ℓ\ell factors in the above decomposition. Each factor is 2r2^r-sparse. As a result, UU can be rewritten as a product of 4ℓ4\ell 2r2^r-sparse unitaries and 44 11-sparse unitaries. Namely, there are m=4ℓ+4m=4\ell+4 unitaries in the decomposition of UU.

Following the proof of Theorem 3.1, we can construct a Hamiltonian AA, which is 2r+12^{r+1}-sparse and O(r+log⁡n)O(r+\log n)-local, such that (see (48))

Tr⁡[f(A)]m2n=(Ed−1−ε)(Re⁡Tr⁡(U)2n±η)+Tr⁡[Pd−1∗(A0)]m.(55)\frac{\operatorname{Tr}[f(A)]}{m2^n}=(E_{d-1}-\varepsilon)\left(\frac{\operatorname{Re}\operatorname{Tr}(U)}{2^n}\pm\eta\right)+\frac{\operatorname{Tr}[P^*_{d-1}(A_0)]}{m}. \tag*{(55)}

Thus, if we can estimate Tr⁡[f(A)]m2n±ξ\frac{\operatorname{Tr}[f(A)]}{m2^n}\pm\xi for some small constant ξ\xi, we then can estimate Re⁡Tr⁡(U)2n±η′\frac{\operatorname{Re}\operatorname{Tr}(U)}{2^n}\pm\eta' with η′:=η+ξEd−1−ε\eta':=\eta+\frac{\xi}{E_{d-1}-\varepsilon} a constant. Moreover, m=deg⁡ε(f)m=\deg_{\varepsilon}(f), i.e., ℓ=(deg⁡ε(f)−4)/4\ell=(\deg_{\varepsilon}(f)-4)/4 and n=rℓ=(log⁡(s/2))(deg⁡ε(f)−4)/4n=r\ell=(\log(s/2))(\deg_{\varepsilon}(f)-4)/4. By Proposition 1.5, we obtain a lower bound of estimating 1m2nTr⁡[f(A)]\frac{1}{m2^n}\operatorname{Tr}[f(A)], which is

Ω~(2n/4)=Ω~(2(log⁡(s/2))(deg⁡ε(f)−4)/16)=Ω~((s/2)(deg⁡ε(f)−4)/16).(56)\widetilde{\Omega}\left(2^{n/4}\right)=\widetilde{\Omega}\left(2^{(\log(s/2))(\deg_{\varepsilon}(f)-4)/16}\right)=\widetilde{\Omega}\left((s/2)^{(\deg_{\varepsilon}(f)-4)/16}\right). \tag*{(56)}

This completes the proof.

In comparison, the quantum algorithm only costs O~(s⋅deg⁡ε(f))\widetilde{O}(s\cdot\deg_{\varepsilon}(f)), 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 Trace⁡k\operatorname{Trace}_k 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 QQ be a nn-qubit quantum circuit over the universal gate set {H,CCSIGN}\{H,\mathrm{CCSIGN}\}, where CCSIGN is a three-qubit gate that maps ∣x,y,z⟩\lvert x,y,z\rangle to (−1)xyz∣x,y,z⟩(-1)^{xyz}\lvert x,y,z\rangle. Assume there are mm Hadamard gates in QQ. Then there exist f1,…,fk:{0,1}n+1→{1,−1}f_1,\ldots,f_k:\{0,1\}^{n+1}\to\{1,-1\} with k=O(m)k=O(m) such that Q′=H⊗(n+1)Of1⋯H⊗(n+1)OfkH⊗(n+1)Q'=H^{\otimes(n+1)}O_{f_1}\cdots H^{\otimes(n+1)}O_{f_k}H^{\otimes(n+1)}, where Q′Q' is either (Q⊗I)(In⊗H)(Q\otimes I)(I_n\otimes H) or Q⊗IQ\otimes I depending on the number of appearance of the one dummy qubit in the construction. This implies that

12n+1Tr⁡[Q′]=12nTr⁡[Q]=12n+1Tr⁡[H⊗(n+1)Of1⋯H⊗(n+1)OfkH⊗(n+1)].(57)\frac{1}{2^{n+1}}\operatorname{Tr}[Q']=\frac{1}{2^n}\operatorname{Tr}[Q]=\frac{1}{2^{n+1}}\operatorname{Tr}[H^{\otimes(n+1)}O_{f_1}\cdots H^{\otimes(n+1)}O_{f_k}H^{\otimes(n+1)}]. \tag*{(57)}
=12n+1Tr⁡[Ofkf1H⊗(n+1)⋯Ofk−1H⊗(n+1)](58)= \frac{1}{2^{n+1}} \operatorname{Tr}\left[O_{f_k f_1} H^{\otimes(n+1)} \cdots O_{f_{k-1}} H^{\otimes(n+1)}\right] \tag*{(58)}
=Trace⁡k−1(fkf1,f2,…,fk−1).(59)= \operatorname{Trace}_{k-1}(f_k f_1, f_2, \ldots, f_{k-1}). \tag*{(59)}

Since QQ comes from a universal gate set, estimating 12nTr⁡[Q]\frac{1}{2^n} \operatorname{Tr}[Q] is DQC1-complete. As a result, estimating Trace⁡k\operatorname{Trace}_k 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:

  1. The DQC1 algorithm proposed in [9] for estimating the normalized trace of f(A)f(A) applies to any KK-Lipschitz function with K=poly⁡(n)K = \operatorname{poly}(n). 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 Ed/Ed−1<1/2E_d/E_{d-1} < 1/2.

  1. It remains interesting to determine the optimal classical query complexity of Trace⁡k\operatorname{Trace}_k. Proposition 1.5 gives an Ω~(N1/4)\widetilde{\Omega}(N^{1/4}) lower bound for Trace⁡4\operatorname{Trace}_4, which is sufficient for establishing our exponential quantum–classical separation. However, this bound does not match the conjectured Ω~(N1/2)\widetilde{\Omega}(N^{1/2}) 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 Ed/Ed−1<1/2E_d/E_{d-1} < 1/2 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 kk, even for k=4k = 4.

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, d=deg⁡~E(f)d = \widetilde{\deg}_E(f). We now prove this claim. Note that the dual form of (23) is

max⁡hi ∑i∈[d+2]f(xi)hi(60)\max_{h_i}\ \sum_{i\in[d+2]} f(x_i)h_i \tag*{(60)}
s.t.∑i∈[d+2]hixik=0,∀k∈{0,1,…,d},(61)\mathrm{s.t.}\quad\sum_{i\in[d+2]} h_i x_i^k = 0,\quad\forall k\in\{0,1,\ldots,d\}, \tag*{(61)}
∑i∈[d+2]∣hi∣=1.(62)\sum_{i\in[d+2]} |h_i| = 1. \tag*{(62)}

The dual solution is

hi=αxi∏j≠i(xi−xj),i∈[d+2],(63)h_i = \frac{\alpha}{x_i\prod_{j\ne i}(x_i-x_j)},\quad i\in[d+2], \tag*{(63)}

where α∈R\alpha\in\mathbb{R} is a free parameter, which is determined by the constraint (A.3). To recover the optimal solution of the primal LP, we assume that g(x)=∑k=0dgkxkg(x)=\sum_{k=0}^{d}g_kx^k. Let gk=gk+−gk−g_k=g_k^+-g_k^- with gk+,gk−≥0g_k^+,g_k^-\ge0. Then in matrix form, (24) is

\begin{pmatrix} 1 & x_1^0 & \cdots& x_1^d & -x_1^0 & \cdots& -x_1^d\\ \vdots& \vdots& & \vdots& \vdots& & \vdots\\ 1 & x_{d+2}^0 & \cdots& x_{d+2}^d & -x_{d+2}^0 & \cdots& -x_{d+2}^d\\ 1 & -x_1^0 & \cdots& -x_1^d & x_1^0 & \cdots& x_1^d\\ \vdots& \vdots& & \vdots& \vdots& & \vdots\\ 1 & -x_{d+2}^0 & \cdots& -x_{d+2}^d & x_{d+2}^0 & \cdots& x_{d+2}^d \end{pmatrix} \begin{pmatrix} \delta\\ g_0^+\\ \vdots\\ g_d^+\\ g_0^-\\ \vdots\\ g_d^- \end{pmatrix} \ge \begin{pmatrix} f(x_1)\\ \vdots\\ f(x_{d+2})\\ -f(x_1)\\ \vdots\\ -f(x_{d+2}) \end{pmatrix}. \tag*{(64)}\end{pmatrix}

The objective function can be written as

δ=(1,0,…,0,0,…,0)(δg0+⋮gd+g0−⋮gd−).(65)\delta=(1,0,\ldots,0,0,\ldots,0) \begin{pmatrix} \delta\\ g_0^+\\ \vdots\\ g_d^+\\ g_0^-\\ \vdots\\ g_d^- \end{pmatrix}. \tag*{(65)}

Therefore, the dual form has an objective function

∑i=1d+2f(xi)(hi+−hi−).(66)\sum_{i=1}^{d+2} f(x_i)(h_i^+-h_i^-). \tag*{(66)}

The constraints are described by the following

\begin{pmatrix} 1 & \cdots& 1 & 1 & \cdots& 1\\ x_1^0 & \cdots& x_{\ell+2}^0 & -x_1^0 & \cdots& -x_{\ell+2}^0\\ \vdots& & \vdots& \vdots& & \vdots\\ x_1^d & \cdots& x_{\ell+2}^d & -x_1^d & \cdots& -x_{\ell+2}^d\\ -x_1^0 & \cdots& -x_{\ell+2}^0 & x_1^0 & \cdots& x_{\ell+2}^0\\ \vdots& & \vdots& \vdots& & \vdots\\ -x_1^d & \cdots& -x_{\ell+2}^d & x_1^d & \cdots& x_{\ell+2}^d \end{pmatrix} \begin{pmatrix} h_1^+\\ \vdots\\ h_{d+2}^+\\ h_1^-\\ \vdots\\ h_{d+2}^- \end{pmatrix} \le \begin{pmatrix} 1\\ 0\\ \vdots\\ 0\\ 0\\ \vdots\\ 0 \end{pmatrix}. \tag*{(67)}\end{pmatrix}

Namely,

∑i=1d+2(hi++hi−)≤1,(68)\sum_{i=1}^{d+2}(h_i^+ + h_i^-) \leq1, \tag*{(68)}
∑i=1d+2(hi+−hi−)xik=0.(69)\sum_{i=1}^{d+2}(h_i^+ - h_i^-)x_i^k = 0. \tag*{(69)}

Denote hi=hi+−hi−h_i=h_i^+-h_i^-, then we obtain the dual LP (A.1). WLOG, we assume that x1>⋯>xd+2>0x_1>\cdots>x_{d+2}>0 and α>0\alpha>0, then

{hi+=αxi∏j≠i(xi2−xj2),hi−=0,i is oddhi+=0,hi−=−αxi∏j≠i(xi2−xj2),i is even(70)\left\{ \begin{aligned} h_i^+&=\frac{\alpha}{x_i\prod_{j\ne i}(x_i^2-x_j^2)},\quad h_i^-=0,\quad i\text{ is odd}\\ h_i^+&=0,\quad h_i^-=-\frac{\alpha}{x_i\prod_{j\ne i}(x_i^2-x_j^2)},\quad i\text{ is even} \end{aligned} \right. \tag*{(70)}

From the complementary slackness between LP and dual LP, we know that if hi+>0h_i^+>0 (or hi−>0h_i^->0), then the corresponding constraint of the primal LP is tight, i.e., it is an equality in (A.5). We now assume d+2=2md+2=2m is even for convenience. Then we obtain the following linear system:

\begin{pmatrix} 1 & x_1^0 & \cdots& x_1^d & -x_1^0 & \cdots& -x_1^d\\ 1 & x_{2m-1}^0 & \cdots& x_{2m-1}^d & -x_{2m-1}^0 & \cdots& -x_{2m-1}^d\\ 1 & -x_2^0 & \cdots& -x_2^d & x_2^0 & \cdots& x_2^d\\ \vdots& \vdots& & \vdots& \vdots& & \vdots\\ 1 & -x_{2m}^0 & \cdots& -x_{2m}^d & x_{2m}^0 & \cdots& x_{2m}^d \end{pmatrix} \begin{pmatrix} \delta\\ g_0^+\\ \vdots\\ g_d^+\\ g_0^-\\ \vdots\\ g_d^- \end{pmatrix} = \begin{pmatrix} f(x_1)\\ \vdots\\ f(x_{2m-1})\\ -f(x_2)\\ \vdots\\ -f(x_{2m}) \end{pmatrix}. \tag*{(71)}\end{pmatrix}

Using gj=gj+−gj−g_j=g_j^+-g_j^-, we can simplify the above as follows:

\begin{pmatrix} 1 & x_1^0 & x_1^1 & \cdots& x_1^d\\ 1 & x_{2m-1}^0 & x_{2m-1}^1 & \cdots& x_{2m-1}^d\\ 1 & -x_2^0 & -x_2^1 & \cdots& -x_2^d\\ \vdots& \vdots& \vdots& & \vdots\\ 1 & -x_{2m}^0 & -x_{2m}^1 & \cdots& -x_{2m}^d \end{pmatrix} \begin{pmatrix} \delta\\ g_0\\ g_1\\ \vdots\\ g_d \end{pmatrix} = \begin{pmatrix} f(x_1)\\ \vdots\\ f(x_{2m-1})\\ -f(x_2)\\ \vdots\\ -f(x_{2m}) \end{pmatrix}. \tag*{(72)}\end{pmatrix}

The above defines a linear system of 2m×2m2m\times2m with a unique solution. For g(x)=g0+g1x+⋯+gdxdg(x)=g_0+g_1x+\cdots+g_dx^d, we have g(xi)=f(xi)+(−1)iδg(x_i)=f(x_i)+(-1)^i\delta 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 x1,…,xd+2x_1,\ldots,x_{d+2} 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. [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. [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. [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. [4]Daniel Boley and Gene H Golub. A modified method for reconstructing periodic Jacobi matrices. Mathematics of Computation, 42(165):143–150, 1984.
  5. [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. [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. [7]Fernando GSL Brandão. Entanglement theory and the quantum simulation of many-body physics. arXiv:0810.0026, 2008.
  8. [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. [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. [10]Marco Cerezo, Alexander Poremba, Lukasz Cincio, and Patrick J Coles. Variational quantum fidelity estimation. Quantum, 4:248, 2020.
  11. [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. [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. [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. [14]Warren E Ferguson. The construction of Jacobi and periodic Jacobi matrices with prescribed spectra. Mathematics of Computation, 35(152):1203–1220, 1980.
  15. [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. [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. [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. [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. [19]Michael Golomb. Lectures on Theory of Approximation. Argonne National Laboratory, Applied Mathematics Division, 1962.
  20. [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. [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. [22]Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. Physical Review Letters, 81(25):5672, 1998.DOI
  23. [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. [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. [25]A. Markov. On a question by D. I. Mendeleev. Zap. Imp. Akad. Nauk. St. Petersburg, 62:1–24, 1890.
  26. [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. [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. [28]Subhayan Roy Moulik and Sergii Strelchuk. DQC1-hardness of estimating correlation functions. arXiv:2411.05208, 2024.arxiv.org/abs/2411.05208
  29. [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. [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. [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. [32]Changpeng Shao and Xinzhao Wang. DQC1-hardness of estimating log-determinants. Available at https://changpeng-shao.github.io/complexity_logdet.pdf.
  33. [33]Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 58(2):133–161, 2009.DOI
  34. [34]Dan Shepherd. Computation with unitaries and one pure qubit. arXiv preprint quant-ph/0608132, 2006.DOI
  35. [35]Daniel James Shepherd. Quantum complexity: restrictions on algorithms and architectures. arXiv:1005.1425, 2010.arxiv.org/abs/1005.1425
  36. [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. [37]Lloyd N. Trefethen. Approximation Theory and Approximation Practice, Extended Edition. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2019.DOI
  38. [38]Pierre van Moerbeke. The spectrum of Jacobi matrices. Inventiones Mathematicae, 37(1):45–81, 1976.DOI
  39. [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. [40]Yuxin Zhang and Changpeng Shao. Quantum space-depth tradeoffs for coherent block encodings. arXiv:2607.01843v2, 2026.arxiv.org/abs/2607.01843
  41. [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

Paper details

vlnc:W_n97j3qqd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

GPT-5.6 Sol (bare)

View statement
Looking for related papers…
Contents