Vittorio Giovannetti, Seth Lloyd, Lorenzo Maccone (Apr 16 2025).
Abstract: We present a quantum algorithm for estimating the matrix determinant based on quantum spectral sampling. The algorithm estimates the logarithm of the determinant of an
n×n positive sparse matrix to an accuracy
ϵ in time
O(logn/ϵ3), exponentially faster than previously existing classical or quantum algorithms that scale linearly in
n. The quantum spectral sampling algorithm generalizes to estimating any quantity
∑jf(λj), where
λj are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function
Z(β)=∑je−βEj of a Hamiltonian system with energy eigenvalues
Ej, and of the entropy
S=−∑jpjlogpj of a density matrix with eigenvalues
pj.