Complexity analysis of Grover’s algorithm based on matrix representation

Abstract For unstructured database search problems, Grover’s algorithm has query complexity O ( N ) , which is lower than the O ( N ) query complexity of classical algorithms. This work constructs the matrix forms of the oracle and diffusion operators using a matrix representation. The quantum state is projected onto a two-dimensional subspace spanned by the target and non-target states. The Grover iteration operator is reduced to a rotation matrix whose angle depends on the database size. Based on this reduction, we present the evolution of the quantum state after multiple iterations. We also show the quantitative relationship between the success probability and the number of iterations. When the number of iterations is chosen appropriately, the success probability approaches 1. We further analyze the algebraic structure of the Grover iteration operator. This operator can be decomposed into the identity matrix plus a finite number of rank-one matrices. Multiplication of a single matrix-vector can be performed with complexity O ( N ) . With the optimal number of iterations, the total classical simulation cost is O ( N 3 / 2 ) , whereas the quantum query complexity is O ( N ) .