Reversible and Quantum Circuits: Optimization and Complexity Analysis

Reversible computation is a fundamental concept in quantum circuits and low-power design. As the demand for powerful and energy-efficient computing grows, novel design methods for reversible circuits become critical for achieving high performance with low power consumption. Current reversible circuit synthesis methodologies fall into two classes, each minimizing a different parameter in circuit complexity, but often result in relatively high values in another parameter. Post-synthesis optimizations moderate complexity parameters, basically by trading off between them. However, these optimizations depend on specific gate patterns and may not always meet design constraints effectively. This paper proposes a novel recursive decomposition scheme for large Boolean functions using a single-target gate model in reversible circuit synthesis. The proposed scheme systematically and efficiently manages the trade-off between reversible circuit complexity measures, offering gradually varying parameters at each level in the recursion. The scalability of the proposed approach is presented as a comprehensive complexity analysis for the mathematical model. Rather than providing a globally optimal solution, this approach offers a range of solutions, allowing designers to choose the most suitable option based on specific design constraints.Reversible computation is a fundamental concept in quantum circuits and low-power design. As the demand for powerful and energy-efficient computing grows, novel design methods for reversible circuits become critical for achieving high performance with low power consumption. Current reversible circuit synthesis methodologies fall into two classes, each minimizing a different parameter in circuit complexity, but often result in relatively high values in another parameter. Post-synthesis optimizations moderate complexity parameters, basically by trading off between them. However, these optimizations depend on specific gate patterns and may not always meet design constraints effectively. This paper proposes a novel recursive decomposition scheme for large Boolean functions using a single-target gate model in reversible circuit synthesis. The proposed scheme systematically and efficiently manages the trade-off between reversible circuit complexity measures, offering gradually varying parameters at each level in the recursion. The scalability of the proposed approach is presented as a comprehensive complexity analysis for the mathematical model. Rather than providing a globally optimal solution, this approach offers a range of solutions, allowing designers to choose the most suitable option based on specific design constraints.

Journal of Engineering and Sustainable DevelopmentNov 1, 20260 citations

Reversible and Quantum Circuit Optimization: A Functional Approach

Zahra Sasanian, D. Michael Miller

Lecture notes in computer scienceJan 1, 201329 citations

Synthesis, optimization and testing of reversible and quantum circuits

Anindita Banerjee

Jun 12, 20101 citation

Implementation and Analysis of Spin-Torque-Based Reversible D-Latch

Anant Aravind Kulkarni, Brajesh Kumar Kaushik, Željko Žilić

Quantum computing due to its ability of inherent parallel processing is emerged as one of the solutions to the complex computing problems. In connection with this, several proposals have been given for the quantum circuits-based design of the reversible combinational and sequential circuits. However, the implementation of the reversible sequential logic is challenging in comparison to the reversible combinational logic. Spin-torque-based reconfigurable architecture could be utilized to realize the quantum circuits. However, the architecture needs the optimized decomposition of the quantum circuits utilized for the reversible sequential logic due to required number of single qubit rotations and two-qubit entanglements. In this paper, the elementary decomposition of the quantum circuits representing the reversible D-Latch is optimized with the help of elementary quantum library $\{R_{\mathrm{y}}(\theta),\ R_{\mathrm{z}}(\theta),\ \sqrt{\text{SWAP}}\}$ . The number of elementary operations required to realize the D-Latch over 5 clock cycles is reduced by 43.56%. The average fidelity of the D-Latch considered for the implementation and analysis is obtained at the end of each clock cycle is well above 97%. The fidelity is further improved by approximating the present state output utilized for the next state input.Quantum computing due to its ability of inherent parallel processing is emerged as one of the solutions to the complex computing problems. In connection with this, several proposals have been given for the quantum circuits-based design of the reversible combinational and sequential circuits. However, the implementation of the reversible sequential logic is challenging in comparison to the reversible combinational logic. Spin-torque-based reconfigurable architecture could be utilized to realize the quantum circuits. However, the architecture needs the optimized decomposition of the quantum circuits utilized for the reversible sequential logic due to required number of single qubit rotations and two-qubit entanglements. In this paper, the elementary decomposition of the quantum circuits representing the reversible D-Latch is optimized with the help of elementary quantum library$\{R_{\mathrm{y}}(\theta),\ R_{\mathrm{z}}(\theta),\ \sqrt{\text{SWAP}}\}$. The number of elementary operations required to realize the D-Latch over 5 clock cycles is reduced by 43.56%. The average fidelity of the D-Latch considered for the implementation and analysis is obtained at the end of each clock cycle is well above 97%. The fidelity is further improved by approximating the present state output utilized for the next state input.

Conference proceedings - Canadian Conference on Electrical and Computer EngineeringMay 1, 20181 citation

Complexity of reversible circuits and their quantum implementations

Nabila Abdessaied, Matthew Amy, Rolf Drechsler +1 more

Theoretical Computer ScienceJan 15, 201619 citations

Quantum logic synthesis by symbolic reachability analysis

William N. N. Hung, Xiaoyu Song B, Guowu Yang +2 more

Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.Reversible quantum logic plays an important role in quantum computing. In this paper, we propose an approach to optimally synthesize quantum circuits by symbolic reachability analysis where the primary inputs are purely binary. we use symbolic reachability analysis, a technique most commonly used in model checking (a way of formal verification), to synthesize the optimum quantum circuits. We present an exact synthesis method with optimal quantum cost and a speedup method with non-optimal quantum cost. Both our methods guarantee the synthesizeability of all reversible circuits. Unlike previous works which use permutative reversible gates, we use a lower level library which includes non-permutative quantum gates. For the first time, problems in quantum logic synthesis have been reduced to those of multiple-valued logic synthesis thus reducing the search space and algorithm complexity. We synthesized quantum circuits for gate, half-adder, full-adder, etc. with the smallest cost.. Our approach obtains the minimum cost quantum circuits for Miller's gate, half-adder, and full-adder, which are better than previous results. In addition, we prove the minimum quantum cost (using our elementary quantum gates) for Fredkin, Peres, and Toffoli gates. Our work constitutes the first successful experience of applying satisfiability with formal methods to quantum logic synthesis.

ACM/IEEE Design Automation Conference (DAC)Jun 7, 200483 citations

\{R_{\mathrm{y}}(\theta),\ R_{\mathrm{z}}(\theta),\ \sqrt{\text{SWAP}}\}

. The number of elementary operations required to realize the D-Latch over 5 clock cycles is reduced by 43.56%. The average fidelity of the D-Latch considered for the implementation and analysis is obtained at the end of each clock cycle is well above 97%. The fidelity is further improved by approximating the present state output utilized for the next state input.