# Dequantization and Hardness of Spectral Sum Estimation

Roman Edenhofer, Atsuya Hasegawa, François Le Gall

► To cite this version:

Roman Edenhofer, Atsuya Hasegawa, François Le Gall. Dequantization and Hardness of Spectral Sum Estimation. 2025. hal-05319339

HAL Id: hal-05319339

https://hal.science/hal-05319339v1

Preprint submitted on 17 Oct 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Dequantization and Hardness of Spectral Sum Estimation

Roman Edenhofer*¹, Atsuya Hasegawa†², and François Le Gall‡²

¹Université Paris Cité, CNRS, IRIF, Paris, France

²Graduate School of Mathematics, Nagoya University, Japan

## Abstract

We give new dequantization and hardness results for estimating spectral sums of matrices, such as the log-determinant. Recent quantum algorithms have demonstrated that the logarithm of the determinant of sparse, well-conditioned, positive matrices can be approximated to $\varepsilon$-relative accuracy in time polylogarithmic in the dimension $N$, specifically in time poly($\log(N)$, $s$, $\kappa$, $1/\varepsilon$), where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. We provide a simple dequantization of these techniques that preserves the polylogarithmic dependence on the dimension. Our classical algorithm runs in time polylog($N$) $\cdot s^{O(\sqrt{\kappa} \log \kappa / \varepsilon)}$ which constitutes an exponential improvement over previous classical algorithms in certain parameter regimes.

We complement our classical upper bound with DQC1-completeness results for estimating specific spectral sums such as the trace of the inverse and the trace of matrix powers for log-local Hamiltonians, with parameter scalings analogous to those of known quantum algorithms. Assuming BPP $\subseteq$ DQC1, this rules out classical algorithms with the same scalings. It also resolves a main open problem of Cade and Montanaro (TQC 2018) concerning the complexity of Schatten-$p$ norm estimation. We further analyze a block-encoding input model, where instead of a classical description of a sparse matrix, we are given a block-encoding of it. We show DQC1-completeness in a very general way in this model for estimating tr[$f(A)$] whenever $f$ and $f^{-1}$ are sufficiently smooth.

We conclude our work with BQP-hardness and PP-completeness results for high-accuracy log-determinant estimation.

<footnote>*edenhofer@irif.fr</footnote>

<footnote>†atsuya.hasegawa@math.nagoya-u.ac.jp</footnote>

<footnote>‡legall@math.nagoya-u.ac.jp</footnote>
# Contents

<table><thead><tr><th></th><th></th></tr></thead><tbody><tr><td><strong>1 Introduction</strong></td><td><strong>2</strong></td></tr><tr><td>1.1 Background</td><td>2</td></tr><tr><td>1.2 Our results</td><td>3</td></tr><tr><td>1.3 Our techniques</td><td>5</td></tr><tr><td>1.4 Open Questions</td><td>8</td></tr><tr><td>1.5 Organization of this paper</td><td>9</td></tr><tr><td><strong>2 Preliminaries</strong></td><td><strong>9</strong></td></tr><tr><td>2.1 Hoeffding's inequality</td><td>9</td></tr><tr><td>2.2 Taylor's theorem</td><td>9</td></tr><tr><td>2.3 Complexity classes</td><td>9</td></tr><tr><td>2.4 Sparse-access to matrices and other input models</td><td>10</td></tr><tr><td><strong>3 A simple classical algorithm for spectral sums</strong></td><td><strong>11</strong></td></tr><tr><td>3.1 Baby version of our algorithm</td><td>11</td></tr><tr><td>3.2 Speeding up our algorithm via Chebyshev approximation</td><td>14</td></tr><tr><td>3.3 A specialized algorithm for k-local Hamiltonians</td><td>16</td></tr><tr><td><strong>4 DQC1-completeness of estimating several spectral sums</strong></td><td><strong>18</strong></td></tr><tr><td>4.1 DQC1-containment for log-local Hamiltonians</td><td>18</td></tr><tr><td>4.2 DQC1-hardness for log-local Hamiltonians</td><td>18</td></tr><tr><td>4.2.1 Brandão's DQC1-circuit to Hamiltonian construction</td><td>18</td></tr><tr><td>4.2.2 Estimating $\frac{1}{2^n} \text{tr}[H^{-1}] \pm 1/\text{poly}(n)$ is DQC1-hard</td><td>20</td></tr><tr><td>4.2.3 Estimating $\frac{1}{2^n} \text{tr}[H^p] \pm 1/\text{poly}(n)$ is DQC1-hard</td><td>21</td></tr><tr><td>4.3 Block-encoding input model</td><td>23</td></tr><tr><td><strong>5 BQP-hardness and PP-completeness of estimating the log-determinant</strong></td><td><strong>26</strong></td></tr><tr><td>5.1 BQP- and PP-hardness of the (log-)determinant</td><td>26</td></tr><tr><td>5.2 PP-containment</td><td>29</td></tr><tr><td><strong>A Omitted proof of Lemma 3.6</strong></td><td><strong>34</strong></td></tr></tbody></table>

# 1 Introduction

## 1.1 Background

For a Hermitian matrix $A \in \mathbb{C}^{N \times N}$ and a function $f$ defined on the spectrum of $A$, the spectral sum is

$$ \text{tr}[f(A)] = \sum_{i=1}^{N} f(\lambda_i), $$

where $\lambda_1, \dots, \lambda_N$ are the eigenvalues of $A$. A central example, and the main focus of this work, is the log-determinant

$$ \log \det(A) = \log \left( \prod_{i=1}^{N} \lambda_i \right) = \sum_{i=1}^{N} \log \lambda_i. $$

An $\varepsilon$-additive approximation to $\log \det(A)$ corresponds to an $(e^\varepsilon - 1) \approx \varepsilon$ multiplicative approximation to the determinant of $A$, for small $\varepsilon > 0$. Other spectral sums of interest include the partition function $Z(A, \beta) = \text{tr}[e^{-\beta A}]$ with inverse temperature $\beta > 0$, the trace of powers $\text{tr}[A^p]$ which corresponds to Schatten $p$-norms, and the trace of the inverse $\text{tr}[A^{-1}]$.
Spectral sums arise in diverse areas such as machine learning, computational chemistry, bio- ology, statistics, and finance (see, e.g., [ABB00, WR06, NHD12]), and many classical estimation algorithms have been proposed (see, e.g., [HMS15, UCS17, MMMW21]). Most of these methods build on Hutchinson's stochastic trace estimator [Hut89]: for a random vector $v \in \mathbb{R}^N$ with $\mathbb{E}[vv^T] = I$, one has $\mathrm{tr}[A] = \mathbb{E}[v^T A v]$. In practice, $v$ is often drawn from the Rademacher distribution which minimizes the estimators variance. The time to evaluate $v^T A v$ is then determined by the time for matrix-vector multiplication and scales linearly in the number of nonzero entries of $A$. For instance, the fastest known classical algorithm estimates the log-determinant with relative error $\varepsilon$ in time

$$O\left(\frac{\sqrt{\kappa} \|A\|_0}{\varepsilon^2} \log\left(\frac{\kappa}{\varepsilon\delta}\right)\right),$$

where $\delta$ is the failure probability and $\|A\|_0$ the number of nonzeros of $A$ [HMS15]. Even if $A$ is sparse with at most $s$ nonzeros per row and column, $\|A\|_0$ typically still scales polynomially with $N$.

Recently, several quantum algorithms for estimating spectral sums, most notably the log-determinant, have been proposed [ZFO$^{+}$19, LS20, GLM25]. For sparse matrices, these algorithms avoid the polynomial dependence on the matrix dimension $N$, achieving instead an $\varepsilon$-relative approximation to $\log \det(A)$ in time $\mathrm{poly}(\log N, s, \kappa, 1/\varepsilon)$, where $s$ is the sparsity and $\kappa$ the condition number of the input matrix. The algorithms of [ZFO$^{+}$19, GLM25] employ phase estimation of $e^{iA}$ on the maximally mixed state, thereby sampling eigenvalues approximately uniformly; taking logarithms of these samples yields an estimate of the log-determinant. In contrast, the approach of [LS20] first implements a block-encoding of $A$ and applies quantum singular value transformation [GSLW19] to approximate $\log(A)$ by a polynomial $p(A)$. Amplitude estimation within a Hadamard test then allows to estimate the log-determinant.

These algorithms are closely related to the model of quantum computation with few clean qubits, known as DQC1, introduced by Knill and Laflamme [KL98] in the context of high-temperature NMR (nuclear magnetic resonance) quantum devices. In this model, one applies a polynomial-time quantum circuit to the $n$-qubit state

$$\rho = |0\rangle \langle 0| \otimes \frac{1}{2^{n-1}} I_{n-1},$$

where a single qubit is initialized in $|0\rangle$ and the remaining qubits are maximally mixed. It was shown in [CM18] that for log-local Hamiltonians, a subclass of $s = \mathrm{poly}(n)$ sparse matrices, any sufficiently smooth spectral sum $\mathrm{tr}[f(A)]$ can be estimated in DQC1 within parameters comparable to the quantum algorithms discussed above. The key limitation of this result is that it does not extend to general sparse matrices. Nevertheless, all of the examples from above, including the log-determinant, are encompassed in this framework. We also remark that Brandão [Bra08] established that estimating the normalized partition function $\frac{1}{2^n}Z(A, \beta)$ for $\beta = \mathrm{poly}(n)$ is DQC1-hard.

A natural question, raised recently by Aaronson [Aar25] in response to the work of [GLM25], is whether these quantum algorithms for the log-determinant can be dequantized, that is whether there exists a classical algorithm with similar runtime parameters.

The story of dequantization results typically begins with Tang [Tan19] who discovered a classical polynomial-time algorithm for recommendation systems, which was believed to offer an exponential quantum advantage by the quantum algorithm of Kerenidis and Prakash [KP17]. More recently, it was shown [CGL$^{+}$22, GLG23, BT24, Le 25] that one can dequantize the quantum singular value transformation [GSLW19], a powerful algorithmic framework that captures many of the currently known quantum algorithms.

## 1.2 Our results

As our first contribution, we answer Aaronson's dequantization question [Aar25] partly in the affirmative and present a classical algorithm for estimating spectral sums such as the log-
determinant in time polylogarithmic in the matrix dimension. For this, we assume we are given
sparse access to an $s$ sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$, meaning that in time poly($n$) we can
query the at most $s$ nonzero entries per row and column of $A$. We write $O^*(T)$ for $\tilde{O}(T \text{ poly}(n))$,
suppressing such polynomial overheads for any time bound $T$. Our classical algorithm is sum-
marized in the following theorem.

**Theorem 1.1 (Theorem 3.4).** Given sparse-access to an $s$ sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ satisfying $\|A\| \le 1$, and a degree $d$ polynomial $p(x) = \sum_{k=0}^d c_k x^k$ so that $|p(x)| \le 1$ for all $x \in [-1, 1]$, there is a classical algorithm running in time $O^*(s^d/\epsilon^2)$ which outputs with probability at least $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[p(A)]$.

This theorem is the basis for all our classical spectral sum estimation algorithms. For example, the logarithm can be approximated within error $\epsilon$ on the interval $[1/\kappa, 1]$ by a polynomial of degree $d = O(\sqrt{\kappa \log(\kappa/\epsilon)})$, which yields the following.

**Corollary 1.2** (contained in **Corollary 3.11**). *Given sparse-access to an $s$ sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ with spectrum in $[\frac{1}{\kappa}, 1]$, there is a classical algorithm running in time $O^*(s^{c\sqrt{\kappa}\log(\kappa/\epsilon)})$ which outputs with probability $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n}\log \det(A)$. Here, $c \ge 1$ is a universal constant.*

We emphasize that an $\epsilon$-additive approximation to the normalized log-determinant $\frac{1}{2^n} \log \det(A)$ implies an $\epsilon\kappa$-relative approximation of the (non-normalized) log-determinant, provided one makes the additional assumption $\lambda_{\max}(A) \le 1 - \frac{1}{\kappa}$. Thus, the quality of our approximation is directly comparable to that in prior work. Indeed, all works that claim relative approximation guarantees for the log-determinant [HMS15, LS20, GLM25] rely on this additional assumption.

In particular, when $s = \text{poly}(n)$, there can be exponentially many non-zero elements in $A$ and thus our classical algorithm can exhibit an exponential speedup over the best known classical algorithm from [HMS15].

We complement these classical upper bounds with DQC1-completeness results for estimat-
ing two specific spectral sums: the trace of the inverse and the trace of matrix powers. This
yields a strict barrier on the achievable parameter scalings of any classical algorithm assum-
ing BPP $\subsetneq$ DQC1. The containment in DQC1 was already established by Cade and Montanaro
[CM18] but it only holds for log-local Hamiltonians which are a special case of poly($n$) sparse
matrices. Formally, we find:

**Theorem 1.3** ([CM18], **Theorems 4.4** and 4.5). *Given a log-local Hamiltonian $H \in \mathbb{C}^{2^n \times 2^n}$ with spectrum in $[\frac{1}{\text{poly}(n)}, 1]$, respectively $[-1, 1]$, estimating $\frac{1}{2^n} \text{tr}[H^{-1}]$ or $\frac{1}{2^n} \text{tr}[H^p]$ with additive error $1/\text{poly}(n)$ is DQC1-complete.*

Cade and Montanaro also proved DQC1-hardness in the case of the trace of matrix powers,
however with much stricter accuracy than the containment. Our matching hardness result thus
resolves the most immediate open problem in their work regarding the complexity of Schatten-$p$
norm estimation. Unfortunately, we could not prove an analogous DQC1-hardness result for the
estimation of the log-determinant.

However, we can prove DQC1-hardness of estimating the log-determinant with similar pa-
rameters in a different input model; namely, in the *block-encoding model*, where one is given a
polynomial-size classical description of a quantum circuit implementing a block-encoding of a
matrix. It is known that given a circuit description of a unitary $U \in \mathbb{C}^{2^n \times 2^n}$, estimating $\frac{1}{2^n} \text{tr}[U]$ within additive accuracy $1/\text{poly}(n)$ is DQC1-complete [SJ08]. We show the following general-
ization for spectral sums of block-encoded matrices.

**Theorem 1.4** (Informal version of **Theorem 4.8**). *Given a $(1, O(\log n), \frac{1}{\text{poly}(n)})$ block-encoding of a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$, if $f$ and $f^{-1}$ are sufficiently smooth, estimating $\frac{1}{2^n} \text{tr}[f(A)]$ with additive error $1/\text{poly}(n)$ is DQC1-complete.*
In particular estimating the log-determinant is DQC1-hard (Corollary 4.9). Among the input models we consider, block-encodings are in some sense the easiest to obtain. From either a log-local Hamiltonian or sparse access to a matrix A, one can efficiently construct a quantum circuit implementing a block-encoding of A. However, only for log-local Hamiltonians can this be achieved with $O(\log n)$ ancilla qubits, as implicitly shown in [CM18], which is still compatible with DQC1. For general sparse matrices, the standard block-encoding approaches require $O(n)$ ancilla qubits [ATS03, BCK15, GSLW19], and fall outside the DQC1 framework.

Finally, we establish BQP-hardness and PP-completeness for high-accuracy log-determinant estimation.

**Theorem 1.5** (Theorem 5.3 and Corollary 5.5). Given sparse-access to a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ with spectrum in $[\frac{1}{\text{poly}(n)}, 1]$, is BQP-hard, and

1. estimating $\log \det(A)$ with additive accuracy $\varepsilon = \frac{1}{\text{poly}(n)}$ is BQP-hard, and

2. estimating $\log \det(A)$ with additive accuracy $\varepsilon = \frac{1}{\exp(n)}$ is PP-complete.

Most of our main results are summarized in Tables 1 to 4. Throughout these tables we assume that $A \in \mathbb{C}^{2^n \times 2^n}$ is a poly(n) sparse hermitian matrix and that $H \in \mathbb{C}^{2^n \times 2^n}$ is a log-local Hamiltonian. Further, the maximum eigenvalue of the matrices is at most 1 and the condition number is the ratio of maximum and minimum eigenvalue $\kappa(A) = \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}$. To our knowledge, no classical quasi-polynomial-time algorithm is known that can simulate DQC1 circuits. Hence, the apparent quantum advantage of DQC1 does not stem from achieving higher estimation accuracy $\varepsilon$, but rather from the broader class of matrices it can handle, namely those with weaker restrictions on $\kappa$, $p$ or $\beta$, respectively.

