# On the CNOT-complexity of CNOT-PHASE circuits. (arXiv:1712.01859v1 [quant-ph])

We study the problem of CNOT-optimal quantum circuit synthesis over gate sets

consisting of CNOT and $Z$-basis rotations of arbitrary angles. We show that

the circuit-polynomial correspondence relates such circuits to Fourier

expansions of pseudo-Boolean functions, and that for certain classes of

functions this expansion uniquely determines the minimum CNOT cost of an

implementation. As a corollary we prove that CNOT minimization over CNOT and

phase gates is at least as hard as synthesizing a CNOT-optimal circuit

computing a set of parities of its inputs. We then show that this problem is

NP-complete for two restricted cases where all CNOT gates are required to have

the same target, and where the circuit inputs are encoded in a larger state

space. The latter case has applications to CNOT optimization over more general

Clifford+$T$ circuits.

We further present an efficient heuristic algorithm for synthesizing circuits

over CNOT and $Z$-basis rotations with small CNOT cost. Our experiments with a

suite of benchmark circuits show 23% reduction in CNOT gates on average, with a

maximum of 48%.