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

arXiv:quant-ph/0302002

Efficient Synthesis of Linear Reversible Circuits

K.N. Patel, Igor L. Markov, John P. Hayes

Published Feb 3, 2003• 28 citations
arXivHTMLPDF

Abstract

In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates. We present an algorithm that is optimal up to a multiplicative constant, as well as Theta(log n) times faster than previous methods. While our results are primarily asymptotic, simulation results show that even for relatively small n our algorithm is faster and yields more efficient circuits than the standard method. Generically our algorithm can be interpreted as a matrix decomposition algorithm, yielding an asymptotically efficient decomposition of a binary matrix into a product of elementary matrices.

DOI
10.48550/arxiv.quant-ph/0302002

Related papers

Optimal synthesis of linear reversible circuits

K.N. Patel, Igor L. Markov, J.P. Hayes

In this paper we consider circuit synthesis for $n$-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with $O\left(n^2\right)$ gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as $O\left(n^2/\log\, n\right)$ gates.

Quantum Information and Computation•Mar 1, 2008•92 citations

Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits

Timothée Goubault De Brugière, Marc Baboulin, Benoît Valiron +2 more

Linear reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. These circuits can be efficiently simulated by classical computers and their size is polynomially bounded by the number of qubits, making them a good candidate to deploy efficient methods to reduce computational costs. We propose a new algorithm for synthesizing any linear reversible operator by using an optimized version of the Gaussian elimination algorithm coupled with a tuned LU factorization. We also improve the scalability of purely greedy methods. Overall, on random operators, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes: The custom Gaussian elimination algorithm provides the best results for large problem sizes (n > 150), while the purely greedy methods provide quasi optimal results when n < 30. On a benchmark of reversible functions, we manage to significantly reduce the CNOT count and the depth of the circuit while keeping other metrics of importance (T-count, T-depth) as low as possible.

arXiv:2201.06508•ACM Transactions on Quantum Computing•Sep 30, 2021•17 citations

Reversible Logic Circuit Synthesis

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. We study circuit decompositions of reversible circuits where gates of the same type are next to each other. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

arXiv:quant-ph/0207001•Jun 28, 2002•0 citations

An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition

Hochang Lee, Kyung Chul Jeong, Daewan Han +1 more

An algorithm for reversible logic synthesis is proposed. The task is, for a given n -bit substitution map, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates with m control bits, where \(m \in \lbrace 0, \ldots , n-1\rbrace\) . Controlled gates with large m (> 2) are then further decomposed into smaller gates ( \(m \le 2\) ). A primary goal in designing the algorithm is to reduce the number of Toffoli gates, which is known to be universal. The main idea is to view an n -bit substitution map as a rank-2 n tensor and to transform it such that the resulting map can be written as a tensor product of a rank-(2 n -2) tensor and the 2× 2 identity matrix. It can then be seen that the transformed map acts nontrivially on n -1 bits only, meaning that the map to be synthesized becomes ( n -1)-bit substitution. This size reduction process is iteratively applied until it reaches a tensor product of only 2× 2 matrices. The time complexity of the algorithm is exponential in n , as most previously known heuristic algorithms for reversible logic synthesis are, but it terminates within reasonable time for not too large n , which may find practical uses. As stated earlier, our primary target is to reduce the number of Toffoli gates in the output circuit. Benchmark results show that the algorithm works well for hard benchmark functions, but it does not seem advantageous when the function is structured. As an application, the algorithm is applied to find reversible circuits for cryptographic substitution boxes, which are often required in quantum cryptanalysis.

arXiv:2107.04298•ACM Transactions on Quantum Computing•Jun 18, 2024•5 citations

Synthesis of reversible logic circuits

Vivek Shende, Aditya K. Prasad, Igor L. Markov +1 more

Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•May 29, 2003•570 citations

A Novel Efficient Optimal Reversible Circuit Synthesis Algorithm

Yu-Shan Yang, Han-Kuan Chen, Shu–Yu Kuo +2 more

In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.

