System and Method for Reducing CNOT Count in Clifford+T Circuits on Connectivity Constrained Architectures

The present application recognizes the problem of reducing the CNOT-count in Clifford+ T circuits on connectivity constrained architectures. Here, one can “slice” the circuit at the position of Hadamard (H) gates and “build” the intermediate portions. Two kinds of partitioning are evaluated, namely: (i) a simple method of partitioning the gates of the input circuit based on the locality of H gates, and (ii) a second method of partitioning the phase polynomial of the input circuit. The intermediate {CNOT, T} sub-circuits can be synthesized using Steiner trees, similar to the work of Nash, Gheorghiu, Mosca [NGM20] and Kissinger, de Griend [KdG19]. The following algorithms have certain procedural differences that also help to further reduce the CNOT-count. The performances of the algorithms are compared while mapping different benchmark circuits as well as random circuits to some popular architectures like 9-qubit square grid, 16-qubit square grid, Rigetti 16qubit Aspen, 16-qubit IBM QX5, ...