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