Conference proceedings/Conference proceedings - IEEE International Conference on Systems, Man, and Cybernetics•Oct 1, 2015•2 citations
In this paper we consider circuit synthesis for n-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n^2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n^2/log n) gates. We present an algorithm that is optimal up to a multiplicative constant, as well as Theta(log n) times faster than previous methods. While our results are primarily asymptotic, simulation results show that even for relatively small n our algorithm is faster and yields more efficient circuits than the standard method. Generically our algorithm can be interpreted as a matrix decomposition algorithm, yielding an asymptotically efficient decomposition of a binary matrix into a product of elementary matrices.
In this paper we consider circuit synthesis for nnn-wire linear reversible circuits using the C-NOT gate library. These circuits are an important class of reversible circuits with applications to quantum computation. Previous algorithms, based on Gaussian elimination and LU-decomposition, yield circuits with O(n2)O\left(n^2\right)O(n2) gates in the worst-case. However, an information theoretic bound suggests that it may be possible to reduce this to as few as O(n2/log⁡ n)O\left(n^2/\log\, n\right)O(n2/logn) gates.
Linear reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. These circuits can be efficiently simulated by classical computers and their size is polynomially bounded by the number of qubits, making them a good candidate to deploy efficient methods to reduce computational costs. We propose a new algorithm for synthesizing any linear reversible operator by using an optimized version of the Gaussian elimination algorithm coupled with a tuned LU factorization. We also improve the scalability of purely greedy methods. Overall, on random operators, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes: The custom Gaussian elimination algorithm provides the best results for large problem sizes (n > 150), while the purely greedy methods provide quasi optimal results when n < 30. On a benchmark of reversible functions, we manage to significantly reduce the CNOT count and the depth of the circuit while keeping other metrics of importance (T-count, T-depth) as low as possible.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting distributions of circuit sizes. We study circuit decompositions of reversible circuits where gates of the same type are next to each other. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
An algorithm for reversible logic synthesis is proposed. The task is, for a given n -bit substitution map, to find a sequence of reversible logic gates that implements the map. The gate library adopted in this work consists of multiple-controlled Toffoli gates with m control bits, where m∈{0,…,n−1}m \in \lbrace 0, \ldots , n-1\rbracem∈{0,…,n−1} . Controlled gates with large m (> 2) are then further decomposed into smaller gates ( m≤2m \le 2m≤2 ). A primary goal in designing the algorithm is to reduce the number of Toffoli gates, which is known to be universal. The main idea is to view an n -bit substitution map as a rank-2 n tensor and to transform it such that the resulting map can be written as a tensor product of a rank-(2 n -2) tensor and the 2× 2 identity matrix. It can then be seen that the transformed map acts nontrivially on n -1 bits only, meaning that the map to be synthesized becomes ( n -1)-bit substitution. This size reduction process is iteratively applied until it reaches a tensor product of only 2× 2 matrices. The time complexity of the algorithm is exponential in n , as most previously known heuristic algorithms for reversible logic synthesis are, but it terminates within reasonable time for not too large n , which may find practical uses. As stated earlier, our primary target is to reduce the number of Toffoli gates in the output circuit. Benchmark results show that the algorithm works well for hard benchmark functions, but it does not seem advantageous when the function is structured. As an application, the algorithm is applied to find reversible circuits for cryptographic substitution boxes, which are often required in quantum cryptanalysis.
Reversible or information-lossless circuits have applications in digital signal processing, communication, computer graphics, and cryptography. They are also a fundamental requirement in the emerging field of quantum computation. We investigate the synthesis of reversible circuits that employ a minimum number of gates and contain no redundant input-output line-pairs (temporary storage channels). We prove constructively that every even permutation can be implemented without temporary storage using NOT, CNOT, and TOFFOLI gates. We describe an algorithm for the synthesis of optimal circuits and study the reversible functions on three wires, reporting the distribution of circuit sizes. We also study canonical circuit decompositions where gates of the same kind are grouped together. Finally, in an application important to quantum computing, we synthesize oracle circuits for Grover's search algorithm, and show a significant improvement over a previously proposed synthesis algorithm.
In quantum computing, the synthesis of reversible circuits is an important topic. Reversible circuit synthesis is particularly challenging because the complexity grows as the number of bits increases. To date, many reversible circuit synthesis algorithms have been proposed, but most are unable to find the optima within an acceptable time. Because traditional methods only consider partial interests, the resulting cost would be more gates. This paper proposes a novel method, called Bound Oriented Algorithm, which has the ability to find the optimal solution with a high hit rate, one greater than 75% on average. Moreover, with the prediction of the optima by bound, it can reduce excess calculation to further improve efficiency. In addition, a special library containing only Toffoli gates is used, which simplifies algorithm design and is more easily converted to a common library. The experiment result shows that the proposed method performs better than other methods in terms of solution quality and time cost.