This paper gives a simple but nontrivial set of local transformation rules for Control-NOT(CNOT)-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, S1 and S2, there is a sequence of transformations, each of them in the rule set, which changes S1 to S2. Our motivation is to use this rule set for developing a design theory for quantum circuits whose Boolean logic parts should be implemented by CNOT based circuits. As a preliminary example, we give a design procedure based on our transformation rules which reduces the cost of CNOT-based circuits.
This paper gives a simple but nontrivial set of local transformation rules for control-NOT (CNOT)-based combinatorial circuits. It is shown that this rule set is complete, namely, for any two equivalent circuits, S/sub 1/ and S/sub 2/, there is a sequence of transformations, each of them in the rule set, which changes S/sub 1/ to S/sub 2/. Our motivation is to use this rule set for developing a design theory for quantum circuits whose Boolean logic parts should be implemented by CNOT-based circuits. As a preliminary example, we give a design procedure based on the transformation rules which reduces the cost of CNOT-based circuits.
We introduce a complete transformation rule set and a minimal equation set for controlled-NOT (CNOT)-based quantum circuits. Using these rules, quantum circuits that compute the same Boolean function are reduced to a same normal form. We can thus easily check the equivalence of circuits by comparing their normal forms. By applying the Knuth-Bendix completion algorithm to a set of modified 18 equations introduced by Iwama et al. 2002 [IKY02], we obtain a complete transformation rule set (i.e., a set of transformation rules with the properties of `termination' and `confluence'). Our transformation rule set consists of 114 rules. Moreover, we found a minimal subset of equations for the initial equation set.
We introduce a complete transformation rule set and a minimal equation set for controlled-NOT (CNOT)-based quantum circuits. Using these rules, quantum circuits that compute the same Boolean function are reduced to the same normal form. We can thus easily check the equivalence of circuits by comparing their normal forms. By applying the Knuth-Bendix completion algorithm to a set of modified 18 equations introduced by Iwama et al. 2002, we obtain a complete transformation rule set (i.e., a set of transformation rules with the properties of `termination' and `confluence'). Our transformation rule set consists of 114 rules. Moreover, we discovered a minimal combination of equations for the initial equation set.
Reversible logic synthesis is a crucial component in quantum electronic design automation. While rule-based methodologies have gained prominence in reversible circuit optimization, the completeness of the transformation rule systems is a longstanding problem in this domain. In this work, we propose the first complete set of transformation rules for reversible circuits, comprising five fundamental rules: any two equivalent reversible circuits can be transformed into each other using the rules. To prove the completeness, a canonical circuit representation for reversible functions is introduced, and we show that every reversible function is computed by a unique reversible circuit in the canonical form, and any reversible circuit can be transformed into its canonical form by applying the rules.
Transformation rules play a central role in reversible circuit optimization, template-based rewriting, and equivalence checking, and establishing their completeness is a fundamental problem in reversible logic synthesis. In this work, we investigate the completeness of transformation rules for reversible circuits both with and without ancillary bits and garbage outputs. For reversible circuits without ancillary bits and garbage outputs, we introduce a refined and complete transformation rule set
RCr, obtained by replacing one rule in the rule set
RC proposed in the previous work (TCAD, 45, pp. 3711--3724, 2026) with a simpler and widely adopted transformation rule. Since all rules in
RCr are commonly used in reversible logic synthesis, this result reveals that practically adopted transformation rules are already sufficient to establish a complete rewriting framework. Based on this result, we further propose an extended rule set, denoted by
RC+, and prove its completeness for reversible circuits with ancillary bits and garbage outputs. To the best of our knowledge, this work presents the first complete transformation rule set for arbitrary reversible circuits, regardless of whether ancillary bits or garbage outputs are employed. The proposed framework establishes a theoretical foundation for circuit optimization, template generation, and equivalence checking, and may facilitate the development of automated design tools for reversible and quantum circuits.
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%.