Facta universitatis - series Electronics and Energetics

The Fredkin gate in reversible and quantum environments

Claudio Moraga, Fatima Zohra Hadjam

Published Jan 1, 2023• 4 citations

Abstract

Reversible Computing circuits are characterized by low power consumption and their proximity to circuits for quantum computing. The Fredkin gate was one of the earliest proposed controlled reversible circuits, which however, was soon superseded by the Toffoli gate, the NOT, and CNOT gates, which constituting a flexible functionally complete set could also realize the Fredkin gate as a building block. In quantum computing circuits, the Fredkin gate (under the name controlled SWAP) plays an important role regarding the superposition of states. The present paper studies extensions of the Fredkin gate in terms of mixed polarity in the reversible domain and an application in quantum computing.

DOI: 10.2298/fuee2302253m

Related papers

Fredkin/Toffoli Templates for Reversible Logic Synthesis

Dmitri Maslov, Gerhard W. Dueck, D. Michael Miller

Abstract—Reversible logic has applications in quantum com-puting, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate (which performs a controlled NOT) and the Fredkin gate (performs a controlled swap of two inputs). Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply trans-formations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified—they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously. I.

Jan 1, 200344 citations

Shallow unitary decompositions of quantum Fredkin and Toffoli gates for connectivity-aware equivalent circuit averaging

Pedro M. Q. Cruz, Bruno Murta

The controlled-swap and controlled-controlled-not gates are at the heart of the original proposal of reversible classical computation by Fredkin and Toffoli. Their widespread use in quantum computation, both in the implementation of classical logic subroutines of quantum algorithms and in quantum schemes with no direct classical counterparts, has made it imperative early on to pursue their efficient decomposition in terms of the lower-level gate sets native to different physical platforms. Here, we add to this body of literature by providing several logically equivalent circuits for the Toffoli and Fredkin gates under all-to-all and linear qubit connectivity, the latter with two different routings for control and target qubits. Besides achieving the lowest cnot counts in the literature for all these configurations, we also demonstrate the remarkable effectiveness of the obtained decompositions at mitigating coherent errors on near-term quantum computers via equivalent circuit averaging. We first quantify the performance of the method in silico with a coherent-noise model before validating it experimentally on a superconducting quantum processor. In addition, we consider the case where the three qubits on which the Toffoli or Fredkin gates act nontrivially are not adjacent, proposing a novel scheme to reorder them that saves one cnot for every swap. This scheme also finds use in the shallow implementation of long-range cnots. Our results highlight the importance of considering different entangling gate structures and connectivity constraints when designing efficient quantum circuits.

arXiv:2305.18128APL QuantumFeb 23, 202422 citations

Fredkin/Toffoli templates for reversible logic synthesis

D. Maslov, Gerhard W. Dueck, D. Michael Miller

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the size of the circuit. Transformations are accomplished via template matching. The basis for a template is a network with m gates that realizes the identity function. If a sequence in the network to be synthesized matches more than half of a template, then a transformation that reduces the gate count can be applied. In this paper we show that Toffoli and Fredkin gates behave in a similar manner. Therefore, some gates in the templates may not need to be specified-they can match a Toffoli or a Fredkin gate. We formalize this by introducing the box gate. All templates with less than six gates are enumerated and classified. We synthesize all three input, three output reversible functions and compare our results to those obtained previously.

International Conference on Computer Aided DesignMay 13, 200421 citations

Design of a Ternary Fredkin Reversible Gate

C. Moraga

Several realizations of a reversible ternary Fredkin gate are developed based on Muthukrishnan-Stroud controlled-controlled Sum modulo 3 gates and controlled scaling gates. It is shown that under positive polarity, the proposed Fredkin gates have the expected controlled swap behaviour and that under mixed polarity, other behaviours are possible. Most introduced realizations have a lower realization complexity than realizations found in the literature.

IEEE International Conference on Microelectronics (MIEL)Oct 16, 20230 citations

A quantum Fredkin gate

Raj B. Patel, Joseph Ho, Franck Ferreyrol +2 more

Minimizing the resources required to build logic gates into useful processing circuits is key to realizing quantum computers. Although the salient features of a quantum computer have been shown in proof-of-principle experiments, difficulties in scaling quantum systems have made more complex operations intractable. This is exemplified in the classical Fredkin (controlled-SWAP) gate for which, despite theoretical proposals, no quantum analog has been realized. By adding control to the SWAP unitary, we use photonic qubit logic to demonstrate the first quantum Fredkin gate, which promises many applications in quantum information and measurement. We implement example algorithms and generate the highest-fidelity three-photon Greenberger-Horne-Zeilinger states to date. The technique we use allows one to add a control operation to a black-box unitary, something that is impossible in the standard circuit model. Our experiment represents the first use of this technique to control a two-qubit operation and paves the way for larger controlled circuits to be realized efficiently.

arXiv:1603.08086Science AdvancesMar 4, 2016158 citations

A modified Transformation-Template based Synthesis using FREDKIN/SWAP Gates in Reversible Circuits

Mousum Handique, Rijumoni Singha

Reversible logic computing is an emerging research area due to its high-speed computing abilities and generating the lossless information. Due to the ability of reverse operation and high-speed computing performance, reversible computation is considered as a future alternative to the conventional computing. The rapid progress of reversible computation in the current scenario, the reversible circuit is the way to solve this type of computation. Moreover, the reversible circuit computation is the higher level abstraction of the quantum circuit. The synthesis design of these circuits is an important aspect in the current literature. In this paper, we present our work in the field of synthesis design of a reversible circuit. In this work, we propose a modified transformation-based synthesis design using the FREDKIN/SWAP gate to reduce the quantum cost and minimizing the number of gates. To obtain this synthesis design approach, we have introduced some new templates which are defined by rules of replacing the k-CNOT/FREDKIN/SWAP gates using a template matching approach. Here, we are considering only k-CNOT ( k ≥ 1), FREDKIN and SWAP based gate in our templates. Finally, we provide our experimental results based on different benchmark reversible circuits. The experimental result has shown that the number of quantum cost and gate count are reduced using the FREDKIN/SWAP gate in the transformation-based approach with the help of proposed templates.

Procedia Computer ScienceJan 1, 20182 citations