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:2305.18128 · APL Quantum

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

Pedro M. Q. Cruz, Bruno Murta

Published Feb 23, 2024• 32 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1063/5.0187026

Related papers

Layout Synthesis for Quantum Circuits Considering Toffoli Gate Decomposition

Po-Wei Chen, Sheng-Tan Huang, Shao‐Yun Fang

State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.

ACM Transactions on Design Automation of Electronic Systems•Jun 16, 2025•1 citation

Efficient implementation of multi-control Toffoli gates in linear nearest neighbor arrays

Saman Daraeizadeh

Most promising implementations in quantum computing are based on Linear Nearest Neighbor (LNN) architectures, where qubits only interact with neighbors. Multi-control Toffoli gates are used in many quantum applications such as error correction and algorithms like Shor's factorization. Typically, to implement a multi-control Toffoli gate in an LNN architecture, additional operations called swap gates are required to bring the qubits adjacent to each other. This may increase the total number of quantum gates and computational overhead of the circuit. Here, we propose a new method to implement multi-control Toffoli gates in LNN arrays without using swap gates. The circuit reduction techniques discussed here are based on 3 lemmas. Using the lemmas, we show how to implement multi-control Toffoli gates in LNN arrays with different separations between the control and target qubits. The key feature of our scheme is to involve qubits other than control and target qubits to take part in gate operations. We call these qubits auxiliary qubits and they are used in our gate decomposition protocols. Auxiliary qubits can be in any arbitrary states, a|0>+beta|1> , and are always restored back to their original states. Since we do not use swap gates to bring qubits adjacent to each other, compared to circuits using swap gates, the total number of gate operations used in our method is decreased, and the quantum cost is lowered. In addition, for implementing multi-control Toffoli gate operations efficiently in LNN arrays, we also show how to extend our protocols to 2D arrays. Here, in addition to translating our gate reduction techniques, directly from 1D to 2D, we use further simplification techniques for particular arrangements of qubits.

•May 1, 2014•1 citation

The Fredkin gate in reversible and quantum environments

Claudio Moraga, Fatima Zohra Hadjam

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.

Facta universitatis - series Electronics and Energetics•Jan 1, 2023•4 citations

Efficient nnn-qubit entangling operations via a superconducting quantum router

Xuntao Wu, Haoxiong Yan, Gustav Andersson +13 more

Quantum algorithms on near-term quantum processors are typically executed using shallow quantum circuits composed of one- and two-qubit gates. However, as circuit depth and gate number increase, gate imperfections and qubit decoherence begin to dominate, limiting algorithmic complexity. An alternative approach is to explore gates involving more than two qubits. In previous work (X. Wu et al., Physical Review X 14, 041030 (2024)), we demonstrated a new superconducting qubit architecture with user-selectable two-qubit interactions via a reconfigurable router, used to connect pairs of qubits. Here, we leverage this novel architecture to realize programmable and efficient multi-qubit operations involving more than two qubits, resulting in faster preparation of multi-qubit entangled states with good fidelities. We also successfully apply model-free reinforcement learning to perform multi-qubit gates, including training a two-qubit controlled-Z gate as well as three-qubit controlled-SWAP and controlled-controlled-phase (Fredkin and Toffoli) gates. Higher $n$th-order gates may also be feasible, using our high-connectivity router design. This could provide a more efficient and higher-fidelity implementation of complex quantum algorithms and a more practical approach to quantum computation.

quant-pharXiv:2604.15432•Apr 20, 2026•1 citation

Realization of a quantum controlled-SWAP gate with photonic circuits (Conference Presentation)

Shigeki Takeuchi, Takafumi Ono, Ryo Okamoto +2 more

Quantum information science addresses how the storage, processing, and transmission of information are affected by uniquely quantum mechanical phenomena, such as superposition and entanglement. New technologies that harness these quantum effects are beginning to be realized in the areas of communication, information processing and precision measurement. For the realization of a universal gate set, by which, in principle, any quantum information task can be realized, two-qubit gates have been demonstrated and have been used to realize small-scale quantum circuits. However, scalability is becoming a critical problem. It may therefore be helpful to consider the use of three-qubit gates, which can simplify the structure of quantum circuits dramatically. Although both the controlled-SWAP (CSWAP) gate (also called Fredkin gate) and the controlled-controlled-NOT gate (also called Toffoli gate) are representative three-qubit gates, the Fredkin gates can be directly applied to many important quantum information protocols, e.g., error correction, fingerprinting, optimal cloning, and controlled entanglement filtering. Here we report a realization of the Fredkin gate using a photonic quantum circuit, following the theoretical proposal by Fiurasek. We achieve a fidelity of 0.85 for the classical truth table of CSWAP operation and an output state fidelity of 0.81 for a generated 3-photon Greenberger-Horne-Zeilinger (GHZ) state. We also confirmed that the gate is capable of genuine tripartite entanglement with a quantum coherence corresponding to a visibility of 0.69 for three-photon interferences. From these results, we estimate a process fidelity of 0.77, which indicates that our Fredkin gate can be applied to various quantum tasks.

