The Quantum Query Complexity of Algebraic Properties

Sebastian Dörn and Thomas Thierauf

In this paper we present an application of the quantum walk search schema by Magniez et al. for finding more than one solution of a search problem. We apply our quantum walk to matrix multiplication, thereby improving a result by Buhrman and Spalek. Futhermore we give tight quantum query complexity bounds of some important linear algebra problems, like the determinant, rank, matrix inverse and the matrix power problem.