Author: Robert R. Tucci
(Qubiter Logo)
Check out the following paper unveiled last night in ArXiv:
An Open-Source, Industrial-Strength Optimizing Compiler for Quantum Programs, by Robert S. Smith, Eric C. Peterson, Mark G. Skilbeck, Erik J. Davis, https://arxiv.org/abs/2003.13961
This is an exciting development for me since I have been a proponent and practitioner of the art of quantum compilers for a long time.
The new “optimized quantum compiler” by Rigetti is a computer program that tackles the problem of searching for the “shortest” quantum circuit. Note, however, that it comes with some caveats:
- This program doesn’t generally find the optimal solution to this problem. Finding the optimal solution for this problem most probably requires an exp(number of qubits) number of operations to “finish”. So for more than 5 to 10 qubits, an optimal program for this problem would be so slow that it would be well-nigh useless. The shortest circuit problem probably has many local minima. This program is not even guaranteed to find one of those local minima. It finds something that is optimal only within small segments of the circuit. “piecewise optimal”?
- What is the “shortest circuit” is somewhat debatable and device dependent. The output of this computer program is device dependent, as it favors gates that are native to the Rigetti qc.
- This program is written in Lisp, which is, to put it mildly, not one of the most popular or fastest-growing or newest or easiest to write, computer languages in town.
To be fair, IBM’s optimizing quantum compiler suffers from all the same difficulties, except that theirs is written in Python/C++ instead of Lisp. Microsoft’s quantum compiler suffers from these difficulties too, but theirs is written in one or more of Microsoft’s dead or dying languages C#, F#, Q#. (The # stands for a tombstone with a cross.) In fact, classical compilers suffer from similar difficulties too.
(IBM calls their quantum compiler a transpiler instead of a compiler, but dozens of researchers that have preceded IBM in this field call this type of software a compiler.)
Quantum compilers have a long history. Nowadays, Microsoft, IBM, Rigetti and Google, have one.
The first paper to use the term “quantum compiler” in its title (and probably also in its body but I’m less sure about that) was mine
A Rudimentary Quantum Compiler, by Robert R. Tucci, https://arxiv.org/abs/quant-ph/9805015
I quickly followed that paper with a beefier “second edition” with more “quantum compiler optimizations”:
A Rudimentary Quantum Compiler(2cnd Ed.), by Robert R. Tucci, https://arxiv.org/abs/quant-ph/9902062
Within a year of my “rudimentary quantum compiler” paper, I wrote a C++ program called Qubiter that implemented the algorithms of the paper, and I filed for a patent for Qubiter (It’s item #2 in this list. The patent expires today, April 01, 2020). Later, I also applied for an ARO (Army Research Office) grant to enhance Qubiter. I applied for the grant jointly with a university professor that specializes in Linear Algebra. Sadly, the aplication was rejected. (That’s an interesting story in itself, but for another time.)
My original reason for studying quantum compiling was to “compile” the nodes of a quantum Bayesian network (i.e., to replace each of the nodes by a sequence of elementary gates). In fact, I wrote a paper explaining how to achieve that goal
How to Compile A Quantum Bayesian Net, by Robert R. Tucci, https://arxiv.org/abs/quant-ph/9805016
More recently, I wrote an open-source quantum simulator in Python, that I also called Qubiter. The new Qubiter includes a Python implementation of the old C++ Qubiter. It also includes, in a folder called LEGACY, the C++ code for the original Qubiter.
My original use of the word “quantum compiler” has been expanded somewhat by others throughout the years. To be more specific, nowadays I call Qubiter’s original quantum compiler a “quantum CSD compiler”. CSD stands for Cosine-Sine Decomposition, a very famous, in its own right, decomposition in Linear Algebra. Here is the LAPACK implementation of CSD. My “rudimentary quantum compiler” paper was the first paper ever to use that decomposition to compile an arbitrary unitary matrix (i.e., to decompose it into a sequence of elementary gates such as single qubit rotations and CNOTs).
Since I wrote my original paper on quantum compilers, I’ve written several other arxiv papers on the subject. I’ve also written numerous articles about quantum compiling for my blog, “Quantum Bayesian Networks”.