Lower Bound on Givens Rotation Matrices Decomposition of Quantum Fourier Transform
摘要
It is a well-known fact in matrix theory that unitary complex matrices can be represented as a product of complex Givens rotation matrices. The aim of this work is to establish a lower limit on the number of Givens rotation matrices required to decompose the quantum Fourier transform (QFT) matrix. It is shown that a minimum of three 2n − 3 Givens matrices are needed to factorize a n-qubit quantum Fourier transform matrix. The result has implications on the feasibility of implementing quantum algorithms that involve the quantum Fourier transform using an equivalent classical computer through matrix multiplications on the unitary matrix.