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 , we need a sequence of at least elementary operation. Hence, for 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()). 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