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

EPJ Quantum Technology

Analysis of converting $\mathfrak{C^{0}}$-circuit into $\mathfrak{C^{*}}$-circuit

Qing-bin Luo, Lang Ding, Guowu Yang, Xiaoyu Li

Published Jan 28, 2025• 3 citations
Publisher

Abstract

A $\mathfrak{C^{*}}$ -circuit, which was proposed in Asiacypt 2022 by Huang and Sun (Advances in cryptology – ASIACRYPT 2022, pp. 614–644, 2022), can directly perform calculations with the existing quantum states, thereby reducing the use of quantum resources in quantum logic synthesis. We theoretically prove how to convert a $\mathfrak{C^{0}}$ -circuit into the corresponding $\mathfrak{C^{*}}$ -circuit through two lemmas and one theorem. The first lemma proves the interchangeability of CNOT gates and NOT gates by using the equivalence of quantum circuits. The second lemma proves that adding CNOT gates to the front of a quantum circuit whose initial states are all $|0\rangle $ s will not change the output states of the circuit. The theorem is used to describe what kind of $\mathfrak{C^{0}}$ -circuit can be transformed into $\mathfrak{C^{*}}$ -circuit, and the correctness of this transformation is proved. Our work will provide a theoretical basis for converting $\mathfrak{C^{0}}$ -circuit to $\mathfrak{C^{*}}$ -circuit. Then applying the theoretical analysis results to the multiplication over $\text{GF}(2^{8})$ , the constructed quantum circuit needs 27 Toffoli gates and 118 CNOT gates, which is 15 fewer Toffoli gates and 43 CNOT gates than the current best result. This shows that the method of constructing quantum circuits by using the conversion of $\mathfrak{C^{0}}$ -circuit to $\mathfrak{C^{*}}$ -circuit is very efficient.

DOI
10.1140/epjqt/s40507-025-00317-6

Related papers

Quantum reversible circuits for $\mathrm{GF}(2^{8})$ multiplicative inverse

Qing-bin Luo, Guowu Yang, Xiaoyu Li +1 more

Abstract The synthesis of quantum circuits for multiplicative inverse over $\operatorname{GF}(2^{8})$ GF ( 2 8 ) are discussed in this paper. We first convert the multiplicative inverse operation in $\operatorname{GF}(2^{8})$ GF ( 2 8 ) to arithmetic operations in the composite field $\operatorname{GF}((2^{4})^{2})$ GF ( ( 2 4 ) 2 ) , and then discuss the expressions of the square calculation, the inversion calculation and the multiplication calculation separately in the finite field $\operatorname{GF}(2^{4})$ GF ( 2 4 ) , where the expressions of multiplication calculation in $\operatorname{GF}(2^{4})$ GF ( 2 4 ) are given directly in $\operatorname{GF}(2^{4})$ GF ( 2 4 ) and given through being transformed into the composite field $\operatorname{GF}((2^{2})^{2})$ GF ( ( 2 2 ) 2 ) . Then the quantum circuits of these calculations are realized one by one. Finally, two quantum circuits for multiplicative inverse over $\operatorname{GF}(2^{8})$ GF ( 2 8 ) are synthesized. They both use 21 qubits, the first quantum circuit uses 55 Toffoli gates and 107 CNOT gates and the second one uses 37 Toffoli gates and 209 CNOT gates. As an example of the application of multiplication inverse, we apply these quantum circuits to the implementations of the S-box quantum circuit of the AES cryptographic algorithm. Two quantum circuits for implementing the S-box of the AES cryptographic algorithm are presented. The first quantum circuit uses 21 qubits, 55 Toffoli gates, 131 CNOT gates and 4 NOT gates and the second one uses 21 qubits, 37 Toffoli gates, 233 CNOT gates and 4 NOT gates. Through the evaluation of quantum cost, the two quantum circuits of the S-box of AES cryptographic algorithm use less quantum resources than the existing schemes.

