Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM/IEEE Design Automation Conference (DAC)

Transformation rules for designing CNOT-based quantum circuits

Kazuo Iwama, Yahiko Kambayashi, Shigeru Yamashita

Published Jan 1, 2002• 39 citations
Publisher

Abstract

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.

DOI
10.1145/514022.514026

Related papers

A complete transformation rule set and a minimal equation set for CNOT-based 3 qubits quantum circuits

Issei Sakashita

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.

•Apr 1, 2013•0 citations

A complete transformation rule set and a minimal equation set for CNOT-based 3-qubit quantum circuits (Draft)

Issei Sakashita

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.

arXiv:1304.5916•Apr 22, 2013•0 citations

A Complete Set of Transformation Rules for Reversible Circuits

Shiguang Feng, Lvzhou Li

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.

arXiv:2508.17273•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Dec 8, 2025•2 citations

On the completeness of transformation rules in reversible logic synthesis

Shiguang Feng, Zongxing Xiong, Lvzhou Li

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 $\mathcal{RC}^{r}$, obtained by replacing one rule in the rule set $\mathcal{RC}$ proposed in the previous work (TCAD, 45, pp. 3711--3724, 2026) with a simpler and widely adopted transformation rule. Since all rules in $\mathcal{RC}^{r}$ 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 $\mathcal{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.

arXiv:2607.19059•Jul 21, 2026•0 citations

On the controlled-NOT complexity of controlled-NOT–phase circuits

Matthew Amy, Parsiad Azimzadeh, Michele Mosca

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

arXiv:1712.01859•Quantum Science and Technology•Aug 8, 2018•113 citations

Rotation-Based Design and Synthesis of Quantum Circuits

Mariam Zomorodi Moghadam, Keivan Navi

In this paper, a new synthesis method for Boolean irreversible functions has been proposed which is based on rotation quantum operators. The primary motivation is that the implementation of these operators is commonly available in quantum technologies. We introduce an approach for synthesizing Boolean irreversible functions in quantum logic which is based on quantum rotation and CNOT operators and uses a prespecified fixed design where by changing the rotation angles a new functionality can be achieved. So this design can be viewed as a programmable array of rotation gates. If reduction in quantum cost is desired, after this step the optimization approach may be applied to reduce the number of gates by using some rules, which leads to a reduction of up to 48% in the quantum cost after optimization compared to the original nonoptimized design obtained from the synthesis method. The paper also introduces efficient designs with rotation operators for some important gates in the quantum circuit libraries. Our main contribution is introducing a novel and low complexity approach for synthesizing irreversible functions using elementary rotation operators with a regular fixed design. Also having as many functions as desired with the same inputs, the execution time just increases by one for each additional function and the circuit width is increased by one for each additional function. It is proved that our approach can always be applied to each Boolean function. We show the correctness of our approach and make an upper bound of the quantum cost of the circuit.

Journal of Circuits Systems and Computers•Jul 25, 2016•10 citations
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.
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\mathcal{RC}^{r}RCr, obtained by replacing one rule in the rule set RC\mathcal{RC}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\mathcal{RC}^{r}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+\mathcal{RC}^+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%.
In this paper, a new synthesis method for Boolean irreversible functions has been proposed which is based on rotation quantum operators. The primary motivation is that the implementation of these operators is commonly available in quantum technologies. We introduce an approach for synthesizing Boolean irreversible functions in quantum logic which is based on quantum rotation and CNOT operators and uses a prespecified fixed design where by changing the rotation angles a new functionality can be achieved. So this design can be viewed as a programmable array of rotation gates. If reduction in quantum cost is desired, after this step the optimization approach may be applied to reduce the number of gates by using some rules, which leads to a reduction of up to 48% in the quantum cost after optimization compared to the original nonoptimized design obtained from the synthesis method. The paper also introduces efficient designs with rotation operators for some important gates in the quantum circuit libraries. Our main contribution is introducing a novel and low complexity approach for synthesizing irreversible functions using elementary rotation operators with a regular fixed design. Also having as many functions as desired with the same inputs, the execution time just increases by one for each additional function and the circuit width is increased by one for each additional function. It is proved that our approach can always be applied to each Boolean function. We show the correctness of our approach and make an upper bound of the quantum cost of the circuit.