Dequantization and Hardness of Spectral Sum Estimation

Based on the provided text, here is a detailed technical summary of the paper "Dequantization and Hardness of Spectral Sum Estimation."

Problem Statement

The paper addresses the computational complexity of estimating spectral sums of matrices, defined as $\text{tr}[f(A)] = \sum_{i=1}^N f(\lambda_i)$, where $\lambda_i$ are the eigenvalues of a Hermitian matrix $A$. Key examples include the log-determinant ($\log \det(A)$), the partition function ($\text{tr}[e^{-\beta A}]$), traces of powers ($\text{tr}[A^p]$), and the trace of the inverse ($\text{tr}[A^{-1}]$).

Recent quantum algorithms have demonstrated that for sparse, well-conditioned matrices, these quantities can be approximated with relative error $\epsilon$ in time polylogarithmic in the dimension $N$ (specifically $\text{poly}(\log N, s, \kappa, 1/\epsilon)$, where $s$ is sparsity and $\kappa$ is the condition number). The paper investigates two fundamental questions:

1. Dequantization: To what extent can these quantum runtime parameters be reproduced by classical algorithms?
2. Hardness: When classical reproduction is not possible, what are the complexity-theoretic obstructions?

Methodology

The authors develop two distinct classical algorithmic frameworks and complement them with complexity-theoretic lower bounds.

1. Classical Algorithms

Both algorithms rely on the observation that if a polynomial $p(x)$ uniformly approximates a function $f(x)$ on the spectrum of $A$, then the normalized spectral sums of $f$ and $p$ are close. The core task reduces to estimating the normalized trace of a matrix polynomial, $\frac{1}{2^n}\text{tr}[p(A)]$, which can be expressed as the expectation of diagonal entries: $\mathbb{E}_{i}[p(A)_{ii}]$.

• Deterministic Sparse Powering (for Sparse Matrices):

  • Approach: This algorithm samples a random diagonal index $i$ and explicitly enumerates all closed walks of length up to $d$ (the degree of the approximating polynomial) starting and ending at $i$.
  • Mechanism: For an $s$-sparse matrix, the number of such walks is bounded by $s^d$. The algorithm computes the weighted sum of these walks to evaluate $p(A)_{ii}$.
  • Runtime: $O^*(s^d \cdot f_{\max}^2 / \epsilon^2)$.
  • Application: By using Chebyshev truncation to approximate $\log(x)$, the authors derive an algorithm for the log-determinant of an $s$-sparse matrix with condition number $\kappa$. The runtime is $O^*(s^{c \cdot \sqrt{\kappa} \log(\kappa/\epsilon)})$. This represents an exponential improvement over previous classical methods (e.g., Hutchinson's estimator) which scale polynomially with the total number of non-zeros $\|A\|_0$.

• Random Walk Estimator (for Local Hamiltonians):

  • Approach: This algorithm replaces exhaustive enumeration with a random walk. Starting from a random index $i$, the walk transitions to neighbors with probability proportional to the absolute value of the matrix entries.
  • Mechanism: The algorithm maintains a running weight that compensates for the transition probabilities using row 1-norms and complex signs. This ensures the estimator is unbiased.
  • Advantage: For $k$-local Hamiltonians with bounded total interaction strength, the 1-norm $\|H\|_1$ is bounded by $2^{k/2}$, independent of the number of local terms $m$.
  • Runtime: $O^*(2^{kd} \|p\|_1^2 / \epsilon^2)$. This removes the dependence on the number of terms $m$ from the exponential part of the runtime, making it efficient for log-local Hamiltonians.

2. Complexity-Theoretic Hardness

The authors establish lower bounds to determine when classical algorithms cannot achieve the same efficiency as quantum ones.

• DQC1-Completeness: The paper proves that estimating normalized spectral sums (traces of powers and inverses) for log-local Hamiltonians to inverse-polynomial additive accuracy is DQC1-complete. This resolves an open problem regarding the complexity of Schatten-$p$ norm estimation. The proof utilizes a circuit-to-Hamiltonian construction (Kitaev's construction adapted by Brandão), showing that the spectral sum encodes the rejection probability of a DQC1 circuit.
• PP-Completeness: For unnormalized spectral sums, the authors prove PP-completeness under mild assumptions (polynomial approximability and non-degeneracy). The reduction involves constructing a diagonal matrix where the trace corresponds to the number of satisfying assignments of a Boolean formula, reducing the problem to MAJSAT.

Key Results

1. Dequantization of Log-Determinant: The authors provide a classical algorithm for the log-determinant of sparse, well-conditioned matrices that runs in time $O^*(s^{c \cdot \sqrt{\kappa} \log(\kappa/\epsilon)})$. While not fully polynomial in all parameters (specifically $\kappa$ and $\epsilon^{-1}$), it offers an exponential improvement in the dimension $N$ compared to classical methods scaling with $\|A\|_0$.
2. Complexity Landscape: The paper maps the complexity of four spectral sums (log-determinant, partition function, trace of powers, trace of inverse) across different parameter regimes:
   • Constant parameters: All problems are in BPP (solvable by classical randomized polynomial time).
   • Polylogarithmic parameters (e.g., $\kappa, \beta, p$): Problems admit classical quasipolynomial-time algorithms.
   • Polynomial parameters: For log-local Hamiltonians, the problems are DQC1-complete, implying no polynomial-time classical algorithm exists unless DQC1 $\subseteq$ BPP.
   • Inverse-exponential accuracy: Problems become PP-complete.
3. Resolution of Open Problems: The work resolves the DQC1-hardness for traces of polynomial powers and inverses, completing the complexity picture for these spectral sums initiated by Cade and Montanaro (2018).

Significance and Claims

The paper claims to fit into the broader program of "dequantizing" quantum linear algebra algorithms. Its significance lies in:

• Partial Dequantization: Demonstrating that the polylogarithmic dependence on dimension $N$ achieved by quantum algorithms can be preserved classically for specific parameter regimes, specifically for sparse matrices and local Hamiltonians.
• Identifying Quantum Advantage: The results suggest that the apparent quantum advantage in spectral sum estimation does not arise from the ability to achieve higher estimation accuracy per se, but rather from the ability to handle spectral parameters (like condition number $\kappa$ or inverse temperature $\beta$) that grow polynomially with $n$. In these regimes, the problems become DQC1-complete, and no efficient classical algorithm is known.
• Theoretical Completeness: By establishing DQC1-completeness for traces of powers and inverses, the paper closes a gap in the understanding of the computational power of the DQC1 model regarding spectral sums.

The authors note that while their classical algorithms improve upon previous bounds, they do not fully dequantize the quantum algorithms in all parameter regimes (specifically when $\kappa$ or $\epsilon^{-1}$ are large). Furthermore, they leave open the question of whether normalized spectral sums of general sparse matrices (not just log-local Hamiltonians) can be estimated in DQC1, noting that standard block-encoding techniques may not be ancilla-efficient enough for the DQC1 model.