On the controlled-NOT complexity of controlled-NOT–phase circuits
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
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 show a 23% reduction of CNOT gates on average across a suite of Clifford+T benchmark circuits, with a maximum reduction of 43%.