EPJ Quantum Technology•Oct 7, 2022•11 citations

Realization of permutation groups by quantum circuit

Junchi Liu, Yangyang Ren, Yan Cao +2 more

In this paper, we exclusively utilize CNOT gates for implementing permutation groups generated by more than two elements. In Lemma 1, we recall that three CNOT gates are both necessary and sufficient to execute a two-qubit swap gate operation. Subsequently, in Lemma 2, we show that the maximum number of CNOT gates needed to carry out an n-qubit substitution operation is 3(n-1). Moving forward, our analysis in Section 3 reveals that utilizing five or fewer CNOT gates is insufficient for implementing a three-qubit swap gate corresponding to the permutation element (123). Hence six CNOT gates are both necessary and sufficient for implementing (123). This is done by employing a graph-theoretic approach to rigorously validate the results in terms of at most five CNOT gates. Using computational tools, we exhaustively explore all valid circuit diagrams containing exactly six CNOT gates to successfully execute the swap gate for (123), by explaining the equivalence classes in Remark 6 and Table 2. We conclude them in Theorem 7.To extend our analysis to the multiqubit scenario, we present the reducible and irreducible permutation elements in Definition 8. We clarify the equivalence between rows in the multi-qubit space and provide an approximate upper bound for multi-qubits to perform the aforementioned operations in Theorem 9. The comprehensive exploration of this paper aims to pave the way for further advancements in understanding quantum circuit optimization via multiple use of a specific two-qubit gate.

arXiv:2406.01350•Jun 3, 2024•3 citations

Quantum circuit syntheses of Boolean matrix multiplication using only CNOT gates

Yuanmeng Zheng, Qing-bin Luo, Qiang Li +4 more

Abstract Boolean matrices and operations on Boolean matrices have become increasingly popular in quantum computing and quantum information because they can be used to represent quantum states and the corresponding operations. In this paper, we first give a quantum circuit direct synthesis of general Boolean matrix multiplication using Toffoli gates. We assign a qubit to each element of the matrix and add Toffoli gates at the corresponding positions where the matrix elements are multiplied according to the arithmetic of matrix multiplication. For n × p dimensional matrix A multiplied by p × m dimensional matrix B, np + pm + nm qubits and at most pmn Toffoli gates are used in total. Then, an improved heuristic algorithm based on matrix Hamming distance selection of CNOT gate is proposed to synthesize the quantum circuit of a matrix, without using wire switching and SWAP gates, using only CNOT gates. The results show that our method is as good as or better than the classical synthesis. Finally, the quantum circuit of Boolean matrix multiplication with at least one invertible or full-rank matrix using only CNOT gates is given, which is divided into five cases for discussion and analysis. For n × n dimensional invertible matrix A multiplied by n × m dimensional matrix B, nm qubits and at most mn 2 CNOT gates are used in total. For n × p dimensional column full-rank matrix A multiplied by p × m dimensional matrix B, nm qubits and at most pmn CNOT gates are used in total. The results show that this method uses less quantum resources to synthesize the quantum circuit of Boolean matrix multiplication. The correctness of the quantum circuits was verified by the Aer simulator of the IBM Quantum platform.

Physica Scripta•Oct 14, 2024•1 citation

Algebraic Characterization of CNOT-Based Quantum Circuits with its Applications on Logic Synthesis

Mehdi Saeedi, Morteza Saheb Zamani, Mehdi Sedighi

The exponential speed up of quantum algorithms and the fundamental limits of current CMOS process for future design technology have directed attentions toward quantum circuits. In this paper, the matrix specification of a broad category of quantum circuits, i.e. CNOT-based circuits, are investigated. We prove that the matrix elements of CNOT-based circuits can only be zeros or ones. In addition, the columns or rows of such a matrix have exactly one element with the value of 1. Furthermore, we show that these specifications can be used to synthesize CNOT-based quantum circuits. In other words, a new scheme is introduced to convert the matrix representation into its SOP equivalent using a novel quantum-based Karnaugh map extension. We then apply a search-based method to transform the obtained SOP into a CNOT-based circuit. Experimental results prove the correctness of the proposed concept.

