The Quantum Query Complexity of the Determinant

Sebastian Dörn and Thomas Thierauf

Abstract:
In this paper we give tight quantum query complexity bounds of some important linear algebra problems. We prove Θ(n2) quantum query bounds for verifying the determinant, rank, matrix inverse and the matrix power problem.