<table><caption>Table 1: The computational complexity of estimating $\log \det(A)$ at various accuracies and condition numbers. The DQC1-containment only holds for log-local Hamiltonians. The DQC1-completeness result (Corollary 4.9) for the block-encoding model is not shown above.</caption><thead><tr><th>conditioning</th><th>accuracy</th><th>complexity</th></tr></thead><tbody><tr><td>κ = const</td><td><sup>1</sup>&frasl;<sub>2<sup>n</sup></sub> log det(A) ± const</td><td>∈ BPP (Corollary 3.7)</td></tr><tr><td>κ = polylog(n)</td><td><sup>1</sup>&frasl;<sub>2<sup>n</sup></sub> log det(A) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>quasi-poly time classical algo<br>(Corollary 3.7)</td></tr><tr><td>κ = poly(n)</td><td><sup>1</sup>&frasl;<sub>2<sup>n</sup></sub> log det(H) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>∈ DQC1 ([CM18])</td></tr><tr><td>κ = poly(n)</td><td><sup>1</sup>&frasl;<sub>2<sup>n</sup></sub> log det(A) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>∈ BQP<br>([ZFO<sup>+</sup>19, LS20, GLM25])</td></tr><tr><td>κ = poly(n)</td><td>log det(A) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>BQP-hard<br>(Theorem 5.3)</td></tr><tr><td>κ = poly(n)</td><td>log det(A) ± <sup>1</sup>&frasl;<sub>exp(n)</sub></td><td>PP-complete<br>(Theorem 5.3, Corollary 5.5)</td></tr></tbody></table>

## 1.3 Our techniques

### Our classical algorithm

