On the CNOT-complexity of CNOT-PHASE circuits

Understand

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.