Reversible circuits play an important role in quantum computation. The realization of reversible quantum circuits is required for any quantum computer to be universal. This paper1studies the realization and synthesis problem of reversible circuits. Using group theory, we present two sets of new 3-bit reversible logic gates, which included g1g2g3and nine complex gates, respectively. It is shown that any 3-bit reversible logic circuit is realizable by cascading NOT and Feynman gates, and at most one instance of our proposed gates. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N ≤ 2n, and the other (2n- N) input patterns will be the same as their outputs. According to a synthesis example, it demonstrates that the main results are constructive and practical than others.
By means of analyzing the equivalence relation of reversible gate logic network to permutation group,the reversible gate network cascade was converted into the cycle of symmetric group.It was verified that any neighboring 3-cycle permutation (u,s,t) could be generated by four(n-2)-CNOT gates and 2n NOT gates at least.Thus,n-digit even bivariate reversible network could be constructed with NOT and 2-CNOT gates.A constructing method of reversible network cascade was proposed by means of permutation of cycle of symmetric group.The validity of this method was verified by an example.The result showed that the network was without garbage output.Meantime,the trigger of the reversible gate was even more flexible and effective.
With increase in emphasis on low-power design and quantum computation, research in reversible logic synthesis has gained great attention. Various methods of synthesis exist in the literature, like exact synthesis, heuristic approaches, methods based on group theory, and those based on higher level representation of functions like Binary Decision Diagram (BDD). In this paper a group theory based synthesis approach for reversible circuits is presented, using both positive-control and negative-control Toffoli gates. The method uses group theoretic rules for factoring permutation cycles for synthesis. The use of both positive and negative control Toffoli gates results in reduction of total number of gates required as compared to previous methods based on group theory. Several worked out examples illustrate the advantage of the proposed approach.
Quantum computation relies on exploiting quantum mechanical phenomena, and has received significant attention in recent years. Higher-dimensional quantum systems increase the density of encoded information per computing element (e.g., qutrit for three-level system), resulting in less resource overhead. For instance, 63% reduction in the number of qutrits is possible for ternary quantum systems as compared to the corresponding binary systems. The proposed work exploits this fact to synthesize ternary reversible circuits employing a cycle-based technique. The method starts from the ternary reversible specification of a given function in the form of a permutation. The permutation cycles are factored into simpler three-cycles and two-cycles, which are then mapped to ternary reversible gates. Different gate libraries are used to synthesize three-cycles and two-cycles, respectively. A gate decomposition approach is also proposed to synthesize a quantum gate netlist in terms of elementary ternary quantum gates, viz. Muthukrishnan–Stroud gate and shift gate. Synthesis results on benchmark functions indicate that the proposed method results in 27% and 6% improvements in quantum cost and gate count, respectively, over existing works in the literature.
Quantum reversible logic circuits synthesis is one of the key technologies to construct quantum computer. The algebraic model for quantum information processing is a unitary matrix operator. Matrix can better reflect the quantum state evolution and the properties of quantum computation. Bidirectional matrix-based algorithm for quantum reversible logic circuits synthesis is proposed in this paper. The matrix representation of quantum reversible circuit and the circuit transformation rules of adjacent matrix are employed to construct any quantum reversible circuit in this paper. Compared with, the computational complexity of our algorithm has been decreased exponentially and the speed has been increased by about 105times. In addition, the types of the quantum reversible circuits synthesized by our algorithm are extended from only even permutations in to even and odd ones. we have synthesized 13!=6227020800 quantum reversible circuits, which can't be done by other algorithms.
Classical reversible circuits, acting on
w~bits, are represented by permutation matrices of size
2w×2w. Those matrices form the group P(
2w), isomorphic to the symmetric group {\bf S}
2w. The permutation group P(
n), isomorphic to {\bf S}
n, contains cycles with length~
p, ranging from~1 to
L(n), where
L(n) is the so-called Landau function. By Lagrange interpolation between the
p~matrices of the cycle, we step from a finite cyclic group of order~
p to a 1-dimensional Lie group, subgroup of the unitary group U(
n). As U(
2w) is the group of all possible quantum circuits, acting on
w~qubits, such interpolation is a natural way to step from classical computation to quantum computation.