Quantum circuit optimization via matroid partitioning

QuICS Seminar

Dmitri Maslov (NSF)
Monday, February 23, 2015 - 2:00pm
CSS 2115

In this talk I will give a broad overview of the topics I am interested in and was working on, and then concentrate on one recent result. Specifically, I will discuss an approach to the optimization of quantum Clifford+T circuits. The algorithm works in two stages: first, it efficiently (in polynomial time) optimizes {CNOT ,T} circuits with performance guarantee (optimally), and secondly, it is modified to handle Hadamard gates. The overall algorithm remains efficient while optimizing circuits over the complete fault-tolerant library {H, CNOT, T} = {{H, P=T^2, CNOT}, T} = {Clifford, T}, however, optimality may no longer be guaranteed. I will report the results of testing the practical performance of this algorithm using benchmarks. To illustrate the efficiency, a constant T-depth implementation of GF multiplication was discovered, whereas the best known circuits developed by humans had linear (and since more recently, logarithmic) T-depth. (No background beyond basic understanding of quantum computing and quantum circuit concepts is necessary.)