Posted

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×nn \times n positive sparse matrix to an accuracy ϵ\epsilon in time O(logn/ϵ3){\cal O}(\log n/\epsilon^3), exponentially faster than previously existing classical or quantum algorithms that scale linearly in nn. The quantum spectral sampling algorithm generalizes to estimating any quantity jf(λj)\sum_j f(\lambda_j), where λj\lambda_j are the matrix eigenvalues. For example, the algorithm allows the efficient estimation of the partition function Z(β)=jeβEjZ(\beta) =\sum_j e^{-\beta E_j} of a Hamiltonian system with energy eigenvalues EjE_j, and of the entropy S=jpjlogpj S =-\sum_j p_j \log p_j of a density matrix with eigenvalues pjp_j.

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!