Quantum Compiler

During Winter Quarter 2012 at University of Washington, I optimized an algorithm that compiles quantum gates.  Given a target gate, this compiler will construct a sequence of quantum gates  that is “close” to the target gate using a matrix trace distance measure.  I didn’t finish everything I set out to do, but I’m in a good position to finish it next quarter!

The First Paper Version

Here’s a paper that summarizes some of my results.  In summary:

  1. Performance improved between 10x and 100x with a “meet in the middle” bipartite graph matching algorithm.
    1. The algorithm still requires exponential time and memory for a given sequence length.
    2. There are a lot of trivial things I could do to improve it, like using k-d trees.
  2. The FPGA optimizations were never actually finished (but they were close).

It does have a few errors and omissions:

  1. No Acknowledgements – please see the bottom of this page!
  2. Bad Trend Lines – The trend lines in the graph relating time to precision should only use the last 5 or 6 data points, because the algorithms have different behavior in the beginning.
  3. Unoptimized lines in the graph legends refer to Fowler’s original algorithm, with his optimizations, not mine.
  4. There are some other errors in the legends.

This certainly isn’t done yet. At the time of my presentation, I had a lot of work still in progress:

  1. FPGA implementation – it was compiling sequences in a simulator program ont he computer, but not yet on the actual prototyping board.
  2. Matrix multiplication precision benchmark – I was going to run an algorithm to measure the accumulation in trace error over a sequence of matrix multiplications on the FPGA prototyping board.

There are a few other things to try as well:

  1. Lookup batching – a large MITM data structure (or even just a unique sequence cache) could be stored on a hard disk, and requests to it could be batched by storage location.
  2. Optimized calculation – I can try a different representation of gates that yields faster calculations.

Want to find out more?


  • Paul Pham – the graduate student who suggested the research topic for this project, and who provided essential context and advice.  I had weekly meetings with him, and I worked with him on his pulse sequencer board two years ago.  Here’s his quantum compiler using the Solovay-Kitaev Theorem.
  • Aram Harrow – my faculty advisor, who came up with smart suggestions for error accumulation.  He also indirectly proposed the “meet in the middle” approach.
  • Carl Ebeling – my former faculty advisor, whose specialty is in hardware development.  He offered advice for the development of my FPGA implementation of the quantum compiler.

Leave a Reply