Quantum Determinant Estimation

Abstract

A quantum algorithm for computing the determinant of a unitary matrix $U\in U(N)$ is given. The algorithm requires no preparation of eigenstates of $U$ and estimates the phase of the determinant to $t$ binary digits accuracy with $\mathcal{O}(N{\log }^{2}N+t^2)$ operations and $tN$ controlled applications of $U^{2^m}$ with $m=0,\dots ,t-1$. For an orthogonal matrix $O\in O(N)$ the algorithm can determine with certainty the sign of the determinant using $\mathcal{O}(N{\log }^{2}N)$ operations and $N$ controlled applications of $O$. An extension of the algorithm to contractions is discussed.

13 pages, 3 figures. Added references and discussion of runtime. Version accepted for publication