Synthesis of small quantum and reversible circuits with quality guarantee

  • Dmitri Maslov | US National Science Foundation

I will discuss algorithms for reversible and quantum circuit synthesis that guarantee different kinds of optimality. I will start with the single qubit case and describe a synthesis algorithm for Clifford+T circuits, followed by an outline of the proof of minimality of the number of Hadamard gates used in those circuits produced by the algorithm. For the multiple qubit case, I will present a meet-in-the-middle algorithm for the synthesis of Clifford+T depth-optimal circuits. The search is capable of finding 3-qubit optimal circuits of depth up to 10, and has important implications for quantum circuit design and simplification. Finally, I will describe a fast—taking an average of 0.00756 seconds to find a circuit—implementation of the meet-in-the-middle algorithm for 4-bit reversible logic synthesis that guarantees optimal gate counts, as well as an optimized implementation of the pruned breadth-first search capable of finding all 16! (=20,922,789,888,000) optimal reversible 4-bit circuits. The gate library used for reversible logic synthesis consists of the Toffoli type gates—NOT, CNOT, Toffoli, and Toffoli-4.

ArXiv paper numbers: arXiv:1103.2686, arXiv:1206.0758, arXiv:1206.5236.

Speaker Details

Dmitri Maslov received the MSc degree in Mathematics from Lomonosov’s Moscow State University, Russia, in 2000, and the MSc and PhD degrees in Computer Science from the University of New Brunswick, Canada, in 2002 and 2003, respectively. Currently, he is working as a Program Director in the Division of Computing and Communication Foundations, Directorate for Computer and Information Science and Engineering, US National Science Foundation, and as an Adjunct Faculty in the Department of Physics and Astronomy, the University of Waterloo, and the Institute for Quantum Computing, Canada. His research interests include quantum circuits and architectures, quantum algorithms, quantum information processing, logic synthesis, reversible logic, and circuit complexity.

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks