Quantum circuits synthesis using Householder transformations

A quantum compilation toolchain should provide a mean for decomposing a unitary matrix in a series of elementary operations: a so-called quantum circuit. Almost all existing methods have only sought to minimize the final size... [ view full abstract ]

A quantum compilation toolchain should provide a mean for decomposing a unitary matrix in a series of elementary operations: a so-called quantum circuit. Almost all existing methods have only sought to minimize the final size of the quantum circuit, the Quantum Shannon Decomposition being the reference method because producing the smallest circuits. Instead of only focusing on the size of the circuit, one can consider the problem in its globality and also take into account the quantity of classical resources needed, and in particular the time it takes to generate the circuit. This latter aspect is a recent subject of research and is the focus of our paper. 

We adapt the well known QR factorization based on Householder transformations to the quantum case. If some existing theoretical and experimental work has been undertaken, to our knowledge none has proposed an implementation method and a final circuit construction with clearly defined properties. The Householder method is numerically stable and is very promising in terms of compilation speed, therefore providing an interesting tool to be added in a quantum compilation toolbox. Our method breaks down into two stages. First we apply the QR factorization to a unitary matrix, in that case we can apply a simplified algorithm in order to divide the flops complexity by two. Secondly, we transform the QR factorization in a quantum circuit by synthesizing the elementary Householder transformations into precise quantum circuits. 

We made sequential and multithreaded runs to compare our method with the classical QR factorization and the QSD (see figures attached). We recover the factor of 2 between the classical QR and our QR factorization and the gain in time is considerable if we compare with the QSD. This compensates the bigger size of the final quantum circuit produced by the Householder method. For multithreaded runs the Householder method can rely on the scalability of the original QR method even if some improvements still need to be done to achieve the same performance. On the contrary no multithreaded version of the Cosine-Sine Decomposition (which is at the core of the QSD) exists to our knowledge. Above all, these results reveal that there is a tradeoff between the quantum resources and the classical resources needed in the compilation toolchain.