A Practical Top-down Approach to Quantum Circuit Synthesis
Vivek Shende, Stephen S. Bullock, Igor L. Markov · arXiv (Cornell University) · 2004
Operators acting on a collection of two-level quantum-mechanical systems can be represented by quantum circuits. In this work we develop a decomposition of such unitary operators which reveals their top-down structure and can be implemented numerically with well-known primitives. It leads to simultaneous improvements by a factor of two over (i) the best known n-qubit circuit synthesis algorithms for large n, and (ii) the best known three-qubit circuits. In the worst case, our algorithm NQ produces circuits that differ from known lower bounds by approximately a factor of two. Thus, the required number of quantum controlled-not's (i.e. two-qubit interactions) is only half of the number of real degrees of freedom (4^n-1) of a generic unitary operator. This is desirable since CNOTs are typically slower and more error-prone than one-qubit rotations, and they may in addition may require physically coupling distant two-level systems.