•Dec 7, 2016•0 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.08086•Science Advances•Mar 4, 2016•160 citations
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.
State-of-the-art studies on quantum layout synthesis have proposed various approaches based on the assumption that the input circuit is only composed of single-qubit and two-qubit gates. This assumption greatly simplifies the layout synthesis problem, and thus they only require ensuring that all controlled-NOT (CNOT) gates satisfy the hardware constraints imposed by a given coupling graph. However, during the design of quantum circuits, multi-controlled Toffoli (MCT) gates are usually used to better characterize the function of the circuits. Directly decomposing them into single and two-qubit gates with a fixed routine ignores the flexibility and optimization opportunity provided by various decomposition (i.e., logic synthesis) possibilities and thus suffers from sub-optimal results. This article proposes a co-optimization approach for quantum logic and layout synthesis. The MCT gates are first decomposed into Toffoli gates, and an efficient qubit mapping checking process is proposed to optimally solve the SWAP-free layout synthesis problem by automatically determining the decomposition result of each Toffoli gate. If a SWAP-free result cannot be found, the proposed algorithm flow is then used to obtain a solution that minimizes the total cost that simultaneously counts the cost caused by the different decomposition methods for Toffoli gates and the cost induced by SWAP gates. Compared with a state-of-the-art method, the proposed approach reduces the number of additional CNOT gates by 16% with around 25X runtime speedup for the cases with SWAP-free solutions, which cannot be obtained without the co-optimization approach.
Most promising implementations in quantum computing are based on Linear Nearest Neighbor (LNN) architectures, where qubits only interact with neighbors. Multi-control Toffoli gates are used in many quantum applications such as error correction and algorithms like Shor's factorization. Typically, to implement a multi-control Toffoli gate in an LNN architecture, additional operations called swap gates are required to bring the qubits adjacent to each other. This may increase the total number of quantum gates and computational overhead of the circuit. Here, we propose a new method to implement multi-control Toffoli gates in LNN arrays without using swap gates. The circuit reduction techniques discussed here are based on 3 lemmas. Using the lemmas, we show how to implement multi-control Toffoli gates in LNN arrays with different separations between the control and target qubits. The key feature of our scheme is to involve qubits other than control and target qubits to take part in gate operations. We call these qubits auxiliary qubits and they are used in our gate decomposition protocols. Auxiliary qubits can be in any arbitrary states, a|0>+beta|1> , and are always restored back to their original states. Since we do not use swap gates to bring qubits adjacent to each other, compared to circuits using swap gates, the total number of gate operations used in our method is decreased, and the quantum cost is lowered. In addition, for implementing multi-control Toffoli gate operations efficiently in LNN arrays, we also show how to extend our protocols to 2D arrays. Here, in addition to translating our gate reduction techniques, directly from 1D to 2D, we use further simplification techniques for particular arrangements of qubits.
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.
Quantum algorithms on near-term quantum processors are typically executed using shallow quantum circuits composed of one- and two-qubit gates. However, as circuit depth and gate number increase, gate imperfections and qubit decoherence begin to dominate, limiting algorithmic complexity. An alternative approach is to explore gates involving more than two qubits. In previous work (X. Wu et al., Physical Review X 14, 041030 (2024)), we demonstrated a new superconducting qubit architecture with user-selectable two-qubit interactions via a reconfigurable router, used to connect pairs of qubits. Here, we leverage this novel architecture to realize programmable and efficient multi-qubit operations involving more than two qubits, resulting in faster preparation of multi-qubit entangled states with good fidelities. We also successfully apply model-free reinforcement learning to perform multi-qubit gates, including training a two-qubit controlled-Z gate as well as three-qubit controlled-SWAP and controlled-controlled-phase (Fredkin and Toffoli) gates. Higher nnnth-order gates may also be feasible, using our high-connectivity router design. This could provide a more efficient and higher-fidelity implementation of complex quantum algorithms and a more practical approach to quantum computation.
Quantum information science addresses how the storage, processing, and transmission of information are affected by uniquely quantum mechanical phenomena, such as superposition and entanglement. New technologies that harness these quantum effects are beginning to be realized in the areas of communication, information processing and precision measurement. For the realization of a universal gate set, by which, in principle, any quantum information task can be realized, two-qubit gates have been demonstrated and have been used to realize small-scale quantum circuits. However, scalability is becoming a critical problem. It may therefore be helpful to consider the use of three-qubit gates, which can simplify the structure of quantum circuits dramatically. Although both the controlled-SWAP (CSWAP) gate (also called Fredkin gate) and the controlled-controlled-NOT gate (also called Toffoli gate) are representative three-qubit gates, the Fredkin gates can be directly applied to many important quantum information protocols, e.g., error correction, fingerprinting, optimal cloning, and controlled entanglement filtering. Here we report a realization of the Fredkin gate using a photonic quantum circuit, following the theoretical proposal by Fiurasek. We achieve a fidelity of 0.85 for the classical truth table of CSWAP operation and an output state fidelity of 0.81 for a generated 3-photon Greenberger-Horne-Zeilinger (GHZ) state. We also confirmed that the gate is capable of genuine tripartite entanglement with a quantum coherence corresponding to a visibility of 0.69 for three-photon interferences. From these results, we estimate a process fidelity of 0.77, which indicates that our Fredkin gate can be applied to various quantum tasks.
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.