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•10 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•1 citation

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

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•37 citations

Design and Optimization of Quantum Arithmetic Circuits for Next-Generation Quantum Systems

Yogeswari Palanisamy, Murugan Kathirvelu, G.B. Mohankumar +3 more

Quantum computing (Q-computing) is a revolutionary technology that applies quantum mechanics (QM) to implement calculations significantly quicker than traditional computers. Q-computing employs Q-bits (qubits) rather than classical bits, which can take on a superposition state, making it possible to represent both 0 and 1 at once. This distinctive property allows qubits to perform multiple calculations simultaneously, making Q computers exponentially more powerful as more qubits are added, compared to the linear scaling of classical computers. However, challenges such as qubit instability and error rates remain significant obstacles to fully realizing this potential. A vital aspect of this technology is the development of Q arithmetic circuits, which act as the foundational blocks for efficiently executing Q algorithms. Q half-adder and full-adder circuits are integral to performing fundamental arithmetic operations within Q computers. In contrast to classical adders, Q adders rely on Q gates such as Controlled NOT (CNOT) and Toffoli gates. These gates exploit Q phenomena like entanglement and superposition, allowing for more efficient computations. The Q half-adder consists of two qubits and adds two single bits, producing a carry and sum output. It utilizes the CNOT gate to compute the sum and the Toffoli gate (controlled-controlled-NOT [CCNOT]) to compute the carry. The Q full-adder builds on this, adding three qubits to produce a sum and a carry output, further increasing computational capacity. Through the entanglement of qubits, these circuits allow for more parallelism and speed compared to classical adders. Q carry-look-ahead adders (QCLAs) and Q ripple-carry adders (QRCAs) are used to perform more complex arithmetic operations based on these half-adder and full-adder structures. Q arithmetic circuits have broad applications, boosting secure key generation in cryptography, speeding up matrix operations for faster model training in machine learning, and enabling more precise, efficient image transformations in Q image processing, benefiting fields like medical imaging and computer vision.

Auerbach Publications eBooks•Feb 24, 2026•0 citations

Efficient quantum circuit implementation of the SM4 S-box

LIU JiaHong, Xiaoqing Tan, LI Ming +1 more

In recent years, the quantum circuit implementation in symmetric cryptography has attracted widespread attention. The SM4 block cipher algorithm is China's first commercial cipher standard and was accepted as an ISO/IEC international standard in 2021. S-box is the most complex component in the SM4 block cipher algorithm. This study investigates the quantum circuit implementation of the SM4 S-box. Based on the algebraic structure, using tower filed decomposition technology, the quantum circuit of the SM4 S-box is built. Based on the number of NCT gate sets, our quantum circuit requires 20 qubits, 52 Toffoli gates, 196 CNOT gates, and 13 X gates. The Toffoli depth of our circuit is 36. Compared with previous literature, the quantum circuit proposed herein requires fewer quantum resources.

Zhongguo kexue. Wulixue Lixue Tianwenxue•Dec 8, 2023•4 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.
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.
Quantum computing (Q-computing) is a revolutionary technology that applies quantum mechanics (QM) to implement calculations significantly quicker than traditional computers. Q-computing employs Q-bits (qubits) rather than classical bits, which can take on a superposition state, making it possible to represent both 0 and 1 at once. This distinctive property allows qubits to perform multiple calculations simultaneously, making Q computers exponentially more powerful as more qubits are added, compared to the linear scaling of classical computers. However, challenges such as qubit instability and error rates remain significant obstacles to fully realizing this potential. A vital aspect of this technology is the development of Q arithmetic circuits, which act as the foundational blocks for efficiently executing Q algorithms. Q half-adder and full-adder circuits are integral to performing fundamental arithmetic operations within Q computers. In contrast to classical adders, Q adders rely on Q gates such as Controlled NOT (CNOT) and Toffoli gates. These gates exploit Q phenomena like entanglement and superposition, allowing for more efficient computations. The Q half-adder consists of two qubits and adds two single bits, producing a carry and sum output. It utilizes the CNOT gate to compute the sum and the Toffoli gate (controlled-controlled-NOT [CCNOT]) to compute the carry. The Q full-adder builds on this, adding three qubits to produce a sum and a carry output, further increasing computational capacity. Through the entanglement of qubits, these circuits allow for more parallelism and speed compared to classical adders. Q carry-look-ahead adders (QCLAs) and Q ripple-carry adders (QRCAs) are used to perform more complex arithmetic operations based on these half-adder and full-adder structures. Q arithmetic circuits have broad applications, boosting secure key generation in cryptography, speeding up matrix operations for faster model training in machine learning, and enabling more precise, efficient image transformations in Q image processing, benefiting fields like medical imaging and computer vision.
In recent years, the quantum circuit implementation in symmetric cryptography has attracted widespread attention. The SM4 block cipher algorithm is China's first commercial cipher standard and was accepted as an ISO/IEC international standard in 2021. S-box is the most complex component in the SM4 block cipher algorithm. This study investigates the quantum circuit implementation of the SM4 S-box. Based on the algebraic structure, using tower filed decomposition technology, the quantum circuit of the SM4 S-box is built. Based on the number of NCT gate sets, our quantum circuit requires 20 qubits, 52 Toffoli gates, 196 CNOT gates, and 13 X gates. The Toffoli depth of our circuit is 36. Compared with previous literature, the quantum circuit proposed herein requires fewer quantum resources.