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%.