Quantum Fast Fourier Transform Viewed as a Special Case of Recursive Application of Cosine-Sine Decomposition

Abstract

A quantum compiler is a software program for decomposing ("compiling") an arbitrary unitary matrix into a sequence of elementary operations (SEO). Coppersmith showed that the $\nb$-bit Discrete Fourier Transform matrix $U_{FT}$ can be decomposed in a very efficient way, as a sequence of order($\nb^2$) elementary operations. Can a quantum compiler that doesn't know a priori about Coppersmith's decomposition nevertheless decompose $U_{FT}$ as a sequence of order($\nb^2$) elementary operations? In other words, can it rediscover Coppersmith's decomposition by following a much more general algorithm? Yes it can, if that more general algorithm is the recursive application of the Cosine-Sine Decomposition (CSD).

14 pages (files: 1 .tex, 2 .sty, 5 .eps)

Cited by in corpus (3)

• How to Compile Some NAND Formula Evaluators
• A new algorithm for producing quantum circuits using KAK decompositions
• Quantum Compiling with Approximation of Multiplexors