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

We study the computational complexity of estimating the normalized trace 2^-nTr[f(A)] for a log-local Hamiltonian A acting on n qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x). We show that if f(x) is a continuous function with approximate degree Ω\({rm poly}(n\)), then estimating 2^-nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when A is sparse, the classical query complexity of this problem is exponential in the approximate degree, assuming a conjectured lower bound for a trace variant of the k-Forrelation problem in the DQC1 query model. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and, conditionally, the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.