2025/04/15 by Vittorio Giovannetti, Seth Lloyd, Giovannetti, Vittorio +3 · 4 citations
Computer Science · Mathematics · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2504.11049
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 \cal O(log n/ε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 ∑j f(λj), where λj are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function Z(β) =∑j e-βEj of a Hamiltonian system with energy eigenvalues Ej, and of the entropy S =-∑j pj log pj of a density matrix with eigenvalues pj.