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:

*Performance improved between 10x and 100x*with a “meet in the middle” bipartite graph matching algorithm.- The algorithm still requires exponential time and memory for a given sequence length.
- There are a lot of trivial things I could do to improve it, like using k-d trees.

*The FPGA optimizations were never actually finished*(but they were close).

It does have a few errors and omissions:

*No Acknowledgements*– please see the bottom of this page!

*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.*Unoptimized*lines in the graph legends refer to Fowler’s original algorithm, with*his*optimizations,*not*mine.- 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:

*FPGA implementation*– it was compiling sequences in a simulator program ont he computer, but not yet on the actual prototyping board.*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:

*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.*Optimized calculation*– I can try a different representation of gates that yields faster calculations.

**Want to find out more?**

- Look at my live research paper draft on Google Docs.
- Download my FPGA code from Github. Source code for optimizations of the Fowler algorithm cannot be released for legal reasons.
- Read the brief research paper, by Austin Fowler, that describes the algorithm I’m optimizing.
- Read my weekly status updates. They have comics!

**Acknowledgements**

- 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.