arXiv:0712.2963•Euromicro Conference on Digital System Design (DSD)•Aug 1, 2007•8 citations

Constructing quantum circuits with global gates

John van de Wetering

Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.

arXiv:2012.09061•New Journal of Physics•Mar 24, 2021•44 citations

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•387 citations
Analysis of converting C0\mathfrak{C^{0}}C0-circuit into C∗\mathfrak{C^{*}}C∗-circuit
A C∗\mathfrak{C^{*}}C∗ -circuit, which was proposed in Asiacypt 2022 by Huang and Sun (Advances in cryptology – ASIACRYPT 2022, pp. 614–644, 2022), can directly perform calculations with the existing quantum states, thereby reducing the use of quantum resources in quantum logic synthesis. We theoretically prove how to convert a C0\mathfrak{C^{0}}C0 -circuit into the corresponding C∗\mathfrak{C^{*}}C∗ -circuit through two lemmas and one theorem. The first lemma proves the interchangeability of CNOT gates and NOT gates by using the equivalence of quantum circuits. The second lemma proves that adding CNOT gates to the front of a quantum circuit whose initial states are all ∣0⟩|0\rangle ∣0⟩ s will not change the output states of the circuit. The theorem is used to describe what kind of C0\mathfrak{C^{0}}C0 -circuit can be transformed into C∗\mathfrak{C^{*}}C∗ -circuit, and the correctness of this transformation is proved. Our work will provide a theoretical basis for converting C0\mathfrak{C^{0}}C0 -circuit to C∗\mathfrak{C^{*}}C∗ -circuit. Then applying the theoretical analysis results to the multiplication over GF(28)\text{GF}(2^{8})GF(28) , the constructed quantum circuit needs 27 Toffoli gates and 118 CNOT gates, which is 15 fewer Toffoli gates and 43 CNOT gates than the current best result. This shows that the method of constructing quantum circuits by using the conversion of C0\mathfrak{C^{0}}C0 -circuit to C∗\mathfrak{C^{*}}C∗ -circuit is very efficient.
Quantum reversible circuits for GF(28)\mathrm{GF}(2^{8})GF(28) multiplicative inverse
Abstract The synthesis of quantum circuits for multiplicative inverse over GF⁡(28)\operatorname{GF}(2^{8})GF(28) GF ( 2 8 ) are discussed in this paper. We first convert the multiplicative inverse operation in GF⁡(28)\operatorname{GF}(2^{8})GF(28) GF ( 2 8 ) to arithmetic operations in the composite field GF⁡((24)2)\operatorname{GF}((2^{4})^{2})GF((24)2) GF ( ( 2 4 ) 2 ) , and then discuss the expressions of the square calculation, the inversion calculation and the multiplication calculation separately in the finite field GF⁡(24)\operatorname{GF}(2^{4})GF(24) GF ( 2 4 ) , where the expressions of multiplication calculation in GF⁡(24)\operatorname{GF}(2^{4})GF(24) GF ( 2 4 ) are given directly in GF⁡(24)\operatorname{GF}(2^{4})GF(24) GF ( 2 4 ) and given through being transformed into the composite field GF⁡((22)2)\operatorname{GF}((2^{2})^{2})GF((22)2) GF ( ( 2 2 ) 2 ) . Then the quantum circuits of these calculations are realized one by one. Finally, two quantum circuits for multiplicative inverse over GF⁡(28)\operatorname{GF}(2^{8})GF(28) GF ( 2 8 ) are synthesized. They both use 21 qubits, the first quantum circuit uses 55 Toffoli gates and 107 CNOT gates and the second one uses 37 Toffoli gates and 209 CNOT gates. As an example of the application of multiplication inverse, we apply these quantum circuits to the implementations of the S-box quantum circuit of the AES cryptographic algorithm. Two quantum circuits for implementing the S-box of the AES cryptographic algorithm are presented. The first quantum circuit uses 21 qubits, 55 Toffoli gates, 131 CNOT gates and 4 NOT gates and the second one uses 21 qubits, 37 Toffoli gates, 233 CNOT gates and 4 NOT gates. Through the evaluation of quantum cost, the two quantum circuits of the S-box of AES cryptographic algorithm use less quantum resources than the existing schemes.
In this paper, we exclusively utilize CNOT gates for implementing permutation groups generated by more than two elements. In Lemma 1, we recall that three CNOT gates are both necessary and sufficient to execute a two-qubit swap gate operation. Subsequently, in Lemma 2, we show that the maximum number of CNOT gates needed to carry out an n-qubit substitution operation is 3(n-1). Moving forward, our analysis in Section 3 reveals that utilizing five or fewer CNOT gates is insufficient for implementing a three-qubit swap gate corresponding to the permutation element (123). Hence six CNOT gates are both necessary and sufficient for implementing (123). This is done by employing a graph-theoretic approach to rigorously validate the results in terms of at most five CNOT gates. Using computational tools, we exhaustively explore all valid circuit diagrams containing exactly six CNOT gates to successfully execute the swap gate for (123), by explaining the equivalence classes in Remark 6 and Table 2. We conclude them in Theorem 7.To extend our analysis to the multiqubit scenario, we present the reducible and irreducible permutation elements in Definition 8. We clarify the equivalence between rows in the multi-qubit space and provide an approximate upper bound for multi-qubits to perform the aforementioned operations in Theorem 9. The comprehensive exploration of this paper aims to pave the way for further advancements in understanding quantum circuit optimization via multiple use of a specific two-qubit gate.
Abstract Boolean matrices and operations on Boolean matrices have become increasingly popular in quantum computing and quantum information because they can be used to represent quantum states and the corresponding operations. In this paper, we first give a quantum circuit direct synthesis of general Boolean matrix multiplication using Toffoli gates. We assign a qubit to each element of the matrix and add Toffoli gates at the corresponding positions where the matrix elements are multiplied according to the arithmetic of matrix multiplication. For n × p dimensional matrix A multiplied by p × m dimensional matrix B, np + pm + nm qubits and at most pmn Toffoli gates are used in total. Then, an improved heuristic algorithm based on matrix Hamming distance selection of CNOT gate is proposed to synthesize the quantum circuit of a matrix, without using wire switching and SWAP gates, using only CNOT gates. The results show that our method is as good as or better than the classical synthesis. Finally, the quantum circuit of Boolean matrix multiplication with at least one invertible or full-rank matrix using only CNOT gates is given, which is divided into five cases for discussion and analysis. For n × n dimensional invertible matrix A multiplied by n × m dimensional matrix B, nm qubits and at most mn 2 CNOT gates are used in total. For n × p dimensional column full-rank matrix A multiplied by p × m dimensional matrix B, nm qubits and at most pmn CNOT gates are used in total. The results show that this method uses less quantum resources to synthesize the quantum circuit of Boolean matrix multiplication. The correctness of the quantum circuits was verified by the Aer simulator of the IBM Quantum platform.
The exponential speed up of quantum algorithms and the fundamental limits of current CMOS process for future design technology have directed attentions toward quantum circuits. In this paper, the matrix specification of a broad category of quantum circuits, i.e. CNOT-based circuits, are investigated. We prove that the matrix elements of CNOT-based circuits can only be zeros or ones. In addition, the columns or rows of such a matrix have exactly one element with the value of 1. Furthermore, we show that these specifications can be used to synthesize CNOT-based quantum circuits. In other words, a new scheme is introduced to convert the matrix representation into its SOP equivalent using a novel quantum-based Karnaugh map extension. We then apply a search-based method to transform the obtained SOP into a CNOT-based circuit. Experimental results prove the correctness of the proposed concept.
Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.