Synthesis of small quantum and reversible circuits with quality guarantee

Опубликовано 28 июля 2016, 1:16

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.