Our classical algorithm is motivated by two complementary threads: (i) the Quantum Singular Value Transformation (QSVT) framework [GSLW19], which underlies many quantum spectral
<table><caption>Table 2: The computational complexity of estimating tr[A<sup>-1</sup>]. The DQC1-containment only holds for log-local Hamiltonians.</caption><thead><tr><th>conditioning</th><th>accuracy</th><th>complexity</th></tr></thead><tbody><tr><td>κ = const</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[A<sup>-1</sup>] ± const</td><td>∈ BPP (Corollary 3.7)</td></tr><tr><td>κ = polylog(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[A<sup>-1</sup>] ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>quasi-poly time classical algo (Corollary 3.7)</td></tr><tr><td>κ = poly(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[H<sup>-1</sup>] ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>DQC1-complete ([CM18] &amp; Theorem 4.4)</td></tr><tr><td>κ = poly(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[A<sup>-1</sup>] ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>∈ BQP ([LS20, GLM25])</td></tr><tr><td>κ = poly(n)</td><td>tr[A<sup>-1</sup>] ± <sup>1</sup>&frasl;<sub>exp(n)</sub></td><td>∈ PP (Corollary 5.5)</td></tr></tbody></table>

<table><caption>Table 3: The computational complexity of estimating tr[A<sup>p</sup>]. The DQC1-containment only holds for log-local Hamiltonians.</caption><thead><tr><th>power</th><th>accuracy</th><th>complexity</th></tr></thead><tbody><tr><td>p = const</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[A<sup>p</sup>] ± const</td><td>∈ BPP ([AGSS23] or Theorem 3.4)</td></tr><tr><td>p = polylog(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[A<sup>p</sup>] ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>quasi-poly time classical algo ([AGSS23] or Theorem 3.4)</td></tr><tr><td>p = poly(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[H<sup>p</sup>] ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>DQC1-complete ([CM18] &amp; Theorem 4.5)</td></tr><tr><td>p = poly(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> tr[A<sup>p</sup>] ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>∈ BQP ([LS20, GLM25])</td></tr><tr><td>p = poly(n)</td><td>tr[A<sup>p</sup>] ± <sup>1</sup>&frasl;<sub>exp(n)</sub></td><td>∈ PP (Corollary 5.5)</td></tr></tbody></table>

<table><caption>Table 4: The computational complexity of estimating the partition function Z(A, β) = Σ<sub>j</sub> e<sup>-βλ<sub>j</sub>(A)</sup>. The DQC1-containment only holds for log-local Hamiltonians.</caption><thead><tr><th>inverse temperature</th><th>accuracy</th><th>complexity</th></tr></thead><tbody><tr><td>β = const</td><td><sup>1</sup>&frasl;<sub>2n</sub> Z(A, β) ± const</td><td>∈ BPP (Corollary 3.7)</td></tr><tr><td>β = polylog(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> Z(A, β) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>quasi-poly time classical algo (Corollary 3.7)</td></tr><tr><td>β = poly(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> Z(H, β) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>DQC1-complete ([Bra08, CM18, CSS21])</td></tr><tr><td>β = poly(n)</td><td><sup>1</sup>&frasl;<sub>2n</sub> Z(A, β) ± <sup>1</sup>&frasl;<sub>poly(n)</sub></td><td>∈ BQP ([LS20, GLM25])</td></tr><tr><td>β = poly(n)</td><td>Z(A, β) ± <sup>1</sup>&frasl;<sub>exp(n)</sub></td><td>∈ PP (Corollary 5.5)</td></tr></tbody></table>
algorithms, and (ii) the dequantization program initiated by Tang [Tan19] and developed in subsequent works (e.g. [CGL+22, GLG23, BT24, Le 25]). While these ideas might suggest a complex procedure, the resulting classical algorithm is remarkably simple: it essentially amounts to sampling a diagonal element of the matrix, evaluating a low-degree polynomial $p(A)$ at that element, and then applying a standard averaging argument.

Formally, for the maximally entangled state $|\Phi\rangle = \frac{1}{\sqrt{2^n}} \sum_{i \in [2^n]} |i\rangle|i\rangle$ we have

$$ \langle\Phi|(f(A) \otimes I)|\Phi\rangle = \frac{1}{2^n} \sum_{i,j=1}^{2^n} \langle i|f(A)|j\rangle \langle i|j\rangle = \frac{1}{2^n} \sum_{i=1}^{2^n} f(A)(i,i) = \frac{1}{2^n} \text{tr}[f(A)]. $$

We find that when $f = p$ is a polynomial of degree $d$, the diagonal entry $p(A)(i,i)$ can be expressed as a linear combination of entries of powers $A^k$ for $k \le d$. For an $s$ sparse matrix, each term $A^k(i,i)$ is supported on closed walks of length $k$ starting and ending at $i$, and can be computed by exploring the $s$-ary tree of such walks, as described in [GLG23] and recalled in Corollary 3.3.

Sampling $i \in [2^n]$ uniformly and evaluating $p(A)(i,i)$ yields a simple unbiased estimator of $\frac{1}{2^n} \text{tr}[p(A)]$ with runtime $O^*(s^d/\epsilon^2)$. For general smooth $f$, we choose a polynomial $p$ so that $\|f - p\|_{\infty}$ is sufficiently small on the spectrum of $A$ and find that $\frac{1}{2^n} \text{tr}[p(A)]$ gives a good approximation for the normalized trace $\frac{1}{2^n} \text{tr}[f(A)]$. When $f$ is a monomial, this reduces to the algorithm of [AGSS23]; our contribution is to generalize this approach to other spectral functions which can be well-approximated by a low-degree polynomial.

## DQC1-completeness for log-local Hamiltonians

Brandão [Bra08] adapted Kitaev’s circuit-to-Hamiltonian construction [KSV02] to the DQC1 setting. While Kitaev’s original construction encodes the acceptance probability of a BQP circuit into the ground-state energy of a local Hamiltonian, Brandão’s variant encodes the rejection probability of a DQC1 circuit for input size $n$ and depth $T$ into the average of the first $2^{n-1}$ out of $2^{n+\log T}$ eigenvalues of a Hamiltonian (see Theorem 4.3 for a precise statement). As a consequence, Brandão showed that estimating the normalized partition function $\frac{1}{2^n}Z(H, \beta)$ with inverse-polynomial additive error is DQC1-complete for $\beta = \text{poly}(n)$. This relies on the fact that $e^{-\beta x}$ decays exponentially fast with growing $x$, so the contributions of the higher eigenvalues to the partition function can be safely neglected.

We refine Brandão’s approach using Taylor’s theorem with explicit remainder bounds to obtain fine-grained control over more general spectral sums. Working with a carefully conditioned variant of Brandão’s circuit-to-Hamiltonian construction, we show that estimating the trace of the inverse of this variant allows one to recover the average of the first $2^{n-1}$ eigenvalues of the original Hamiltonian, and thereby determine the rejection probability of the corresponding DQC1 circuit. Since $1/x$ decays much more slowly than $e^{-\beta x}$, this requires a more detailed error analysis than in Brandão’s work. A similar argument applies to traces of large powers, $\text{tr}[H^p]$ with $p = \text{poly}(n)$, yielding DQC1-hardness for these spectral sums as well.

## DQC1-completeness for the block-encoding input model

The block-encoding model gives another natural input format: one is given a classical description of a quantum circuit that implements a unitary $U_A$ whose top-left block is proportional to $A$. It is folklore [SJ08] that estimating $\frac{1}{2^n} \text{tr}[U]$ given a circuit description of unitary $U$ is DQC1-complete. This easily extends to estimating the normalized trace of a Hermitian matrix given by an explicit block-encoding that uses only $O(\log n)$ ancillas which we show in Theorem 4.6.

We then show DQC1-completeness of estimating $\frac{1}{2^n} \text{tr}[f(A)]$ in a very general way with the quantum singular value transformation toolkit. Assuming $f$ and $f^{-1}$ are sufficiently smooth
(in particular admitting polynomial approximations of degree poly(n) with inverse-polynomial uniform error on the spectrum of A), there exist polynomials p and q with

$$p(x) \approx f(x), \quad q(x) \approx f^{-1}(x).$$

Given a (1, O(log n), 1/ poly(n)) block-encoding $U_A$ one can use QSVT [GSLW19] to efficiently construct block-encodings of $p(A)$ and $q(A)$. As such, we obtain DQC1-containment of estimating $\frac{1}{2^n}$ tr[$f(A)$] by applying our DQC1 procedure to estimate the normalized trace of the block-encoded $p(A)$. Hardness follows by the converse reduction: since computing $\frac{1}{2^n}$ tr[$A$] is DQC1-hard when A is given as an O(log n)-ancilla block-encoding, constructing $q(A) \approx f^{-1}(A)$ via QSVT yields an instance where $\frac{1}{2^n}$ tr[$f(q(A))$] $\approx \frac{1}{2^n}$ tr[$A$], so hardness of the former implies hardness of the latter.

## BQP-hardness and PP-completeness of the log-determinant

To obtain hardness for high-accuracy log-determinant estimation we reduce from the (well-studied) matrix-inversion problem. It is standard in the literature on quantum algorithms for linear systems (e.g. [HHL09]) and subsequent hardness reductions that entrywise estimation of $A^{-1}$ for a well-conditioned sparse matrix is BQP-hard when inverse-polynomial accuracy is required, and becomes PP-hard when inverse-exponential accuracy is demanded.

We present a polynomial-time reduction from entrywise inversion to log-determinant computation on positive semidefinite sparse matrices building on a similar line of reductions that has been studied in the space-bounded setting by Fefferman and Remscrim [FR21]. The PP upper bound with inverse-exponential accuracy follows from the fact that PP can decide sums of exponentially many efficiently computable terms to inverse-exponential precision: concretely, tr[$p(A)$] for a poly(n) degree polynomial p can be written as a sum of $2^{\text{poly}(n)}$ terms each computable in poly(n) time, so the exponential-precision value lies in PP. Since approximating log(x) on $[1/\kappa, 1]$ to additive accuracy $\epsilon$ requires a Taylor truncation of degree $d = O(\kappa \log(1/\epsilon))$, choosing $\epsilon = 1/\exp(n)$ still yields $d = \text{poly}(n)$ whenever $\kappa = \text{poly}(n)$, which completes the argument for PP-completeness in the exponential-accuracy regime.

## 1.4 Open Questions

The comparison between BQP and DQC1 algorithms for spectral sums in our results highlights two natural open directions.

1. Can a BQP spectral-sum algorithm improve parameters of the DQC1 algorithm? In particular, are there BQP algorithms that achieve better dependence on condition number $\kappa$, on accuracy, or on other resources than the known DQC1 procedures?

2. Can DQC1 be made to apply to general sparse-access matrices instead of just log-local Hamiltonians? We wonder in particular if there is a method to construct a block-encoding of a $2^n \times 2^n$ sparse matrix using only O(log n) clean ancilla qubits? Existing block-encoding and Hamiltonian-simulation constructions for sparse matrices (e.g. [ATS03, BCK15, GSLW19]) typically require O(n) ancillas to implement oracles to the entries of the matrix, and this is a reason why algorithms based on the spectrum sampling in [ZFO+19, LS20, GLM25] are BQP algorithms rather than DQC1 ones. Overcoming this barrier would likely require new ideas or an altogether different paradigm for ancilla-efficient block-encodings.

A more specific technical question that remains open is whether estimating the normalized log-determinant of log-local Hamiltonians to inverse-polynomial additive accuracy is DQC1-hard. Our approach using Brandão's circuit-to-Hamiltonian construction, which succeeds for the trace of the inverse and for the trace of matrix powers, does not yield hardness for the log-determinant because the logarithm log(x) decays too slowly for $x \to 0$.
## 1.5 Organization of this paper

We now give a brief guide to the remainder of the paper.

In Section 2 we collect notation and preliminary facts, including Hoeffding's inequality, Taylor remainder bounds (see Fact 2.2), and definitions of the complexity classes referenced throughout. We also make precise the input models for matrices (sparse access, log-local Hamiltonians, and block-encodings) and summarize their relationships.

In Section 3 we present our classical algorithm for spectral sums of sparse matrices. We first describe a basic version (sufficient for the complexity-theoretic applications) and then refine it to obtain improved runtime bounds; a specialized variant for local Hamiltonians is also given.

In Section 4 we recall how the results of Cade and Montanaro [CM18] yield DQC1 algorithms for spectral sums, and then prove our DQC1-hardness results for the trace of the inverse and for traces of matrix powers. We further show DQC1-completeness of estimating smooth spectral sums if given a block-encoding of a matrix.

Finally, in Section 5 we establish BQP-hardness and PP-completeness of log-determinant estimation at the two accuracy regimes discussed above.

# 2 Preliminaries

In this section we collect some preliminaries that will be used throughout the paper. For general background on quantum computing we refer to [NC10]. We also use standard asymptotic notation throughout.

## 2.1 Hoeffding's inequality

We begin with the standard concentration inequality due to Hoeffding.

**Fact 2.1** (Hoeffding's inequality [Hoe63]). Let $X_1, \dots, X_T$ be independent random variables with expectation $\mathbb{E}[X_i] = \mu$ such that $a \le X_i \le b$ and let $\bar{X} = \frac{1}{T}(X_1 + \dots + X_T)$. Then, for all $\varepsilon > 0$,

$$ \Pr[|\bar{X} - \mu| \ge \varepsilon] \le \exp\left(\frac{-2T\varepsilon^2}{(b-a)^2}\right). $$

## 2.2 Taylor's theorem

We will also need the following standard analytic fact. Let us denote by $f^{(k)}$ the $k$-th derivative of $f$.

**Fact 2.2.** Let $I \subseteq \mathbb{R}$ be an interval, $x, x_0 \in I$ and $f: I \to \mathbb{R}$ $n$ times differentiable. Then there exists a $\xi$ between $x$ and $x_0$ such that

$$ f(x) = \sum_{k=0}^{n-1} \frac{f^{(k)}(x_0)}{k!} (x - x_0)^k + \frac{f^{(n)}(\xi)}{n!} (x - x_0)^n. $$

## 2.3 Complexity classes

We now recall the complexity classes that will appear in our results.

**Definition 2.1.** (DQC1 and DQCk) Let $L = (L_{\text{yes}}, L_{\text{no}})$ be a promise problem. Then $L \in \text{DQCk}$ if and only if there exist functions $a, b: \mathbb{N} \to [0, 1]$ such that $b-a \ge 1/\text{poly}(n)$ and a polynomial-time generated family of quantum circuits $Q = \{Q_x \mid x \in L_{\text{yes}} \cup L_{\text{no}}\}$, where each circuit $Q_x$ acts on $n = \text{poly}(|x|)$ input qubits with initial state $\rho := |0\rangle \langle 0|^{\otimes k} \otimes \frac{1}{2^{n-k}} I_{n-k}$ and consists of $T = \text{poly}(|x|)$ gates such that
• if $x \in L_{\text{yes}}$,

$$ \mu_{\text{accept}} = \text{tr} \left[ (|1\rangle \langle 1|^{\otimes 1} \otimes I_{n-1}) Q_x \rho Q_x^{\dagger} \right] \geq b, $$

• if $x \in L_{\text{no}}$,

$$ \mu_{\text{accept}} = \text{tr} \left[ (|1\rangle \langle 1|^{\otimes 1} \otimes I_{n-1}) Q_x \rho Q_x^{\dagger} \right] \leq a. $$

The following property is well known. A proof is given in [SJ08].

**Fact 2.3.** DQC1 = DQCk for $k = O(\log n)$.

In the definition above, which is standard, one implicitly assumes multiple repetitions of the DQCk circuit to reduce the error probability. In contrast, [FKM+16] introduced a variant called BQ$_{[k]}$P, where the completeness-soundness gap is constant ($b-a = \Omega(1)$), so that a single run suffices, and the number of total clean qubits needed is indeed $k$.

**Definition 2.2 (BQP).** Let $L = (L_{\text{yes}}, L_{\text{no}})$ be a promise problem. Then $L \in \text{BQP}$ if and only if there exists a polynomial-time generated family of quantum circuits $Q = \{Q_x \mid x \in L_{\text{yes}} \cup L_{\text{no}}\}$, where each circuit $Q_x$ acts on $n = \text{poly}(|x|)$ input qubits and consists of $T = \text{poly}(|x|)$ gates such that

• if $x \in L_{\text{yes}}$,

$$ \mu_{\text{accept}} = |\langle 0|^{\otimes n} Q_x |0\rangle^{\otimes n}|^2 \geq \frac{2}{3} $$

• if $x \in L_{\text{no}}$,

$$ \mu_{\text{accept}} = |\langle 0|^{\otimes n} Q_x |0\rangle^{\otimes n}|^2 \leq \frac{1}{3}. $$

This definition of BQP is slightly nonstandard, since it measures all qubits at the end rather than just one. However, the two definitions are easily seen to be equivalent: given a circuit $Q$ with a single designated output qubit, one can construct a circuit $Q'$ with acceptance probability

$$ |\langle 0|^{\otimes (n+1)} Q' |0\rangle^{\otimes (n+1)}|^2 $$

equal to the acceptance probability of $Q$, using a standard gadget described in Lemma 29 of [FL18]. The reverse direction is immediate.

**Definition 2.3 (PP).** Let $L = (L_{\text{yes}}, L_{\text{no}})$ be a promise problem. Then $L \in \text{PP}$ if and only if there exists a polynomial-time probabilistic Turing machine such that

• if $x \in L_{\text{yes}}$, the Turing machine accepts with probability no less than $\frac{1}{2}$.

• if $x \in L_{\text{no}}$, the Turing machine accepts with probability strictly less $\frac{1}{2}$.

## 2.4 Sparse-access to matrices and other input models

Finally, we describe the input models for matrices that we will consider: query- and sparse-access, local Hamiltonians, and block-encodings.

**Definition 2.4 (Query-access to matrices).** We say that we have query-access to a matrix $A \in \mathbb{C}^{2^n \times 2^n}$ in time $Q_A$ if we have access to a classical algorithm $Q_A$ which on input $(i, j) \in [2^n] \times [2^n]$, returns entry $A(i, j)$ in time $Q_A$.

**Definition 2.5 (Sparse-access to matrices).** We say that we have sparse-access to an $s$ sparse matrix $A \in \mathbb{C}^{2^n \times 2^n}$ in time $Q_A$ if we have query-access to $A$ and there exist two more classical algorithms $Q_A^{\text{row}}$ and $Q_A^{\text{col}}$ running in time $Q_A$ such that
* on inputs $(i, l) \in [2^n] \times [s]$, the algorithm $Q_A^{\text{row}}$ outputs the $l$-th non-zero entry of the $i$-th row of $A$ and its corresponding column index if this row has at least $l$ non-zero entries, and outputs an error message otherwise,

* on inputs $(j, l) \in [2^n] \times [s]$, the algorithm $Q_A^{\text{col}}$ outputs the $l$-th non-zero entry of the $j$-th column of $A$ and its corresponding row index if this column has at least $l$ non-zero entries, and outputs an error message otherwise.

Unless stated otherwise, we always assume $Q_A = \text{poly}(n)$ when given a $2^n \times 2^n$ matrix $A$. An important subclass of sparse matrices are local Hamiltonians.

**Definition 2.6 (k-local Hamiltonian).** A $k$-local Hamiltonian is a Hermitian matrix

$$H = \sum_{i=1}^{m} H_i \in \mathbb{C}^{2^n \times 2^n},$$

where each $H_i$ acts non-trivially on at most $k$ qubits and where $m = \text{poly}(n)$.

Observe that each $H_i$ is $2^k$ sparse, so if $k = O(\log n)$, then each $H_i$ as well as $H$ are $\text{poly}(n)$ sparse.

**Definition 2.7 (Block-encoding).** Suppose that $A$ is an $s$ qubit operator, $\alpha, \varepsilon > 0$ and $a \in \mathbb{N}$. We say that an $(s + a)$ qubit unitary $U$ is an $(\alpha, a, \varepsilon)$-block encoding of $A$, if

$$\|A - \alpha(\langle 0 | \otimes^a \otimes I)U(|0\rangle \otimes^a \otimes I)\| \le \varepsilon.$$

When we say we are given a block-encoding of $A$, we mean a classical description of a quantum circuit that implements such a unitary.

We will usually write $H$ for a local Hamiltonian and $A$ for a sparse or block-encoded matrix.

# 3 A simple classical algorithm for spectral sums

In this section we present classical algorithms to approximate spectral sums of the form $\frac{1}{2^n} \text{tr}[f(A)]$, where we have sparse-access to a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ and where $f$ is a scalar function that admits a uniform polynomial approximation on the spectrum $A$. The basic idea is to approximate $f$ by a low-degree polynomial $p$ and then estimate $\frac{1}{2^n} \text{tr}[p(A)]$ by randomly sampling diagonal entries of $p(A)$.

We first describe the primitive using truncated Taylor expansions. In the second subsection, we improve the approach via Chebyshev approximations of monomials. In the final subsection, we give a specialized algorithm for the important case where the input is a $k$-local Hamiltonian.

## 3.1 Baby version of our algorithm

We begin with the basic trace-estimation primitive, which crucially runs in time independent of the dimension of the input matrix.

**Lemma 3.1 (Trace estimation).** Given query-access to a matrix $A \in \mathbb{C}^{2^n \times 2^n}$ in time $Q_A$ which satisfies $\|A\| \le 1$, there is a classical algorithm running in time $O(Q_A \log(1/\delta)/\varepsilon^2)$ which outputs with probability at least $1 - \delta$ an $\varepsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[A] = \frac{1}{2^n} \sum_{i=1}^{2^n} \lambda_i(A)$.

*Proof.* Let $X$ be the random variable which is obtained by uniformly sampling an index $i \in \mathbb{R}[2^n]$ and returning the corresponding diagonal element $A(i, i)$. We find that this yields an unbiased estimator for the normalized trace of $A$:

$$\mathbb{E}[X] = \sum_{i=1}^{2^n} \frac{1}{2^n} A(i, i) = \frac{1}{2^n} \text{tr}[A].$$
Further, $X$ is real as $A$ is hermitian and we can bound $-1 \le X \le 1$ since by assumption $|A(i, i)| \le \|A\| \le 1$ for all $i \in [2^n]$. As such, we can take $T = O(\log(1/\delta)/\epsilon^2)$ independent samples of $X$ and output their mean $\bar{X}$ which gives the desired approximation quality via Hoeffding's inequality:

$$ \Pr[|\bar{X} - \mu| \ge \epsilon] \le \exp\left(\frac{-2T\epsilon^2}{4}\right) \le \delta. $$

The statement then follows since each sample of $X$ can be computed in time $Q_A$. $\square$

To estimate $\frac{1}{2^n} \text{tr}[f(A)]$, we approximate $f$ by a polynomial $p$ and apply Lemma 3.1 to $p(A)$. Given sparse access to $A$, the only remaining ingredient is the ability to query entries of $p(A)$, which reduces to computing entries of powers $A^k$. One immediate way to compute the powers of sparse matrices exactly is a deterministic recursive procedure as suggested in [GLG23]. To compute entries of the $d$-th power this method takes time $O^*(s^d)$. We follow this approach here because of its simplicity. Another way would be to use the probabilistic path integral Monte Carlo method as in [AGSS23]. This would yield a time complexity of $O^*(\|A\|_1^{2d})$ to compute a $1/\text{poly}(n)$-additive approximation of the entries of $A^d$ where $\|A\|_1 = \max_j \sum_{i=1}^{2^n} |A(i, j)|$ denotes the $\ell_1$-norm of $A$ and where it should be noted that $\|A\|_1^2 \le s$. In some applications, as e.g. in [AGSS23], this inequality is strict and their approach yields a substantial improvement.

**Lemma 3.2 (Iterated sparse matrix multiplication).** Given sparse-access to $s$ sparse matrices $A_1, \dots, A_d \in \mathbb{C}^{2^n \times 2^n}$, and two indices $i, j \in [2^n]$, there is a classical (deterministic) algorithm running in time $O^*(s^d)$ which outputs $(A_1 \cdots A_d)(i, j)$.

*Proof.* The algorithm recursively computes $(A_1 \cdots A_d)(i, j)$ by adding up all of the products of the non-zero entries in the $j$-th column $A_d(k, j)$ with the corresponding entries $(A_1 \cdots A_{d-1})(i, k)$. Let $I_{d,j} \subseteq [2^n]$ denote the subset of all non-zeros indices in column $j$ of $A_d$. Then the correctness of the described approach directly follows from

$$ (A_1 \cdots A_d)(i, j) = \sum_{k \in I_{d,j}} (A_1 \cdots A_{d-1})(i, k) A_d(k, j). $$

The time complexity of this procedure is determined by the recurrence

$$ \mathcal{T}(d) \le s \cdot \mathcal{T}(d-1) + O^*(s) $$

since by assumption the number of non-zero entries per row is bounded by $s$. The recurrence solves as $\mathcal{T}(d) = O^*(s^d)$. $\square$

In the case where all matrices $A_i$ are equal, we obtain the following corollary:

**Corollary 3.3 (Sparse matrix powering).** Given sparse-access to an $s$ sparse matrix $A \in \mathbb{C}^{2^n \times 2^n}$, a power $d \in \mathbb{N}$ and two indices $i, j \in [2^n]$, there is a classical (deterministic) algorithm running in time $O^*(s^d)$ which outputs $A^d(i, j)$.

With Corollary 3.3, we can implement query access to $p(A) = \sum_{k=0}^d c_k A^k$ at cost $O^*(s^d)$ per queried entry. Sampling diagonal entries then gives the following.

**Theorem 3.4.** Given sparse-access to an $s$ sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ satisfying $\|A\| \le 1$, and a degree $d$ polynomial $p(x) = \sum_{k=0}^d c_k x^k$ so that $|p(x)| \le 1$ for all $x \in [-1, 1]$, there is a classical algorithm running in time $O^*(s^d/\epsilon^2)$ which outputs with probability at least $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[p(A)]$.

*Proof.* Using Corollary 3.3, we can efficiently implement query-access to $p(A)$: Given entries $i, j \in [2^n]$, we compute each power $A^k(i, j)$ for $k \in \{0, \dots, d\}$ and multiply with the corresponding coefficients $c_k$ to obtain

$$ p(A)(i, j) = \sum_{k=0}^{d} c_k A^k(i, j). $$
Since each power $A^k(i, j)$ can be approximated in time $O^*(s^k)$, the total runtime to implement query-access to $p(A)$ is $O^*(\sum_{k=0}^d s^k) = O^*(d \cdot s^d) = O^*(s^d)$. We then invoke Lemma 3.1 to estimate $\frac{1}{2^n} \text{tr}[p(A)]$ with query-access cost $Q_{p(A)} = O^*(s^d)$, accuracy $\epsilon$ and failure probability $\delta = 2^{-\text{poly}(n)}$ in time $O^*(s^d \log(1/\delta)/\epsilon^2) = O^*(s^d/\epsilon^2)$. $\square$

The above theorem is the main technical part of our algorithm and it extends to any $f$ that admits a uniform polynomial approximation on the spectrum of $A$.

**Corollary 3.5.** Let $I, J \subseteq [-1, 1]$ be intervals and let $f: I \to J$ be $\epsilon$-approximable by a degree $d$ polynomial $p$ such that $|p(x)| \le 1$ for all $x \in I$, i.e.

$$|f(x) - p(x)| \le \epsilon \quad \text{for all } x \in I.$$

Then, given sparse-access to an $s$ sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ whose spectrum lies in $I$, there is a classical algorithm running in time $O^*(s^d/\epsilon^2)$ which outputs with probability at least $1 - 2^{-\text{poly}(n)}$ a $(2\epsilon)$-additive approximation of $\frac{1}{2^n} \text{tr}[f(A)]$.

*Proof.* Observe that if $f$ is $\epsilon$-approximated by $p$, then so is $\frac{1}{2^n} \text{tr}[f(A)]$ by $\frac{1}{2^n}[p(A)]$ as can easily be verified via the triangle inequality:

$$\left| \frac{1}{2^n} \text{tr}[f(A)] - \frac{1}{2^n} \text{tr}[p(A)] \right| \le \frac{1}{2^n} \sum_{i=1}^{2^n} |f(\lambda_i) - p(\lambda_i)| \le \frac{1}{2^n} \cdot 2^n \epsilon = \epsilon.$$

Thus, we can apply Theorem 3.4 to get an $\epsilon$-approximation of $\frac{1}{2^n} \text{tr}[p(A)]$ which suffices as a $2\epsilon$-approximation of $\frac{1}{2^n} \text{tr}[f(A)]$. $\square$

We want to apply the above theorem for some important spectral sums: The log-determinant, the trace of the inverse and the partition function. For this, let us first collect polynomial approximations for these functions.

**Lemma 3.6 (Polynomial approximations via truncated Taylor expansion).** The following holds true:

1. For degree $d = O(\kappa \log \frac{1}{\epsilon})$, the polynomial $p_d^{(1)}(x) := -\sum_{k=1}^d (1-x)^k/k$ is $\epsilon$-close to $\log(x)$ for all $x \in [\frac{1}{\kappa}, 1]$, and

2. for degree $d = O(\kappa \log \frac{\kappa}{\epsilon})$, the polynomial $p_d^{(2)}(x) := \sum_{k=0}^d (1-x)^k$ is $\epsilon$-close to $1/x$ for all $x \in [\frac{1}{\kappa}, 1]$.

3. Let $\beta > 0$. For degree $d = O(\beta + \log \frac{1}{\epsilon})$, the polynomial $p_d^{(3)}(x) := \sum_{k=0}^d (-\beta x)^k/k!$ is $\epsilon$-close to $e^{-\beta x}$ for all $x \in [-1, 1]$.

The proofs of the above statement are standard and we defer them to the appendix to maintain the flow of exposition. They allow us to immediately obtain algorithms to estimate the corresponding normalized spectral sums summarized in the following corollary.

**Corollary 3.7.** Suppose we are given sparse-access to an $s$ sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$.

1. If the spectrum of $A$ satisfies $\frac{1}{\kappa} \le \lambda_{\min}(A) \le \lambda_{\max}(A) \le 1$, then there is a classical algorithm running in time $O^*(s^{c \cdot \kappa \log(1/\epsilon)})$ which outputs with probability $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \log \det(A)$. Here, $c \ge 1$ is a universal constant.

2. If the spectrum of $A$ satisfies $\frac{1}{\kappa} \le \lambda_{\min}(A) \le \lambda_{\max}(A) \le 1$, then there is a classical algorithm running in time $O^*(s^{c' \cdot \kappa \log(\kappa/\epsilon)})$ which outputs with probability $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[A^{-1}]$. Here, $c' \ge 1$ is a universal constant.
3. If $\|A\| \le 1$, then there is a classical algorithm running in time $O^*(s^{c'' \cdot (\beta+\log(1/\epsilon))})$ which outputs with probability $1-2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[e^{-\beta A}] = \frac{1}{2^n} Z(A, \beta)$. Here, $c'' \ge 1$ is a universal constant.

*Proof.* We prove each statement separately.

1. Choose $d = O(\kappa \log \frac{1}{\epsilon})$ so that $p_d^{(1)}(x) = -\sum_{k=1}^d (1-x)^k/k$ from Lemma 3.6 is $\epsilon/2$-close to $\log(x)$ for all $x \in [\frac{1}{\kappa}, 1]$. Further, observe that $|p_d^{(1)}(x)| \le \log \kappa$ for all $x \in [\frac{1}{\kappa}, 1]$. As such, we can apply Corollary 3.5 to approximate with accuracy $\epsilon' = \frac{\epsilon}{\log \kappa}$, $\frac{1}{2^n \cdot \log \kappa}$ $\log \det(A)$ and multiply the result by $\log \kappa$ for an $\epsilon$-approximation of $\frac{1}{2^n} \log \det(A)$. The time to do so is given as

$$O^*(s^d/(\epsilon')^2) = O^*(s^d \cdot \log^2 \kappa/\epsilon^2) = O^*(s^{c' \cdot \kappa \log(1/\epsilon)})$$

for some constant $c \ge 1$.

2. Choose $d = O(\kappa \log \frac{\kappa}{\epsilon})$ so that $p_d^{(2)}(x) = \sum_{k=1}^d (1-x)^k$ from Lemma 3.6 is $\epsilon/2$-close to $1/x$ for all $x \in [\frac{1}{\kappa}, 1]$. Further, observe that $|p_d^{(2)}(x)| \le \kappa$ for all $x \in [\frac{1}{\kappa}, 1]$. As such, we can apply Corollary 3.5 to $\epsilon' = \frac{\epsilon}{\kappa}$ approximate $\frac{1}{2^n} \text{tr}[\frac{1}{\kappa}A^{-1}]$ and multiply the result by $\kappa$ for an $\epsilon$-approximation of $\frac{1}{2^n} \text{tr}[A^{-1}]$. The time to do so is given as

$$O^*(s^d/(\epsilon')^2) = O^*(s^d \cdot \kappa^2/\epsilon^2) = O^*(s^{c' \cdot \kappa \log(\kappa/\epsilon)})$$

for some constant $c' \ge 1$.

3. Choose $d = O(\beta + \log \frac{1}{\epsilon})$ so that $p_d^{(3)}(x) = \sum_{k=1}^d (-\beta x)^k/k!$ from Lemma 3.6 is $\epsilon/2$-close to $1/x$ for all $x \in [-1, 1]$. Further, observe that $|p_d^{(3)}(x)| \le e^\beta$ for all $x \in [-1, 1]$. As such, we can apply Corollary 3.5 to $\epsilon' = \frac{\epsilon}{e^\beta}$-approximate $\frac{1}{2^n} \text{tr}[\frac{1}{e^\beta}e^{-\beta A}]$ and multiply the result by $e^\beta$ for an $\epsilon$-approximation of $\frac{1}{2^n} \text{tr}[e^{-\beta A}] = \frac{1}{2^n} Z(A, \beta)$. The time to do so is given as

$$O^*(s^d/(\epsilon')^2) = O^*(s^d \cdot e^{2\beta}/\epsilon^2) = O^*(s^{c'' \cdot (\beta+\log(1/\epsilon))})$$

for some constant $c'' \ge 1$.

□

## 3.2 Speeding up our algorithm via Chebyshev approximation

The Taylor-based approach of Section 3.1 can be further improved by exploiting Chebyshev approximations of monomials. Instead of computing $A^d$ exactly, we approximate the monomial $x^d$ by a much lower-degree polynomial and only compute the smaller powers appearing therein. The following lemma, due to [SV14] (see also [AGSS23]), guarantees the existence of such approximations.

**Lemma 3.8** (Chebyshev approximation of monomials, compare Theorem 3.3 in [SV14]). Let $\epsilon > 0$ and $d \in \mathbb{N}$. Then the monomial $x^d$ can be approximated by a polynomial $p_{d',d}(x)$ of degree $d' = \lceil \sqrt{2d \log(2/\epsilon)} \rceil$ such that

$$|x^d - p_{d',d}(x)| \le \epsilon \quad \text{for all } x \in [-1, 1].$$

Moreover, the monomial coefficients of $p_{d',d}$ can be computed efficiently.

This lemma directly carries over to improve the necessary degree to approximate any polynomial with bounded coefficients by replacing every appearing monomial by its Chebyshev approximation. We remark that this need not always yield the optimal degree polynomial approximation but it will be sufficient in our cases.
**Corollary 3.9.** Let $p_d(x) = \sum_{k=0}^{d} c_k x^k$ be a polynomial of degree $d$ with coefficients $|c_k| \le 1$. Then, there exists an efficiently computable polynomial $p_d'(x)$ of degree $d' = \lceil \sqrt{2d \log(2d/\varepsilon)} \rceil$ approximating $p_d(x)$ such that

$$|p_d(x) - p_{d'}(x)| \le \varepsilon \quad \text{for all } x \in [-1, 1].$$

*Proof.* By Lemma 3.8, for each monomial $x^k$ with $1 \le k \le d$, there exists a polynomial $p_{k',k}(x)$ of degree at most $d' = \lceil \sqrt{2d \log(2d/\varepsilon)} \rceil$ such that

$$|x^k - p_{k',k}(x)| \le \varepsilon/d \quad \text{for all } x \in [-1, 1].$$

Now define

$$p_{d'}(x) := c_0 + \sum_{k=1}^{d} c_k p_{k',k}(x).$$

This polynomial has degree at most $d' = \lceil \sqrt{2d \log(2d/\varepsilon)} \rceil$ by construction and for any $x \in [-1, 1]$, the approximation error satisfies

$$|p_d(x) - p_{d'}(x)| = \left| \sum_{k=1}^{d} c_k (x^k - p_{k',k}(x)) \right| \le \sum_{k=1}^{d} |c_k| \cdot |x^k - p_{k',k}(x)| \le \sum_{k=1}^{d} \varepsilon/d = \varepsilon.$$

Moreover, since each $p_{k',k}$ can be computed efficiently, the whole construction is efficient. $\square$

We can now revisit the Taylor-based polynomial approximations of Lemma 3.6. Replacing monomials by their Chebyshev approximations reduces the required degree from $O(\kappa \log(1/\varepsilon))$, respectively $O(\kappa \log(\kappa/\varepsilon))$, to $O(\sqrt{\kappa} \log(\kappa/\varepsilon))$ for the logarithm and the inverse function. For the exponential function $e^{-\beta x}$, however, this method does not improve the degree, as the large Taylor coefficients would amplify the approximation error of the monomial approximations.

**Lemma 3.10.** (Improved polynomial approximations) The following holds true:

1. There exists a degree $d' = O(\sqrt{\kappa} \log \frac{\kappa}{\varepsilon})$ polynomial which is $\varepsilon$-close to $\log(x)$ for all $x \in [\frac{1}{\kappa}, 1]$, and

2. there exists a degree $d' = O(\sqrt{\kappa} \log \frac{\kappa}{\varepsilon})$ polynomial which is $\varepsilon$-close to $1/x$ for all $x \in [\frac{1}{\kappa}, 1]$.

Moreover, these polynomials are efficiently computable.

*Proof.* 1. Take $p_d^{(1)}(x) = -\sum_{k=1}^{d} (1-x)^k/k$ $(\varepsilon/2)$-approximating $\log(x)$ as in Lemma 3.6. Substitute $z = (1-x)$ so that $p_d^{(1)}(z) = -\sum_{k=1}^{d} z^k/k$. We then infer Corollary 3.9 to $(\varepsilon/2)$-approximate $p_d^{(1)}(z)$ on $[-1, 1]$ by a polynomial $p_{d'}^{(1)}(z)$ of degree

$$d' = O\left(\sqrt{d \log \frac{d}{\varepsilon}}\right) = O\left(\sqrt{\kappa \log\left(\frac{1}{\varepsilon}\right) \cdot \log\left(\frac{\kappa \log\left(\frac{1}{\varepsilon}\right)}{\varepsilon}\right)}\right) = O\left(\sqrt{\kappa} \cdot \log\left(\frac{\kappa}{\varepsilon}\right)\right).$$

In particular $p_{d'}^{(1)}(x)$ is $(\varepsilon/2)$-close to $p_d^{(1)}(x)$ on $[\frac{1}{\kappa}, 1]$ and as such $\varepsilon$-close to $\log(x)$.

2. The same argument applies to $p_d^{(2)}(x) = \sum_{k=0}^{d} (1-x)^k$, which $(\varepsilon/2)$-approximates $1/x$ for $d = O(\kappa \log(\kappa/\varepsilon))$. Again Corollary 3.9 yields a polynomial approximation of degree

$$d' = O\left(\sqrt{\kappa \log\left(\frac{\kappa}{\varepsilon}\right) \cdot \log\left(\frac{\kappa \log\left(\frac{\kappa}{\varepsilon}\right)}{\varepsilon}\right)}\right) = O\left(\sqrt{\kappa} \cdot \log\left(\frac{\kappa}{\varepsilon}\right)\right). \quad \square$$

These improved polynomial approximations translate directly into faster algorithms for spectral sum estimation.
**Corollary 3.11.** Suppose we are given sparse-access to an s sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$.

1. If the spectrum of A satisfies $\frac{1}{\kappa} \le \lambda_{\min}(A) \le \lambda_{\max}(A) \le 1$, then there is a classical algorithm running in time $O^*(s^{c' \cdot \sqrt{\kappa \log(\kappa/\epsilon)}})$ which outputs with probability $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \log \det(A)$. Here, $c \ge 1$ is a universal constant.

2. If the spectrum of A satisfies $\frac{1}{\kappa} \le \lambda_{\min}(A) \le \lambda_{\max}(A) \le 1$, then there is a classical algorithm running in time $O^*(s^{c' \cdot \sqrt{\kappa \log(\kappa/\epsilon)}})$ which outputs with probability $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[A^{-1}]$. Here, $c' \ge 1$ is a universal constant.

3. If $\|A\| \le 1$, then there is a classical algorithm running in time $O^*(s^{c'' \cdot \sqrt{p \log(1/\epsilon)}})$ which outputs with probability $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[A^p]$. Here, $c'' \ge 1$ is a universal constant.

The proof is identical to that of Corollary 3.7, with the degree bounds replaced by those from Lemmas 3.8 and 3.10.

## 3.3 A specialized algorithm for k-local Hamiltonians

Recall that a k-local Hamiltonian is a positive semi-definite matrix

$$H = \sum_{i=1}^{m} H_i \in \mathbb{C}^{2^n \times 2^n}$$

where each $H_i$ acts non-trivially on at most k qubits and where $m = \text{poly}(n)$. We will further make the additional standard assumption that $\sum_{i=1}^m \|H_i\| \le 1$ and that we know bounds $\|H_i\| \le \kappa_i$ for all $i \in [m]$ such that $\sum_{i=1}^m \kappa_i = 1$.

For such matrices, we show that we can improve the time complexity of our algorithm for estimating the spectral sum of a degree d polynomial $\frac{1}{2^n} \text{tr}[p(A)] \pm \epsilon$ from $O^*(s^d/\epsilon^2)$ of the previous section to $O^*(2^{kd}/\epsilon^2)$. This can be a substantial improvement because, while each $H_i$ of a k-local Hamiltonian is $2^k$ sparse, the total Hamiltonian itself consists of $m = \text{poly}(n)$ many such terms. As such, the Hamiltonian might contain $\text{poly}(n)$ many non-zero entries in a row and in a column already in the case where $k = O(1)$. Our spectral sum estimation algorithm builds on an efficient matrix powering algorithm for k-local Hamiltonians by Le Gall [Le 25].

**Theorem 3.12 (k-local spectral sum estimation).** Let $H = \sum_{i=1}^m H_i \in \mathbb{C}^{2^n \times 2^n}$ be a k-local Hamiltonian such that each $\|H_i\| \le \kappa_i$ and $\sum_i \kappa_i = 1$. Further, let $p(x) = \sum_{l=0}^d c_l x^l$ be a degree d polynomial with $|c_l| \le 1$. Then, there is a classical algorithm running in time $O^*(2^{kd}/\epsilon^2)$ that outputs with probability at least $1 - 2^{-\text{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \text{tr}[p(H)]$.

*Proof.* Let us start by presenting an unbiased estimator $X_i^{(l)}$ for the i-th diagonal element of the l-th power of H, $H^l(i, i)$. For $l = 0$ set $X_i^{(0)} := 1$ deterministically and for $l \in [d]$, define a product distribution $q : [m]^l \to [0, 1]$ by

$$q(x_1, \dots, x_l) := \kappa_{x_1} \cdots \kappa_{x_l},$$

sample $x = (x_1, \dots, x_l) \sim q$, and compute

$$X_i^{(l)} := \frac{(H_{x_1} \cdots H_{x_l})(i, i)}{q(x)}.$$

Because each $H_{x_t}$ is $2^k$ sparse, $(H_{x_1} \cdots H_{x_l})(i, i)$ can be computed in time $O^*(2^{kl})$ by Lemma 3.2. We compute for the expectation of $X_i^{(l)}$:

$$\mathbb{E}[X_i^{(l)}] = \sum_{x \in [m]^l} q(x) \frac{(H_{x_1} \cdots H_{x_l})(i, i)}{q(x)} = \sum_{x \in [m]^l} (H_{x_1} \cdots H_{x_l})(i, i) = H^l(i, i).$$
Moreover, for any $i \in [2^n]$:

$$|(H_{x_1} \cdots H_{x_l})(i, i)| \le \|H_{x_1} \cdots H_{x_l}\| \le \kappa_{x_1} \cdots \kappa_{x_l} = q(x),$$

so $|X_i^{(l)}| \le 1$. Further, since $H^l$ is Hermitian, $H^l(i, i) \in \mathbb{R}$. Therefore $\mathbb{E}[\Re[X_i^{(l)}]] = H^l(i, i)$ and it suffices to work with the real estimator $\Re[X_i^{(l)}] \in [-1, 1]$.

This estimator easily extends to one for the diagonal elements $p(H)(i, i)$. For fixed $i$, define

$$X_i := \sum_{l=0}^{d} c_l \Re[X_i^{(l)}].$$

Further, we can bound its absolute value

$$|X_i| \le \sum_{l=0}^{d} |c_l| |\Re[X_i^{(l)}]| \le d + 1.$$

We can now use this to get an estimator for the normalized trace of $p(H)$. Choose $i \in_R [2^n]$ uniformly at random and output $X_i$. Then

$$\mathbb{E}_i[X_i] = \sum_{i=1}^{2^n} \frac{1}{2^n} p(H)(i, i) = \frac{1}{2^n} \mathrm{tr}[p(H)] =: \mu,$$

and the output will always be bounded by $d+1$ in absolute value. We thus obtain for the mean $\bar{X}$ of $T = O((d+1)^2 \log(1/\delta)/\epsilon^2)$ independent samples of this estimator via Hoeffding's inequality:

$$\mathrm{Pr}[|\bar{X} - \mu| \ge \epsilon] \le \exp\left(\frac{-2T\epsilon^2}{(d+1)^2}\right) \le \delta.$$

Since producing one sample of $X_i$ requires generating $\Re[X_i^{(l)}]$ for all $l = 0, \dots, d$, the cost to do so is $\sum_{l=0}^d O^*(2^{kl}) = O^*(2^{kd})$. Hence the overall runtime is

$$O^*(2^{kd} \cdot (d+1)^2 \log(1/\delta)/\epsilon^2) = O^*(2^{kd}/\epsilon^2),$$

where we have chosen $\delta = 2^{-\mathrm{poly}(n)}$. $\square$

**Corollary 3.13.** Suppose we are given a $k$-local Hamiltonian $H = \sum_{i=1}^m H_i \in \mathbb{C}^{2^n \times 2^n}$ such that each $H_i$ is positive semidefinite with $\|H_i\| \le \kappa_i$ and $\sum_i \kappa_i = 1$.

1. If the spectrum of $H$ satisfies $\frac{1}{\kappa} \le \lambda_{\min}(H) \le \lambda_{\max}(H) \le 1$, then there is a classical algorithm running in time $O^*(2^{c \cdot k \kappa \log(1/\epsilon)})$ which outputs with probability $1 - 2^{-\mathrm{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \log \det(H)$. Here, $c \ge 1$ is a universal constant.

2. If the spectrum of $H$ satisfies $\frac{1}{\kappa} \le \lambda_{\min}(H) \le \lambda_{\max}(H) \le 1$, then there is a classical algorithm running in time $O^*(2^{c' \cdot k \kappa \log(\kappa/\epsilon)})$ which outputs with probability $1 - 2^{-\mathrm{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \mathrm{tr}[H^{-1}]$. Here, $c' \ge 1$ is a universal constant.

3. There is a classical algorithm running in time $O^*(2^{c'' \cdot k \beta \log(1/\epsilon)})$ which outputs with probability $1 - 2^{-\mathrm{poly}(n)}$ an $\epsilon$-additive approximation of $\frac{1}{2^n} \mathrm{tr}[e^{-\beta A}] = \frac{1}{2^n} Z(A, \beta)$. Here, $c'' \ge 1$ is a universal constant.

*Proof.* Let us start proving the first claim. For this, take the polynomial

$$p_d^{(1)}(x) = - \sum_{k=1}^{d} (1-x)^k / k$$
of degree $d = O(\kappa \log(1/\epsilon))$ from Lemma 3.6 that $(\epsilon/2)$-approximates $\log(x)$ on $[\frac{1}{\kappa}, 1]$. Further, observe that

$$ \hat{H} := I - H = \sum_{i=1}^{m} (\kappa_i I - H_i) $$

is also a k-local Hamiltonian where $\|\kappa_i I - H_i\| \le \kappa_i$ for each $i \in [m]$. As such, we can get an $(\epsilon/2)$-approximation of $\frac{1}{2^n} \text{tr}[p(H)] = \frac{1}{2^n} \text{tr}[q(\hat{H})]$ by applying Theorem 3.12 with the polynomial $q_d^{(1)}(x) = -\sum_{k=1}^d x^k/k$. This approximation is then again $\epsilon/2$ close to the desired normalized log-determinant. An analogous argument works for the second claim. For the third and last claim consider the polynomial $p_d^{(3)}(x) = \sum_{k=0}^d \frac{(-\beta x)^k}{x^k}$ from Lemma 3.6 again for degree $d = O(\beta + \log(1/\epsilon'))$. If we choose $\epsilon' = \epsilon/(2e^\beta)$, then $p_d^{(3)}(x)$ is $\epsilon/(2e^\beta)$ close to $e^{-\beta x}$. Observe that the coefficients of $p_d^{(3)}(x)$ are bounded by $e^\beta$. We thus invoke Theorem 3.12 to get an $\epsilon'$ approximation of $\frac{1}{2^n} \text{tr}[\frac{1}{e^\beta} p_d^{(3)}(H)]$ in time

$$ O^*(\beta + \log(\frac{1}{\epsilon})) = O^*(\beta + \log(\frac{e^\beta}{\epsilon})) = O^*(\beta \log(1/\epsilon)). $$

Multiplying this estimate by $e^\beta$ gives an $\epsilon/2$ estimate of $\frac{1}{2^n} \text{tr}[p_d^{(3)}(H)]$ which is itself $\epsilon/2$ close to the desired normalized partition function. $\square$

# 4 DQC1-completeness of estimating several spectral sums

## 4.1 DQC1-containment for log-local Hamiltonians

We first cite the following result from Cade and Montanaro [CM18].

**Lemma 4.1 (Lemma 1 in [CM18]).** For a log-local Hamiltonian $H \in \mathbb{C}^{2^n \times 2^n}$, and any log-space polynomial-time computable function $f: I \to [-1, 1]$ (where $I$ contains the spectrum of $A$) that is Lipschitz continuous with constant $K$ (i.e. $|f(x) - f(y)| \le K|x - y|$ for all $x, y \in I$), there exists a DQC1 algorithm to estimate $\frac{1}{2^n} \text{tr}[f(A)] = \frac{1}{2^n} \sum_{i=1}^{2^n} f(\lambda_i)$ up to additive accuracy $\epsilon(K+1)$ where $\lambda_j$ denotes the j-th eigenvalue of $A$, and $\epsilon = \Omega(1/\text{poly}(n))$.

Cade and Montanaro use this lemma, together with the observation that $f(x) = x^p$ is Lipschitz continuous with constant $p$ on $[-1, 1]$, to prove that estimating the $\text{tr}[A^p]$ up to additive error $1/\text{poly}(n)$ is contained in DQC1 when $\|A\| \le 1$ and $p = \text{poly}(n)$. Similarly, one can find that the logarithm $\log(x)$ is Lipschitz continuous on $[\frac{1}{\kappa}, 1]$ with constant $\kappa$, the inverse function $1/x$ is Lipschitz continuous on $[\frac{1}{\kappa}, 1]$ with constant $\kappa^2$ and $e^{-\beta x}$ is Lipschitz continuous on $[0, 1]$ with constant $\beta$. Furthermore, all of these functions can be computed in log-space (up to inverse exponential precision) and as such we directly obtain:

**Corollary 4.2.** Suppose we are given a log-local Hamiltonian $H \in \mathbb{C}^{2^n \times 2^n}$. Then, the following quantities can be estimated up to $1/\text{poly}(n)$ additive accuracy in DQC1:

1. the normalized log-determinant $\frac{1}{2^n} \log \det(H)$ if $1/\text{poly}(n) \le \lambda_{\min}(H) \le \lambda_{\max}(H) \le 1$,

2. the normalized trace of the inverse $\frac{1}{2^n} \text{tr}[H^{-1}]$ if $1/\text{poly}(n) \le \lambda_{\min}(H) \le \lambda_{\max}(H) \le 1$,

3. the normalized partition function $\frac{1}{2^n} Z(H, \beta)$ if $0 \le \lambda_{\min}(H) \le \lambda_{\max}(H) \le 1$ and $\beta = \text{poly}(n)$.

## 4.2 DQC1-hardness for log-local Hamiltonians

### 4.2.1 Brandão's DQC1-circuit to Hamiltonian construction

Brandão [Bra08] considered the following DQC1 circuit-to-Hamiltonian construction inspired by the standard BQP circuit-to-Hamiltonian construction by Kitaev [KSV02].
Given a DQC1-circuit $Q = U_T \cdot \dots \cdot U_1$, the Hamiltonian $H_{DQC1}$ acting on $N = n + \log(T)$ qubits is defined as follows. Let us denote by $\Pi_1$ a projector onto the first qubit, and by $\Pi_{\text{clock}}$ a projector onto the clock register.

$$H_{\text{DQC1}} := H_{\text{out}} + J_{\text{in}}H_{\text{in}} + J_{\text{prop}}H_{\text{prop}},$$

$$\text{where } H_{\text{out}} := (T+1) |0\rangle \langle 0|_1 \otimes I \otimes |T\rangle \langle T|_{\text{clock}},$$

$$H_{\text{in}} := |1\rangle \langle 1|_1 \otimes I \otimes |0\rangle \langle 0|_{\text{clock}},$$

$$H_{\text{prop}} := \sum_{t=1}^{T} H_{\text{prop},t},$$

$$\text{with } H_{\text{prop},t} := I \otimes |t-1\rangle \langle t-1| + I \otimes |t\rangle \langle t| - U_t \otimes |t\rangle \langle t-1| - U_t^\dagger \otimes |t-1\rangle \langle t|.$$

Brandão showed that the low lying spectrum of $H_{DQC1}$ approximates the rejection probability $\mu_{\text{reject}}$ of the underlying circuit. Formally he proved:

**Theorem 4.3 ([Bra08]).** For any $T, \Delta, \varepsilon^{-1} \ge 1$, there exist $J_{\text{in}}, J_{\text{prop}} = \text{poly}(T\Delta/\varepsilon)$ such that

$$\left| \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i(H_{\text{DQC1}}) - \mu_{\text{reject}} \right| \le \varepsilon$$

as well as

$$\lambda_{2^{n-1}}(H_{\text{DQC1}}) \le \delta = O(1) \quad \text{and} \quad \Delta \le \lambda_{2^{n-1}+1}(H_{\text{DQC1}}).$$

Using the above Hamiltonian, Brandão showed that estimating the partition function with additive error $\frac{1}{\text{poly}(n)}$ is DQC1-hard. The proof exploits that the decay of $e^{-\beta x}$ is very fast in $x \to \infty$ so that the average eigenvalue of $e^{-\beta H}$ is dominated by the contribution of the first $2^{n-1}$ eigenvalues which are the relevant ones to estimate $\mu_{\text{reject}}$. See Theorem 7.2.4 in [Bra08] and the following figure.

<figure><img src="image_2.png" /><figcaption>Figure 1: The spectrum of $H_{DQC1}$ versus the function $e^{-\beta x}$. The smallest $2^{n-1}$ eigenvalues of $H_{DQC1}$ are located in the green part. The larger eigenvalues are located in the red part.</figcaption></figure>

**Fact 4.1.** Given a log-local Hamiltonian $H \in \mathbb{C}^{2^n \times 2^n}$ satisfying $\|H\| \le \text{poly}(n)$, there exists $\beta = \text{poly}(n)$ such that estimating $\frac{1}{2^n}Z(H, \beta)$ with additive error $1/\text{poly}(n)$ is DQC1-hard.
<figure><img src="image_3.png" /><figcaption>Figure 2: The spectrum of $\hat{H} = \frac{1}{\kappa}I + \beta H_{DQC1}$ versus the function $1/x$. The smallest $2^{n-1}$ eigenvalues of $\hat{H}$ are located in the green part. The larger eigenvalues are located in the red part.</figcaption></figure>

### 4.2.2 Estimating $\frac{1}{2^n} \text{tr}[H^{-1}] \pm 1/\text{poly}(n)$ is DQC1-hard

**Theorem 4.4.** Given a log-local Hamiltonian $H \in \mathbb{C}^{2^n \times 2^n}$ satisfying $1/\text{poly}(n) \le \lambda_{\min}(H) \le \lambda_{\max}(H) \le 1$, estimating $\frac{1}{2^n} \text{tr}[H^{-1}]$ up to additive error $1/\text{poly}(n)$ is DQC1-hard.

*Proof.* Let $Q = U_T \cdots U_1 \in \mathbb{C}^{2^n \times 2^n}$ correspond to some DQC1-circuit with $T = \text{poly}(n)$ gates of which we wish to decide whether $\mu_{\text{accept}}(Q) \ge b$ or $\le a$ for some $b-a \ge 1/\text{poly}(n)$. We set $\varepsilon := \frac{1}{3}(b-a)/(3+\delta^2/2)$ and consider $H_{DQC1}$, the resulting Hamiltonian from Brandão's construction with parameters $J_{\text{in}}$, $J_{\text{prop}} = \text{poly}(T\Delta/\varepsilon) = \text{poly}(n)$ such that

$$ \left| \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i(H_{\text{DQC1}}) - \mu_{\text{reject}} \right| \le \varepsilon $$

and

$$ \lambda_{2^{n-1}}(H_{\text{DQC1}}) \le \delta < \Delta \le \lambda_{2^{n-1}+1}(H_{\text{DQC1}}), $$

where $\delta = O(1)$ and $\Delta = \frac{2T}{\varepsilon^3} = \text{poly}(n)$. Observe that $H_{\text{DQC1}}$ need not be well-conditioned, nor does it have a spectrum bounded by 1. We instead consider $\hat{H} := \frac{1}{\kappa}I + \beta H_{\text{DQC1}}$ for

$$ \kappa = T + 1 + J_{\text{in}} + 4J_{\text{prop}} = \text{poly}(n) \quad \text{and} \quad \beta = \frac{\varepsilon}{\kappa} = \frac{1}{\text{poly}(n)}. $$

Notice that $\kappa$ is an upper bound for $\|H_{\text{DQC1}}\|$. These parameter choices will turn out useful later. For better readability, we write $\lambda_i$ for the eigenvalues of $H_{\text{DQC1}}$ and $\hat{\lambda}_i$ for the eigenvalues of $\hat{H}$. The spectrum of this new matrix $\hat{H}$ now satisfies

$$ \frac{1}{\kappa} \le \hat{\lambda}_1 \le \dots \le \hat{\lambda}_{2^{n-1}} \le \hat{\delta} < \hat{\Delta} \le \hat{\lambda}_{2^{n-1}+1} \le \dots \le \hat{\lambda}_{2^{n+\log T}} \le 1 $$

for $\hat{\delta} = \frac{1}{\kappa} + \beta\delta$ and $\hat{\Delta} = \frac{1}{\kappa} + \beta\Delta$.

Let us now assume that we can approximate the normalized trace $\frac{1}{2^{n+\log T}} \text{tr}[\hat{H}^{-1}]$ with additive accuracy $\frac{\varepsilon}{2T} = 1/\text{poly}(n)$, i.e. we get an estimate $z$ such that

$$ \left| z - \frac{1}{2^{n+\log T}} \sum_{i=1}^{2^{n+\log T}} \frac{1}{\lambda_i(\hat{H})} \right| \le \frac{\varepsilon}{2T}. $$
Multiplying this estimate by $2^{\log T+1} = 2T$ and taking out the contribution from the large eigenvalues on the left side yields:

$$ \left| 2T \cdot z - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \frac{1}{\lambda_i(\hat{H})} \right| \le \varepsilon + \frac{1}{2^{n-1}} \sum_{i=2^{n-1}+1}^{2^{n+\log T}} \frac{1}{\lambda_i(\hat{H})} \le \varepsilon + \frac{2T}{\beta \Delta}. \quad (1) $$

We want to argue that this estimate allows us to approximate $\mu_{\text{reject}}$. To achieve this, let us first consider the Taylor expansion of $f: [\frac{1}{\kappa}, 1] \to \mathbb{R}$, $f(x) := 1/x$ around $x_0 = 1/\kappa$. We calculate $f'(x) = -\frac{1}{x^2}$ as well as $f''(x) = \frac{2}{x^3}$. By Taylor's theorem (Fact 2.2) we have for all $x \in [\frac{1}{\kappa}, 1]$,

$$ |f(x) - (f(x_0) + f'(x_0) \cdot (x - x_0))| \le \max_{\xi \in [\frac{1}{\kappa}, 1]} \frac{|f''(\xi)|}{2} \cdot (x - x_0)^2, $$

which in our case becomes

$$ \left| \frac{1}{x} - \left(1/\kappa - \kappa^2 \cdot \left(x - 1/\kappa\right)\right) \right| \le \frac{\kappa^3}{2} \cdot \left(x - 1/\kappa\right)^2. $$

We plug this into (1) to obtain

$$ \left| 2T \cdot z - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \left( 1/\kappa - \kappa^2 (\hat{\lambda}_i - 1/\kappa) \right) \right| \le \varepsilon + \frac{2T}{\beta \Delta} + \frac{\kappa^3}{2} \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} |\hat{\lambda}_i - 1/\kappa|^2. $$

Since $\hat{\lambda}_i = \frac{1}{\kappa} + \beta\lambda_i$ and $\lambda_i \le \delta$ for all $i \in [2^{n-1}]$, we can simplify this to

$$ \left| 2T \cdot z - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \left( 1/\kappa - \kappa^2 \beta \lambda_i \right) \right| \le \varepsilon + \frac{2T}{\beta \Delta} + \frac{\kappa^3}{2} \beta^2 \delta^2. $$

Dividing by $\kappa^2\beta$ and rearranging terms yields

$$ \left| \frac{1}{\kappa^2 \beta} \left( 2T \cdot z - 1/\kappa \right) - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i \right| \le \frac{\varepsilon}{\kappa^2 \beta} + \frac{2T}{\kappa^2 \beta^2 \Delta} + \frac{\kappa \beta \delta^2}{2}. $$

Now let $\hat{z} := \frac{1}{\kappa^2 \beta}(2T \cdot z - 1/\kappa)$. Then, plugging in our choices $\beta = \frac{\varepsilon}{\kappa}$, $\Delta = \frac{2T}{\varepsilon^3}$ and observing that implicitly $\kappa \ge \frac{1}{\varepsilon}$, we finally get

$$ \left| \hat{z} - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i \right| \le \frac{\varepsilon}{\kappa^2 \beta} + \frac{2T}{\kappa^2 \beta^2 \Delta} + \frac{\kappa \beta \delta^2}{2} = \frac{1}{\kappa} + \varepsilon + \frac{\varepsilon \delta^2}{2} \le (2 + \delta^2/2)\varepsilon. $$

Since we further know $\frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i$ is $\varepsilon$-close to $\mu_{\text{reject}}$, we can thus $(3 + \delta^2/2)\varepsilon$ approximate $\mu_{\text{reject}}$ by $\hat{z}$ which suffices to distinguish whether $\mu_{\text{reject}} \ge b$ or $\mu_{\text{reject}} \le a$ as we have chosen $\varepsilon = \frac{1}{3}(b-a)/(3+\delta^2/2)$. $\square$

### 4.2.3 Estimating $\frac{1}{2^n} \text{tr}[H^p] \pm 1/\text{poly}(n)$ is DQC1-hard

**Theorem 4.5.** Given a log-local Hamiltonian $H \in \mathbb{C}^{2^n \times 2^n}$ satisfying $\|H\| \le 1$, there exists $p = \text{poly}(n)$ such that estimating $\frac{1}{2^n} \text{tr}[H^p]$ up to additive error $1/\text{poly}(n)$ is DQC1-hard.
<figure><img src="image_4.png" /><figcaption>Figure 3: The spectrum of $\hat{H} = I - \beta H_{DQC1}$ versus the function $x^p$. The largest $2^{n-1}$ eigenvalues of $\hat{H}$ are located in the green part. The smaller eigenvalues are located in the red part.</figcaption></figure>

*Proof.* Consider again $Q = U_T \cdots U_1 \in \mathbb{C}^{2^n \times 2^n}$ corresponding to some DQC1-circuit of which we want to decide $\mu_{accept}(Q) \ge b$ or $\le a$ for some $b-a \ge 1/\text{poly}(n)$. We now slightly defer from the proof of Theorem 4.4 and set $\varepsilon := (\frac{1}{3}(b-a)(2+\delta^2/2))^2$ and consider Brandão's Hamiltonian construction $H_{DQC1}$ with parameters $J_{in}, J_{prop} = \text{poly}(T\Delta/\varepsilon) = \text{poly}(n)$ such that

$$ \left| \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i(H_{DQC1}) - \mu_{reject} \right| \le \sqrt{\varepsilon} $$

and

$$ \lambda_{2^{n-1}}(H_{DQC1}) \le \delta < \Delta \le \lambda_{2^{n-1}+1}(H_{DQC1}), $$

where $\delta = O(1)$ and $\Delta = \frac{1}{\sqrt{\varepsilon}} \log \frac{2T}{\sqrt{\varepsilon}} = \text{poly}(n)$. Furthermore, we choose $p = T+1+J_{in}+4J_{prop}$, which upper bounds $\|H_{DQC1}\|$, and we set $\hat{H} := I - \beta H_{DQC1}$ for $\beta = \frac{\sqrt{\varepsilon}}{p}$. For better readability, we write $\lambda_i$ for the eigenvalues of $H_{DQC1}$. It is easily verified that the spectrum of $\hat{H}$ is contained in $[0, 1]$.

We now assume that we can approximate the normalized trace $\frac{1}{2^{n+\log T}} \text{tr}[\hat{H}^p]$ with additive accuracy $\frac{\sqrt{\varepsilon}}{2T} = 1/\text{poly}(n)$, i.e. we get an estimate $z$ such that

$$ \left| z - \frac{1}{2^{n+\log T}} \sum_{i=1}^{2^{n+\log T}} (1 - \beta \lambda_i)^p \right| \le \frac{\sqrt{\varepsilon}}{2T}. $$

Multiplication by $2^{\log T+1} = 2T$ and taking out the contribution from the large eigenvalues $\lambda_i$ on the left side yields:

$$ \left| 2T \cdot z - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} (1 - \beta \lambda_i)^p \right| \le \sqrt{\varepsilon} + \frac{1}{2^{n-1}} \sum_{i=2^{n-1}+1}^{2^{n+\log T}} (1 - \beta \lambda_i)^p \le \sqrt{\varepsilon} + 2T(1 - \beta \Delta)^p. \quad (2) $$

We again argue that this estimate allows us to approximate $\mu_{reject}$. This time we consider the Taylor expansion of $f: [0, 1] \to \mathbb{R}$, $f(x) := x^p$ around $x_0 = 1$. We calculate $f'(x) = px^{p-1}$ as well as $f''(x) = p(p-1)x^{p-2}$. By Taylor's theorem (Fact 2.2) we find in this case that for all $x \in [0, 1]$,

$$ |x^p - (1 + p \cdot (x - 1))| \le \frac{p^2}{2} \cdot (x - 1)^2. $$
We plug this into (2) to obtain

$$ \left| 2T \cdot z - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} (1 - p\beta\lambda_i) \right| \le \sqrt{\varepsilon} + 2T(1 - \beta\Delta)^p + \frac{p^2}{2} \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} |\beta\lambda_i|^2. $$

Dividing by $p\beta$ and using that $|\lambda_i| \le \delta$ for all $i \in [2^{n-1}]$ yields

$$ \left| \frac{1}{p\beta} (1 - 2T \cdot z) - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i \right| \le \frac{\sqrt{\varepsilon}}{p\beta} + \frac{2T}{p\beta} (1 - \beta\Delta)^p + \frac{p\beta\delta^2}{2}. $$

Now set $\hat{z} := \frac{1}{p\beta}(1 - 2T \cdot z)$ and plug in our choices $\beta = \frac{\sqrt{\varepsilon}}{p}$ as well as $\Delta = \frac{1}{\sqrt{\varepsilon}} \log \frac{2T}{\sqrt{\varepsilon}}$ to obtain

$$ \left| \hat{z} - \frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i \right| \le \frac{\sqrt{\varepsilon}}{p\beta} + \frac{2T}{p\beta} \underbrace{(1 - \beta\Delta)^p}_{\le e^{-\beta\Delta_p}} + \frac{p\beta\delta^2}{2} = \sqrt{\varepsilon} + \sqrt{\varepsilon} + \frac{\sqrt{\varepsilon}\delta^2}{2} \le (2 + \delta^2/2)\sqrt{\varepsilon}. $$

Since further $\frac{1}{2^{n-1}} \sum_{i=1}^{2^{n-1}} \lambda_i$ is $\sqrt{\varepsilon}$-close to $\mu_{\text{reject}}$, we can thus $(3 + \delta^2/2)\sqrt{\varepsilon}$ approximate $\mu_{\text{reject}}$ by $\hat{z}$ which suffices to distinguish whether $\mu_{\text{reject}} \ge b$ or $\mu_{\text{reject}} \le a$ as we have chosen $\varepsilon = (\frac{1}{3}(b-a)/(3+\delta^2/2))^2$. $\square$

## 4.3 Block-encoding input model

We will see that life becomes beautifully simple if we consider the block-encoding input model instead of the sparse-access one. In particular, we obtain that computing any normalized spectral sum is DQC1-complete whenever $f$ and $f^{-1}$ are sufficiently smooth. Throughout this subsection, whenever we say that we are given a unitary or a block-encoding as input, we mean that we are given a polynomial size classical description of a quantum circuit that implements the corresponding unitary.

We first recall the following basic fact about DQC1 which is shown in [SJ08, FKM$^{+}$16].

**Fact 4.2.** Given a unitary $U \in \mathbb{C}^{2^n \times 2^n}$, estimating $\frac{1}{2^n} \Re[\text{tr}[U]]$ up to $1/\text{poly}(n)$ additive accuracy is DQC1-complete.

Using standard techniques it can easily be seen that estimating the trace of a block-encoded Hermitian matrix $A$ is also DQC1-complete if the number of ancillary qubits used for the encoding is at most $O(\log n)$.

**Theorem 4.6.** Given a $(1, a, \varepsilon)$ block-encoding of a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ with $a = O(\log n)$ and $\varepsilon = 1/\text{poly}(n)$, estimating $\frac{1}{2^n} \text{tr}[A]$ up to additive error $1/\text{poly}(n)$ is DQC1-complete.

*Proof.* Let us start with the hardness. For this, we present a reduction from estimating $\frac{1}{2^n} \Re[\text{tr}[U]]$ of a given unitary $U \in \mathbb{C}^{2^n \times 2^n}$. Note that from the circuit description for $U$, we can also implement $U^\dagger$ by just applying the inverse of every gate from $U$ in reverse order. Further, we can apply controlled variants of $U$ and $U^\dagger$ by replacing every simple gate in their description by its controlled version. Thus, we can implement the following circuit for

$$ (H \otimes I)(|0\rangle \langle 0| \otimes U + |1\rangle \langle 1| \otimes U^\dagger)(H \otimes I): $$

<figure><img src="image_5.png" /></figure>
This circuit implements a (1, 1, 0) block-encoding $U_A$ of the Hermitian matrix $A = \frac{1}{2}(U + U^\dagger)$ as it is easily verified that $(\langle 0 | \otimes I) U_A (|0\rangle \otimes I) = A$. Since $\text{tr}[A] = \Re[\text{tr}[U]]$ the hardness follows.

For the containment, we present a converse reduction to the estimation of the real part of the trace of a unitary. For this let $U_A$ now be the block-encoding of some Hermitian matrix $A$ acting on $n + a$ qubits. We define a unitary $U'$ acting on four registers of $n + 3a$ qubits in total:

<figure><img src="image_6.png" /></figure>

The CNOT gates in the above circuit naturally stand for $a$ many CNOT gates applied to each of the qubits from the two registers. As a consequence, we find that for each $x \in \{0, 1\}^{n+3a}$ with $x_i = 1$ for some $i \in [a]$ we have $|x\rangle \perp U'|x\rangle$, i.e. $\langle x | U' | x \rangle = 0$. Hence, we find for the trace of $U'$:

$$ \begin{aligned} \text{tr}[U'] &= \sum_{x \in \{0,1\}^{n+3a}} \langle x | U' | x \rangle \\ &= \sum_{x \in \{0,1\}^{n+2a}} (\langle 0 | \otimes^a \langle x |) U' (|0\rangle \otimes^a |x\rangle) \\ &= \sum_{x \in \{0,1\}^n} \langle x | \underbrace{(\langle 0 | \otimes^a \otimes I) U_A (|0\rangle \otimes^a \otimes I)}_{\approx_{\epsilon} A} |x\rangle \cdot 2^{2a}. \end{aligned} $$

This yields

$$ |\text{tr}[U'] - 2^{2a} \text{tr}[A]| \le \epsilon \cdot 2^{n+2a}. $$

In particular we obtain $|\Re[\text{tr}[U')] - 2^{2a} \text{tr}[A]| \le \epsilon \cdot 2^{n+2a}$ which implies by multiplication with $\frac{1}{2^{n+2a}}$ that

$$ \left| \frac{2^a}{2^{n+3a}} \Re[\text{tr}[U')] - \frac{1}{2^n} \text{tr}[A] \right| \le \epsilon. $$

Thus, by the triangle-inequality, estimating $\frac{1}{2^{n+3a}} \Re[\text{tr}[U')]$ with accuracy $\pm \frac{\epsilon}{2^a}$ and then multiplying the result by $2^a$ gives an estimate for $\frac{1}{2^n} \text{tr}[A]$ with accuracy $\pm 2\epsilon$. $\square$

We now cite the polynomial eigenvalue transformation from [GSLW19]. We refer to their work for a proof.

**Theorem 4.7 (Polynomial eigenvalue transformation [GSLW19, compare Theorem 56]).** Suppose we are given $a$ $(1, a, \epsilon)$ block-encoding of a Hermitian matrix $A$ and a degree $d$ real polynomial satisfying $|p(x)| \le 1/2$ for all $x \in [-1, 1]$. Then there exists a classical algorithm running in time poly$(d, \log(1/\delta))$ that outputs the description of a quantum circuit implementing $a$ $(1, a + 2, 4d\sqrt{\epsilon} + \delta)$ block-encoding of $p(A)$.

We get our main result as a consequence of this.

**Theorem 4.8.** Let $I, J \subseteq [-\frac{1}{2}, \frac{1}{2}]$ be intervals and let $f: I \to J$. Suppose we are given $a$ $(1, a, \epsilon)$ block-encoding of a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ with spectrum in $I$ where $\epsilon = 1/\text{poly}(n)$ and $a = O(\log n)$.

(A1) Further, assume $f$ is $\zeta$-approximable on $I$ by a degree $d = O(\text{poly}(n/\zeta))$ polynomial $p$ such that $|p(x)| \le 1/2$ for all $x \in [-1, 1]$.
Then:

1. (DQC1-containment) There is a DQC1-algorithm that estimates $\frac{1}{2^n} \text{tr}[f(A)]$ with 1/ poly(n) additive accuracy.

2. (DQC1-hardness) If furthermore

(A2) $f^{-1}: J \to I$ exists and is also $\zeta$-approximable by a degree $d = O(\text{poly}(n/\zeta))$ polynomial $q$ such that $|q(x)| \le 1/2$ for all $x \in [-1, 1]$,

(A3) $f$ is Lipschitz continuous with constant $K = \text{poly}(n)$, and

(A4) the intervals $I, J$ are of non-negligible length $|I|, |J| \ge 1/\text{poly}(n)$,

then, estimating $\frac{1}{2^n} \text{tr}[f(A)]$ with $1/\text{poly}(n)$ additive accuracy is also DQC1-hard.

Proof. Let us start with the proof of the DQC1-containment. For this, let us fix a target accuracy $\tau = 1/\text{poly}(n)$. By (A1), we can choose a polynomial $p(x)$ of degree $d = \text{poly}(n/\tau)$ that $(\tau/2)$-approximates $f$ on $I$ and that satisfies $|p(x)| \le 1/2$ for all $x \in [-1, 1]$. This allows us to apply Theorem 4.7 with error $\delta = \frac{\tau}{8}$ to output in classical polynomial time a $(1, a+2, \eta)$ block-encoding of $p(A)$ with

$$ \eta = 4d\sqrt{\varepsilon} + \delta. $$

Since $d = O(\text{poly}(n/\tau))$ and $\varepsilon = 1/\text{poly}(n)$, we may assume $4d\sqrt{\varepsilon} \le \frac{\tau}{8}$ and hence $\eta \le \frac{\tau}{4}$. Using Theorem 4.6, we compute an estimate $z$ of the trace of this block-encoded matrix $\frac{1}{2^n} \text{tr}[p(A)]$ in DQC1 such that

$$ \left| z - \frac{1}{2^n} \text{tr}[p(A)] \right| \le 2\eta \le \frac{\tau}{2}. $$

Since further $\frac{1}{2^n} \text{tr}[p(A)]$ is $\tau/2$-close to $\frac{1}{2^n} \text{tr}[f(A)]$, this estimate $z$ yields the desired $\tau$ additive approximation of $\frac{1}{2^n} \text{tr}[f(A)]$.

Now let us continue with the second claim and show DQC1-hardness. We pick the hard instance from Theorem 4.6, that is let $A \in \mathbb{C}^{2^n \times 2^n}$ now be a Hermitian matrix with a (1, 1, 0) block-encoding $U_A$ of which it is DQC1-hard to estimate its normalized trace with $1/\text{poly}(n)$ additive accuracy. Notice however that the spectrum of $A$ lies in $[-1, 1]$, not in $J$. We therefore consider instead a matrix $\hat{A}$ whose spectrum is guaranteed to lie in $J$. Concretely, if $J = [y_0, y_1]$ for some $y_0, y_1 \in [-\frac{1}{2}, \frac{1}{2}]$, then define $\hat{A} := \frac{y_0+y_1}{2}I + \frac{y_1-y_0}{2}A$. It is immediate that the normalized trace of $\hat{A}$ allows to compute the normalized trace of $A$ since

$$ \frac{1}{2^n} \text{tr}[\hat{A}] = \frac{y_0 + y_1}{2} + \frac{y_1 - y_0}{2} \cdot \frac{1}{2^n} \text{tr}[A]. $$

Indeed, since by assumption $|J| = y_1 - y_0 \ge 1/\text{poly}(n)$, we can compute, with a polynomial overhead in accuracy, an approximation of $\frac{1}{2^n} \text{tr}[A]$ given an approximation of $\frac{1}{2^n} \text{tr}[\hat{A}]$. As such, it remains DQC1-hard to compute $\frac{1}{2^n} \text{tr}[\hat{A}]$ with $1/\text{poly}(n)$ additive accuracy. Also, using the polynomial eigenvalue transformation, Theorem 4.7, we can efficiently construct a $(1, 3, \delta)$ block-encoding $U_{\hat{A}}$ of $\hat{A}$ with $\delta = 1/\text{poly}(n)$ where $p(x) = \frac{y_0+y_1}{2} + \frac{y_1-y_0}{2}x$. Further, we choose a polynomial $q(x)$ of degree $d$ to approximate $f^{-1}$ with accuracy $\delta$ and construct via Theorem 4.7 a $(1, 5, 4d\sqrt{\delta} + \delta)$ block-encoding of $q(\hat{A})$. Finally, by the Lipschitz continuity of $f$ and since $|q(\hat{\lambda}_i) - f^{-1}(\hat{\lambda}_i)| \le \delta$ for all eigenvalues $\hat{\lambda}_i$ of $\hat{A}$, we find

$$ |f(q(\hat{\lambda}_i)) - \hat{\lambda}_i| = |f(q(\hat{\lambda}_i)) - f(f^{-1}(\hat{\lambda}_i))| \le K\delta \quad \text{for each } i \in [2^n]. $$

As such, we also have $|\frac{1}{2^n} \text{tr}[f(q(\hat{A}))] - \frac{1}{2^n} \text{tr}[\hat{A}]| \le K\delta = 1/\text{poly}(n)$ which goes to show that estimating the normalized trace of $f(q(\hat{A}))$ with $1/\text{poly}(n)$ accuracy instead of $\hat{A}$ remains DQC1-hard and thus finishes our proof. $\square$
Let us remark that in particular every Lipschitz continuous function $f$ with Lipschitz constant $K = \text{poly}(n)$ can be $\frac{1}{\text{poly}(n)}$-approximated by a poly($n$) degree polynomial (as e.g. shown in [Car00]). As such, the conditions (A1), (A2), (A3) in Theorem 4.8 could all be subsumed by the stronger condition that $f$ and $f^{-1}$ should both be Lipschitz continuous with poly($n$) bounded constants. As a direct consequence, we obtain:

**Corollary 4.9.** Given $a(1, a, \varepsilon)$ block-encoding of a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ with spectrum in $[\frac{1}{\kappa}, 1]$ where $\kappa, \varepsilon^{-1} = \text{poly}(n)$ and $a = O(\log n)$, estimating $\frac{1}{2^n} \log \det(A)$ with $1/\text{poly}(n)$ additive accuracy is DQC1-complete.

*Proof.* Consider

$$f: [\frac{1}{2\kappa}, \frac{1}{2}] \to [-\frac{1}{2}, 0], \quad f(x) := \frac{\log(2x)}{2\log \kappa}, \quad \text{as well as} \\ f^{-1}: [-\frac{1}{2}, 0] \to [\frac{1}{2\kappa}, \frac{1}{2}], \quad f^{-1}(x) = \frac{1}{2} e^{2x \log \kappa}.$$

Both are Lipschitz continuous with Lipschitz constants $K = \frac{\kappa}{\log \kappa}$ and $K' = \log \kappa$ respectively. In particular, there exist polynomials $p$ and $q$ of degree $d = \text{poly}(n/\zeta)$ which $\zeta$-approximate $f$ and $f^{-1}$ on their respective domains. Thus, estimating $\frac{1}{2^n} \text{tr}[f(\frac{1}{2}A)]$ with $1/\text{poly}(n)$ additive accuracy is DQC1-complete by Theorem 4.8. The same holds true for estimating $\frac{1}{2^n} \log \det(A)$ since $\frac{1}{2^n} \text{tr}[f(\frac{1}{2}A)] = \frac{1}{2^n \log \kappa} \log \det(A)$. $\square$

# 5 BQP-hardness and PP-completeness of estimating the log-determinant

## 5.1 BQP- and PP-hardness of the (log-)determinant

In this subsection we show that it is BQP-hard to estimate the *non-normalized* log-determinant of a sparse-access positive matrix with additive inverse polynomial accuracy and PP-hard to do so with inverse exponential accuracy. We first recall that estimating a specific entry of a matrix inverse is BQP-, respectively PP-hard, with these accuracies and then present a reduction from entrywise matrix inversion to the computation of the determinant which is then further reduced to the estimation of the log-determinant.

So let us now start by showing that estimating a specific entry of a matrix inverse is BQP-hard when inverse polynomial accuracy is required, and PP-hard when the accuracy is inverse exponential. This was first shown in [HHL09]. We now present an alternative proof with the subtle but important distinction that our hard matrix inversion instance has determinant equal to one. We will need this property in the later reductions. A similar construction has previously appeared in the space-bounded setting in [FR21].

**Theorem 5.1 (Compare Theorems 4 and 6 in [HHL09]).** Given sparse-access to $A \in \mathbb{C}^{2^{\text{poly}(n)} \times 2^{\text{poly}(n)}}$ such that $\frac{1}{\text{poly}(n)} \le \sigma_{\min}(A) \le \sigma_{\max}(A) \le 1$ and two indices $s, t \in [2^n]$, then

1. estimating $A^{-1}(s, t)$ with additive accuracy $\varepsilon = \frac{1}{\text{poly}(n)}$ is BQP-hard, and

2. estimating $A^{-1}(s, t)$ with additive accuracy $\varepsilon = \frac{1}{\exp(n)}$ is PP-hard.

*Proof.* Let $L \in \text{BQP}$ and suppose we are given an input $x \in \{0, 1\}^*$ of which we want to reduce the decision of whether $x \in L_{\text{yes}}$ or $x \in L_{\text{no}}$ to the problem of matrix inversion. By assumption, we know that in polynomial time, we can compute a circuit $Q_x = U_T \cdots U_1$ consisting of unitaries $U_1, \dots, U_T \in \mathbb{C}^{2^n \times 2^n}$ such that $|\langle 0 | \otimes^n Q_x | 0 \rangle|^{\otimes n} |^2 \ge 2/3$ or $\le 1/3$ depending on whether $x$ is a positive or negative input. With these unitaries, we define the $(T+1) \cdot 2^n \times (T+1) \cdot 2^n$
block matrix

$$A := \begin{bmatrix} I & -U_T & & & \\ I & -U_{T-1} & & & \\ & \ddots & \ddots & & \\ & & I & -U_1 & \\ & & & I & \end{bmatrix} \qquad (3)$$

and notice that its inverse exists and is equal to

$$A^{-1} = \begin{bmatrix} I & U_T & U_T U_{T-1} & \cdots & \cdots & U_T \cdots U_1 \\ & I & U_{T-1} & U_{T-1} U_{T-2} & \cdots & \vdots \\ & & \ddots & \ddots & \ddots & \vdots \\ & & & I & U_2 & U_2 U_1 \\ & & & & I & U_1 \\ & & & & & I \end{bmatrix}. \qquad (4)$$

Observe that the top right block of $A^{-1}$ is equal to $Q$. Thus, we can decide whether $x$ is a positive or negative input by estimating $A^{-1}(1, T \cdot 2^n+1) = \langle 0 | \otimes^n Q | 0 \rangle \otimes^n$ with constant additive accuracy. Furthermore, since the unitaries $U_i$ are efficiently computable, we can implement sparse-access to $A$. However, it should be noted that the largest singular value of $A$ is bounded by 2, not by 1 as required. We simply rescale the matrix with a factor $1/2$ and claim that $\hat{A} := \frac{1}{2}A$ with $s := 1, t := T \cdot 2^n + 1$ suffices as our hard matrix inversion instance since $\hat{A}^{-1} = 2A^{-1}$. A simple calculation now shows that the singular values of $\hat{A}$ are contained in $[\frac{1}{\kappa}, 1]$ with $\kappa = 2(T + 1) = \text{poly}(n)$:

$$\sigma_{\max}(\hat{A}) = \frac{1}{2} \cdot \sigma_{\max}(A) \le 1 \quad \text{and} \quad \sigma_{\min}(\hat{A}) = \frac{1}{\sigma_{\max}(\hat{A}^{-1})} = \frac{1}{2 \cdot \sigma_{\max}(A^{-1})} \ge \frac{1}{2(T+1)} = \frac{1}{\kappa}.$$

The PP-hardness can now be achieved building on the above findings. Note that counting the number of satisfying assignments to a SAT-formula is PP-hard. Given such a formula $\phi(x_1, ..., x_n)$, it is straightforward to implement a quantum circuit $Q = U_T \cdots U_1$ that maps the initial all-zeros state to the uniform superposition of all possible assignments with a coherent evaluation of $\phi$ on an ancillary qubit:

$$Q |0\rangle^{\otimes n+1} = \frac{1}{\sqrt{2^n}} \sum_{x_i \in \{0,1\}} |x_1 \dots x_n\rangle^{\otimes n} |\phi(x_1, \dots, x_n)\rangle.$$

The probability of measuring 1 in the last qubit is equal to the proportion of satisfying versus total assignments. Using a similar argument as in lemma 29 of [FL18], we can also find a circuit $Q'$ such that $|\langle 0 | Q' | 0 \rangle^{\otimes n+2}|^2$ is equal to this proportion. This directly implies that being able to invert $\hat{A}'$ defined with the unitaries $U'_i$ from $Q'$ with accuracy $1/\exp(n)$ would allow to exactly recover this proportion since it is a multiple of $\frac{1}{2^n}$. In particular, this would allow to recover the number of satisfying assignments to $\phi$. $\square$

The idea for the following reduction is taken from [FR21] who used a similar reduction in the space-bounded setting.

**Theorem 5.2.** Given sparse-access to a matrix $A \in \mathbb{C}^{2^{\text{poly}(n)}} \times 2^{\text{poly}(n)}$ such that $\frac{1}{\text{poly}(n)} \le \sigma_{\min}(A) \le \sigma_{\max}(A) \le 1$, then

1. estimating $|\det(A)|$ with multiplicative accuracy $\varepsilon = \frac{1}{\text{poly}(n)}$ is BQP-hard, and

2. estimating $|\det(A)|$ with multiplicative accuracy $\varepsilon = \frac{1}{\exp(n)}$ is PP-hard.
Proof. Let us start with the BQP-hardness. We present a polynomial time reduction from the hard matrix inversion instance in the above Theorem 5.1, that is let $A \in \mathbb{C}^{N \times N}$ be given as in (3), where $N = 2^{\text{poly}(n)}$. We use the matrix determinant lemma, to reduce the computation of the inverse of A to the computation of the determinant of B := $A + |s\rangle\langle t|$. Concretely, the lemma tells us

$$ \det(B) = (1 + \langle s | A^{-1} | t \rangle) \cdot \underbrace{\det(A)}_{=1}. \qquad (5) $$

Now, we set $\hat{B} := \frac{1}{3}B$ whose largest singular value is bounded by 1. Without loss of generality we assume that $|A^{-1}(s,t)| = |\langle 0 | \otimes^n Q | 0 \rangle |\otimes^n| \le 1-c$, that is the underlying quantum circuit does not accept with probability more than $(1-c)^2$ in any case for some small constant $c > 0$. Then we find that $\hat{B}$ is well-conditioned as we can prove an inverse polynomial lower bound on its smallest singular value. For this, recall the Shermann-Morrison formula which holds for invertible matrices $A$ satisfying $1 + A^{-1}(s,t) \ne 0$:

$$ (A + |s\rangle\langle t|)^{-1} = A^{-1} + \frac{1}{1 + A^{-1}(s,t)}(A^{-1} |s\rangle\langle t| A^{-1}). $$

We can use this formula to bound the smallest singular value of B:

$$ \begin{aligned} \sigma_{\min}(\hat{B}) &= \frac{1}{3\sigma_{\max}(B^{-1})} \ge \frac{1}{3\left(\sigma_{\max}(A^{-1}) + \frac{1}{|1+A^{-1}(s,t)|}\sigma_{\max}(A^{-1})\sigma_{\max}(|s\rangle\langle t|)\sigma_{\max}(A^{-1})\right)} \\ &\ge \frac{1}{3\left(2(T+1) + \frac{1}{c}4(T+1)^2\right)} \\ &\ge \frac{c}{18(T+1)^2}. \end{aligned} $$

From equation (5), we further find for the determinant of $\hat{B}$ that

$$ \det(\hat{B}) = \frac{1}{3^N} (1 + A^{-1}(s, t)). $$

Now assume we have an $\varepsilon$-relative approximation $z \in \mathbb{C}$ of $\det(\hat{B})$. Then we find that $3^Nz - 1$ gives a $(2\varepsilon)$-additive approximation of $A^{-1}(s,t)$ because

$$ |(3^Nz - 1) - A^{-1}(s,t)| = |3^N(z - \det(\hat{B}))| \le 3^N\varepsilon |\det(\hat{B})| = \varepsilon|1 + A^{-1}(s,t)| \le 2\varepsilon. $$

As such, estimating $\det(\hat{B})$ with constant relative accuracy suffices to decide whether $|A^{-1}(s,t)|^2 \ge 2/3$ or $\le 1/3$ and is thus BQP-hard.

The PP-hardness analogously follows for $\varepsilon = 1/\exp(n)$ as estimating $A^{-1}(s,t) \pm 1/\exp(n)$ is PP-hard. $\square$

**Theorem 5.3.** Given sparse-access to a positive semi-definite matrix $A \in \mathbb{C}^{2^{\text{poly}(n)} \times 2^{\text{poly}(n)}}$ such that $\frac{1}{\text{poly}(n)} \le \lambda_{\min}(A) \le \lambda_{\max}(A) \le 1$, then

1. estimating $\log \det(A)$ with additive accuracy $\varepsilon = \frac{1}{\text{poly}(n)}$ is BQP-hard, and

2. estimating $\log \det(A)$ with additive accuracy $\varepsilon = \frac{1}{\exp(n)}$ is PP-hard.

Proof. We show that the relative approximation of the determinant in absolute value of a general matrix as in Theorem 5.2 reduces to additively approximating the log-determinant of a positive semi-definite matrix. Given a possibly non-Hermitian $A \in \mathbb{C}^{2^{\text{poly}(n)} \times 2^{\text{poly}(n)}}$ of which it is BQP-,
respectively PP-hard, to compute an $\varepsilon$ multiplicative estimation of $|\det(A)|$, simply consider the matrix $AA^\dagger$ which is positive semidefinite and whose determinant is

$$ \det(AA^\dagger) = |\det(A)|^2. $$

Moreover, $AA^\dagger$ is $s^2$ sparse and we easily obtain sparse-access to it given sparse-access to $A$. Further, since $\lambda_j(AA^\dagger) = \sigma_j^2(A)$ for each $j \in [2^{\text{poly}(n)}]$, we find $\lambda_{\min}(AA^\dagger) \ge 1/\text{poly}(n)$ if and only if $\sigma_{\min}(A) \ge 1/\text{poly}(n)$.

Now, suppose we are given an $\varepsilon$-additive approximation $z$ of $\log \det(AA^\dagger) = \log(|\det(A)|^2)$. Then, we find that $e^{z/2}$ is an $\varepsilon$ multiplicative approximation of $|\det(A)|$ since

$$ \begin{aligned} |e^{z/2} - |\det(A)|| &= |e^{\frac{\log \det(AA^\dagger)}{2}} + \frac{z - \log \det(AA^\dagger)}{2} - |\det(A)|| \\ &\le |\det(AA^\dagger)^{1/2} \cdot e^{\varepsilon/2} - |\det(A)|| \\ &= (e^{\varepsilon/2} - 1)|\det(A)| \\ &\le \varepsilon|\det(A)|, \end{aligned} $$

where the last inequality holds since $e^{\varepsilon/2} - 1 \le \varepsilon$ for any $\varepsilon \in (0, 1)$. As a consequence, we find that estimating $\log \det(AA^\dagger)$ with additive inverse polynomial accuracy is BQP-hard and with additive inverse exponential accuracy is PP-hard. $\square$

## 5.2 PP-containment

**Theorem 5.4.** Given sparse-access to a Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$ such that $\|A\| \le 1$, a real polynomial $p(x) = \sum_{k=0}^d c_k x^k$ of degree $d = \text{poly}(n)$ such that $|c_{\max}| \le \exp(n)$ and values $a, b \in \mathbb{R}$ such that $\Delta := b - a \ge 1/\exp(n)$, deciding whether $\text{tr}[p(A)] \ge b$ or $\text{tr}[p(A)] \le a$ is contained in PP.

*Proof.* For any $k \in \{0, ..., d\}$, denote by $W_i^{(k)}$ the set of all closed walks of length $k$ from $i \in [2^n]$ to itself, i.e.

$$ W_i^{(k)} := \{ (w_0, ..., w_k) \in [2^n]^{k+1} \mid w_0 = w_k = i \text{ and } A(w_l, w_{l+1}) \neq 0 \ \forall l \in \{0, ..., k-1\} \}. $$

Because each row has at most $s = \text{poly}(n)$ non-zero entries by assumption, the number of such length-$k$ closed walks starting at $i$ is at most $|W_i^{(k)}| \le s^k \le 2^{\text{poly}(n)}$. In fact, let us assume without loss of generality that $|W_i^{(k)}| = s^k$ for each $k \in \{0, ..., d\}$ and $i \in [2^n]$. We could enforce this by filling up $W_i^{(k)}$ with some dummy walks $w = (w_0, ..., w_k)$ for which $A(w_l, w_{l+1}) = 0$ is allowed. Note that the diagonal entry $A^k(i, i)$ expands as

$$ A^k(i, i) = \sum_{(w_0, ..., w_k) \in W_i^{(k)}} A(w_0, w_1) \cdots A(w_{k-1}, w_k) $$

and as such, the trace of $p(A)$ is given as

$$ \text{tr}[p(A)] = \sum_{k=0}^{d} c_k \cdot \text{tr}[A^k] = \sum_{k=0}^{d} c_k \cdot \sum_{i \in [2^n]} A^k(i, i) = \sum_{k=0}^{d} \sum_{i \in [2^n]} \sum_{w \in W_i^{(k)}} c_k \cdot A(w_0, w_1) \cdots A(w_{k-1}, w_k). $$

Observe that the above is a sum of $2^n \cdot \sum_{k=0}^d s^k \le 2^{\text{poly}(n)}$ terms. Moreover, each individual term is a product of some coefficient $c_k$ and $\text{poly}(n)$ entries of $A$ each of which is computable in $\text{poly}(n)$ time since we assume sparse-access to $A$, and so each term can be evaluated in $\text{poly}(n)$ time.

Let us now describe a non-deterministic polynomial time Turing machine which will have more accepting than rejecting paths if $\text{tr}[p(A)] \ge b$ and less if $\text{tr}[p(A)] \le a$.
1. Non-deterministically choose $k \in \{0, ..., d\}$, $i \in [2^n]$ and $w = (w_0, ..., w_k) \in W_i^{(k)}$. Then compute

$$r(k, i, w) := \Re[c_k \cdot A(w_0, w_1) \cdots A(w_{k-1}, w_k)].$$

Observe that $\sum_{k \in [d]-1, i \in [2^n], w \in W_i^{(k)}} r(k, i, w) = \text{tr}[p(A)]$ since $A$ is a Hermitian matrix. Further, we can assume without loss of generality that $r(k, i, w) \in [-1, 1]$. Otherwise, we simply rescale $p$.

2. Let $Q := \lceil \frac{6|W|}{\Delta} \rceil$ where $|W| := \sum_{k=0}^d \sum_{i \in [2^n]} |W_i^{(k)}| = \sum_{k=0}^d s^k$. Then proceed to compute

$$R(k, i, w) := \left\lceil \frac{r(k, i, w) + 1}{2} \cdot Q \right\rceil \in \{0, 1, ..., Q - 1\}.$$

Finally, non-deterministically choose a $T \in \{0, 1, ..., Q - 1\}$ and accept the computation path if and only if $T < R(k, i, w)$ which will be the case for exactly $R(k, i, w)$ many choices of $T$.

The total number of computation paths will be

$$P_{\text{tot}} = \sum_{k=0}^{d} \sum_{i \in [2^n]} |W_i^{(k)}| \cdot Q = 2^n \cdot Q \cdot \sum_{k=0}^{d} s^k \le 2^{\text{poly}(n)}$$

and the number of accepting paths will be

$$P_{\text{acc}} = \sum_{k=0}^{d} \sum_{i \in [2^n], w \in W_i} R(k, i, w).$$

Recall that

$$\text{tr}[p(A)] = \sum_{k \in [d]-1, i \in [2^n], w \in W_i} r(k, i, w) = \frac{2}{Q} \sum_{k \in [d]-1, i \in [2^n], w \in W_i} R(k, i, w) - |W| + E$$

where $E$ is a rounding error term bounded by $|E| \le |W| \cdot \frac{2}{Q} = |W| \cdot 2 \cdot \frac{\Delta}{6|W|} = \frac{\Delta}{3}$.

Now set $P_{\text{thresh}} := \lceil \frac{Q}{2} (m + |W|) \rceil$ where $m = \frac{a+b}{2}$. It turns out that the following holds:

1. If $\text{tr}[A^k] \ge b$, then $P_{\text{acc}} > P_{\text{thresh}}$. This is verified by calculating

$$\begin{aligned} P_{\text{acc}} &= \sum_{k,i,w} R(k,i,w) = \frac{Q}{2} (\text{tr}[A^k] + |W| - E) \\ &\ge \left\lceil \frac{Q}{2} \left( \underbrace{b}_{=m+\frac{\Delta}{2}} + |W| - \underbrace{E}_{<\frac{\Delta}{2}} \right) \right\rceil \\ &> \left\lceil \frac{Q}{2} (m + |W|) \right\rceil = P_{\text{thresh}}. \end{aligned}$$

2. If $\text{tr}[A^k] \le a$, then $P_{\text{acc}} \le P_{\text{thresh}}$. We verify this by similarly calculating

$$\begin{aligned} P_{\text{acc}} &= \sum_{k,i,w} R(k,i,w) = \frac{Q}{2} (\text{tr}[A^k] + |W| - E) \\ &\le \left\lceil \frac{Q}{2} \left( \underbrace{a}_{=m-\frac{\Delta}{2}} + |W| - \underbrace{E}_{>-\frac{\Delta}{2}} \right) \right\rceil \\ &< \left\lceil \frac{Q}{2} (m + |W|) \right\rceil = P_{\text{thresh}}. \end{aligned}$$
Ideally, we would like that $P_{\text{thresh}} = \frac{1}{2}P_{\text{tot}}$. In order to achieve this, we modify our Turing machine to produce a number of dummy accepting and rejecting paths $D_{\text{acc}}$ and $D_{\text{rej}}$ so that indeed $P'_{\text{acc}} = P_{\text{acc}} + D_{\text{acc}}$ is greater than $P'_{\text{rej}} = P_{\text{rej}} + D_{\text{rej}}$ if and only if $P_{\text{acc}} > P_{\text{thresh}}$. For this set $R := 2P_{\text{thresh}} - P_{\text{tot}}$. Importantly, because we assumed $|W| = \sum_{k=0}^{d} s^k$, it is easy to precompute $R$. If $R \ge 0$, choose $D_{\text{acc}} = 0$ and $D_{\text{rej}} = R$. If $R < 0$, choose $D_{\text{acc}} = -R$ and $D_{\text{rej}} = 0$. In any case, it is easy to verify that $P'_{\text{acc}} > P'_{\text{rej}}$ if and only if $P_{\text{acc}} > P_{\text{thresh}}$. $\square$

The above theorem directly implies that we can estimate the log-determinant and the trace of the inverse of a sparse matrix with inverse exponential accuracy in PP.

**Corollary 5.5.** Suppose we are given sparse-access to a poly($n$) sparse Hermitian matrix $A \in \mathbb{C}^{2^n \times 2^n}$, and values $a, b \in \mathbb{R}$ such that $\Delta := b - a \ge 1/\exp(n)$. If the spectrum of $A$ is contained in $[\frac{1}{\text{poly}(n)}, 1]$, 1. then we can decide in PP whether $\log \det(A) \ge b$ or $\le a$, and 2. whether $\text{tr}[A^{-1}] \ge b$ or $\le a$. If the spectrum of $A$ is contained in $[-1, 1]$, 3. then we can decide in PP whether $\text{tr}[A^p] \ge b$ or $\le a$ for any $p = \text{poly}(n)$, and 4. whether $\text{Z}[A, \beta] \ge b$ or $\le a$ for any $\beta = \text{poly}(n)$.

*Proof.* For the first claim, let $p_d^{(1)}(x) = -\sum_{k=1}^d (1-x)^k/k$ from Lemma 3.6 and recall that for degree $d = O(\kappa \log(1/\varepsilon))$, it is $\varepsilon$-close to $\log(x)$ on $[\frac{1}{\kappa}, 1]$. Therefore, for any $\kappa = \text{poly}(n)$ and $\varepsilon = 1/\exp(n)$, the degree remains polynomial in $n$ and we can invoke Theorem 5.4. The other statements follow analogously. $\square$

## Acknowledgments

The authors thank Uma Girish and Kunal Marwaha for suggesting an approach on how to prove the presented PP upper bounds. They also thank Simon Apers, Ryu Hayakawa, Yupan Liu, and Harumichi Nishimura for insightful discussions. Part of the work was done while RE was visiting Nagoya University and Yukawa Institute for Theoretical Physics, and AH was visiting IRIF and Yukawa Institute for Theoretical Physics.

RE has received support under the program "Investissement d'Avenir" launched by the French Government and implemented by ANR, with the reference "ANR-22-CMAS-0001, QuanTEdu-France". AH is supported by JSPS KAKENHI grant No. 24H00071. FLG is supported by JSPS KAKENHI grant No. 24H00071, MEXT Q-LEAP grant No. JPMXS0120319794, JST ASPIRE grant No. JPMJAP2302 and JST CREST grant No. JPMJCR24I4.

## References

[Aar25] Scott Aaronson. Quantum! AI! Everything but Trump!, 2025. https://scottaaronson.blog/?p=8834 [2025/06/12].

[ABB00] Orly Alter, Patrick O Brown, and David Botstein. Singular value decomposition for genome-wide expression data processing and modeling. *Proceedings of the National Academy of Sciences*, 97(18):10101–10106, 2000.

[AGSS23] Simon Apers, Sander Gribling, Sayantan Sen, and Dániel Szabó. A (simple) classical algorithm for estimating Betti numbers. *Quantum*, 7:1202, 2023.
[ATS03] Dorit Aharonov and Amnon Ta-Shma. Adiabatic quantum state generation and statistical zero knowledge, 2003.

[BCK15] Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In *2015 IEEE 56th Annual Symposium on Foundations of Computer Science*, page 792–809. IEEE, October 2015.

[Bra08] Fernando GSL Brandão. Entanglement theory and the quantum simulation of many-body physics. *arXiv preprint arXiv:0810.0026*, 2008.

[BT24] Ainesh Bakshi and Ewin Tang. An improved classical singular value transformation for quantum machine learning. In *Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024)*, pages 2398–2453. SIAM, 2024.

[Car00] N. Carothers. Approximation theory - a short course. 11 2000.

[CGL$^{+}$22] Nai-Hui Chia, András Pal Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and Chunhao Wang. Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning. *Journal of the ACM*, 69(5):1–72, 2022.

[CM18] Chris Cade and Ashley Montanaro. The Quantum Complexity of Computing Schatten p-norms. In *Proceedings of the 13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)*, volume 111 of *LIPIcs*, pages 4:1–4:20, 2018.

[CSS21] 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.

[FKM$^{+}$16] Keisuke Fujii, Hirotada Kobayashi, Tomoyuki Morimae, Harumichi Nishimura, Shuhei Tamate, and Seiichiro Tani. Power of Quantum Computation with Few Clean Qubits. In *Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)*, volume 55 of *LIPIcs*, pages 13:1–13:14, 2016.

[FL18] Bill Fefferman and Cedric Yen-Yu Lin. A complete characterization of unitary quantum space. In *9th Innovations in Theoretical Computer Science Conference (ITCS 2018)*, volume 94 of *LIPIcs*, pages 4:1–4:21, 2018.

[FR21] Bill Fefferman and Zachary Remscrim. Eliminating intermediate measurements in space-bounded quantum computation. In *Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021)*, 2021.

[GLG23] Sevag Gharibian and François Le Gall. Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. *SIAM Journal on Computing*, 52(4):1009–1038, 2023.

[GLM25] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. A quantum algorithm for estimating the determinant. *arXiv preprint arXiv:2504.11049*, 2025.

[GSLW19] 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 (STOC 2019)*, pages 193–204, 2019.

[HHL09] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. *Physical Review Letters*, 103(15), 2009.
[HMS15] Insu Han, Dmitry Malioutov, and Jinwoo Shin. Large-scale log-determinant computation through stochastic chebyshev expansions. In *Proceedings of the 32nd International Conference on Machine Learning (ICML 2015)*, pages 908–917, 2015.

[Hoe63] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. *Journal of the American Statistical Association*, 58(301):13–30, 1963.

[Hut89] Michael F Hutchinson. A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. *Communications in Statistics-Simulation and Computation*, 18(3):1059–1076, 1989.

[KL98] Emanuel Knill and Raymond Laflamme. Power of one bit of quantum information. *Physical Review Letters*, 81(25):5672, 1998.

[KP17] Iordanis Kerenidis and Anupam Prakash. Quantum Recommendation Systems. In *Proceedings of 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)*, volume 67 of *LIPIcs*, pages 49:1–49:21, 2017.

[KSV02] Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. *Classical and quantum computation*. Number 47. American Mathematical Soc., 2002.

[Le 25] François Le Gall. Classical algorithms for constant approximation of the ground state energy of local Hamiltonians. In *Proceedings of the 2025 European Symposium on Algorithms (ESA 2025)*, to appear, 2025.

[LS20] Alessandro Luongo and Changpeng Shao. Quantum algorithms for spectral sums. *arXiv preprint arXiv:2011.06475*, 2020.

[MMMW21] Raphael A Meyer, Cameron Musco, Christopher Musco, and David P Woodruff. Hutch++: Optimal stochastic trace estimation. In *Proceedings of Symposium on Simplicity in Algorithms (SOSA 2021)*, pages 142–155. SIAM, 2021.

[NC10] Michael A Nielsen and Isaac L Chuang. *Quantum computation and quantum information*. Cambridge University Press, 2010.

[NHD12] Feiping Nie, Heng Huang, and Chris Ding. Low-rank matrix recovery via efficient schatten $p$-norm minimization. In *Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2012)*, volume 26, pages 655–661, 2012.

[SJ08] Peter W. Shor and Stephen P. Jordan. Estimating Jones polynomials is a complete problem for one clean qubit. *Quantum Information and Computation*, 8(8):681–714, 2008.

[SV14] Sushant Sachdeva and Nisheeth K. Vishnoi. Faster algorithms via approximation theory. *Foundations and Trends® in Theoretical Computer Science*, 9(2):125–210, 2014.

[Tan19] Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In *Proceedings of the 51st annual ACM SIGACT symposium on theory of computing (STOC 2019)*, pages 217–228, 2019.

[UCS17] Shashanka Ubaru, Jie Chen, and Yousef Saad. Fast estimation of tr(f(A)) via stochastic Lanczos quadrature. *SIAM Journal on Matrix Analysis and Applications*, 38(4):1075–1099, 2017.

[WR06] Christopher KI Williams and Carl Edward Rasmussen. *Gaussian processes for machine learning*, volume 2. MIT press Cambridge, MA, 2006.
[ZFO+19] 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.

A Omitted proof of Lemma 3.6

**Lemma 3.6** (Polynomial approximations via truncated Taylor expansion). *The following holds true:*

1. For degree $d = O(\kappa \log \frac{1}{\epsilon})$, the polynomial $p_d^{(1)}(x) := -\sum_{k=1}^d (1-x)^k/k$ is $\epsilon$-close to $\log(x)$ for all $x \in [\frac{1}{\kappa}, 1]$, and

2. for degree $d = O(\kappa \log \frac{\kappa}{\epsilon})$, the polynomial $p_d^{(2)}(x) := \sum_{k=0}^d (1-x)^k$ is $\epsilon$-close to $1/x$ for all $x \in [\frac{1}{\kappa}, 1]$.

3. Let $\beta > 0$. For degree $d = O(\beta + \log \frac{1}{\epsilon})$, the polynomial $p_d^{(3)}(x) := \sum_{k=0}^d (-\beta x)^k/k!$ is $\epsilon$-close to $e^{-\beta x}$ for all $x \in [-1, 1]$.

*Proof.* We show each claim separately.

1. Observe that for all $x \in [\frac{1}{\kappa}, 1]$, we have $\log(x) = -\sum_{k=1}^{\infty} \frac{(1-x)^k}{k}$. We set $r_d^{(1)}(x) := -\sum_{k=d+1}^{\infty} \frac{(1-x)^k}{k}$ and note that with $d \ge \kappa \log \frac{1}{\epsilon} - 1$ we have for all $x \in [\frac{1}{\kappa}, 1]$,

$$ 
\begin{aligned}
|p_d^{(1)}(x) - \log(x)| &= |r_d^{(1)}(x)| 
\le \frac{1}{d+1} \sum_{k=d+1}^{\infty} \left(1 - \frac{1}{\kappa}\right)^k \\
&= \frac{(1 - \frac{1}{\kappa})^{d+1}}{(d+1)(1 - (1 - \frac{1}{\kappa}))} \\
&\le \frac{\kappa e^{-\frac{1}{\kappa}(d+1)}}{d+1} \\
&\le \frac{\kappa e^{-\frac{1}{\kappa}\kappa \log(1/\epsilon)}}{\kappa \log(1/\epsilon)} = \frac{\epsilon}{\log \frac{1}{\epsilon}} \le \epsilon,
\end{aligned}
$$

where the second inequality uses that $(1-x)^r \le e^{-xr}$ for all $x \in \mathbb{R}$, $r \ge 0$.

2. Similarly, observe that for all $x \in [\frac{1}{\kappa}, 1]$, we have $\frac{1}{x} = \sum_{k=1}^{\infty} (1-x)^k$. We set $r_d^{(2)}(x) := \sum_{k=d+1}^{\infty} (1-x)^k$ and note that with $d \ge \kappa \log \frac{\kappa}{\epsilon} - 1$ we have for all $x \in [\frac{1}{\kappa}, 1]$,

$$ 
\begin{aligned}
|p_d^{(2)}(x) - 1/x| &= |r_d^{(2)}(x)| 
\le \sum_{k=d+1}^{\infty} \left(1 - \frac{1}{\kappa}\right)^k \\
&= \frac{(1 - \frac{1}{\kappa})^{d+1}}{(1 - (1 - \frac{1}{\kappa}))} \\
&\le \kappa e^{-\frac{1}{\kappa}(d+1)} \\
&\le \kappa e^{-\frac{1}{\kappa}\kappa \log \frac{\kappa}{\epsilon}} = \epsilon.
\end{aligned}
$$

3. Lastly, note that for all $x \in [-1, 1]$, we have $\exp(-\beta x) = \sum_{k=0}^{\infty} (-\beta x)^k/k!$. We set
$r_d^{(3)}(x) := \sum_{k=d+1}^{\infty} (-\beta x)^k/k!$ and with $d \ge e^2\beta + \log\frac{1}{\epsilon} - 1$ we can bound for all $x \in [-1, 1]$,

$$
\begin{align*}
|p_d^{(3)}(x) - \exp(-\beta x)| &= |r_d^{(3)}(x)| \\
&\le \sum_{k=d+1}^{\infty} \frac{\beta^k}{k!} \\
&= \frac{\beta^{d+1}}{(d+1)!} \sum_{k=0}^{\infty} \frac{\beta^k (d+1)!}{(k+d+1)!} \\
&\le \frac{\beta^{d+1}}{(d+1)!} \sum_{k=0}^{\infty} \frac{\beta^k}{k!} \\
&= \frac{\beta^{d+1}}{(d+1)!} e^{\beta} \\
&\le \left( \frac{e\beta}{d+1} \right)^{d+1} e^{\beta} \\
&\le \left( \frac{1}{e} \right)^{\beta+\log(1/\epsilon)} e^{\beta} = \frac{\epsilon}{e^{\beta}} e^{\beta} = \epsilon,
\end{align*}
$$

where we used for the third inequality that $(d+1)! \ge (\frac{d+1}{e})^{d+1}$. This inequality is easily verified by taking the exponential of both sides of the following inequality:

$$
\log((d+1)!) = \sum_{k=1}^{d+1} \log k \ge \int_{1}^{d+1} \log(x)dx = (d+1)\log(d+1) - (d+1) + 1.
$$

<figure><img src="image_7.png" /></figure>