Quantum Bayesian Networks

April 17, 2009

Brief Introduction to Quantum Compilers

Filed under: Uncategorized — rrtucci @ 8:46 am

Qubiter Logo

A general purpose quantum compiler is a computer program (for a conventional classical computer) that takes an arbitrary unitary matrix U as input and returns a decomposition of U; more specifically, it expresses U as a SEO (Sequence of Elementary Operations). The basic set of elementary operations is arbitrary, but it usually consists of single-qubit rotations and CNOTs. A SEO is the machine language of quantum computers. It’s what they understand. By an arbitrary unitary matrix we mean a unitary matrix that doesn’t have any structure which is known a priori to the compiler’s user. A special purpose quantum compiler is a computer program that decomposes an input unitary matrix U with known a priori structure into a SEO. For example, it might decompose a matrix U known a priori to be a Discrete Fourier Transform matrix into its Coppersmith SEO.

Back in 1998, when I was 10 years younger (how time flies), I published at ArXiv a paper that describes a method for doing exact, general quantum compiling using, in a recursive manner, something called in Linear Algebra the CS decomposition (CSD). See Appendix A. It appears nobody had thought of using recursive CSD to do quantum compiling before. At the same time, I also posted publicly at my website the C++ source code for a program called Qubiter that implements this recursive CSD method. So far, Qubiter is the only general purpose quantum compiler listed at quantiki.

More recently, I’ve also posted the Java source code for a special purpose quantum compiler called QuanSuite.

Why are quantum compilers useful?

• One good reason to build quantum compilers is simply to obtain a numerical SEO for a pesky unitary. Note that to express exactly an arbitrary unitary matrix of size $2^{N_B}\times 2^{N_B}$, we need a sequence of at least ${\cal O}(2^{N_B}\times 2^{N_B})$ elementary operation. Hence, for $N_B$ larger than about 5, it becomes impractical to compile arbitrary matrices exactly. However, if we can enhance a quantum compiler so that it can do approximate compilations, then the range of doable matrix sizes might be extended considerably. What kind of approximations are useful in quantum compiling? For example, one can use Trotter Rescaling and the Suzuki approximant. See Appendix B. Software implementations of the Trotter and Suzuki methods can be found in the Java class library for QuanSuite. This excellent recent paper by Jordan and Wocjan reviews much of the existing literature about the complexity, as a function of error and number of qubits, of approximate compilations of sparse unitary matrices. Note that some approximations assume that the unitary matrix being compiled is not totally arbitrary, that it has some structure, such as that it is sparse or it is generated by exponentiating a Hamiltonian that connects no more than a fixed number of qubits.
• Another good reason to study quantum compilers is that they help us understand the nature of those special input unitaries U which lead to efficient SEOs (i.e., SEOs whose length or number of elementary operations is polynomial($N_B$)). For example, this and this paper show that the Coppersmith SEO for a Discrete Fourier Transform matrix can be viewed as a special case of the recursive CSD method used by Qubiter. Thus, a Qubiter user unaware of the Coppersmith SEO can independently re-discover it using Qubiter.

Technical Appendices (in pdf):

• Appendix A. What is the CS decomposition and how does one use it to do quantum compiling?
• Appendix B. Brief Introduction to Trotter Rescaling, and to the Lie and Suzuki Approximants