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

Physical Review A

Optimal simulation of Deutsch gates and the Fredkin gate

Nengkun Yu, Mingsheng Ying

Published Mar 6, 2015• 38 citations
Publisher

Abstract

In this paper, we study the optimal simulation of the three-qubit unitary using two-qubit gates. First, we completely characterize the two-qubit gate cost of simulating the Deutsch gate (controlled-controlled gate) by generalizing our result on the two-qubit cost of the Toffoli gate. The function of any Deutsch gate is simply a three-qubit controlled-unitary gate and can be intuitively explained as follows: The gate outputs the states of the two control qubits directly, and applies the given one-qubit unitary $u$ on the target qubit only if both the states of the control qubits are $|1\ensuremath{\rangle}$. Previously, it was only known that five two-qubit gates are sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. We show that if the determinant of $u$ is 1, four two-qubit gates are optimal. Otherwise, five two-qubit gates are required. For the Fredkin gate (the controlled-swap gate), we prove that five two-qubit gates are necessary and sufficient, which settles the open problem introduced in Smolin and DiVincenzo [Phys. Rev. A 53, 2855 (1996)].

DOI
10.1103/physreva.91.032302

Related papers

Optimal simulation of three-qubit gates

Nengkun Yu, Mingsheng Ying

In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate. Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate. The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary $u$ on the target qubit only if both the states of the control are $\ket{1}$. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of $u$ is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.

arXiv:1301.3727•Jan 16, 2013•2 citations

Five two-qubit gates are necessary for implementing the Toffoli gate

Nengkun Yu, Runyao Duan, Mingsheng Ying

In this Rapid Communication, we consider the open problem of the minimum cost of two-qubit gates for simulating the Toffoli gate and show that five two-qubit gates are necessary. Before our work, it was known that five two-qubit gates are sufficient to implement the Toffoli gate, and numerical evidence indicates that five two-qubit gates are also necessary. The idea introduced here can also be used to solve the problem of optimal simulation of Deutsch three-qubit gates.

arXiv:1301.3372•Physical Review A•Jul 30, 2013•77 citations

Low-Cost Fredkin Gate with Auxiliary Space

Wen‐Qiang Liu, Hai‐Rui Wei, L. C. Kwek

Effective quantum information processing is tantamount in part to minimization of the quantum resources needed by quantum logic gates. Here, we propose an optimization of an $n$-controlled-qubit Fredkin gate with a maximum of $2n+1$ two-qubit gates and $2n$ single-qudit gates by exploiting auxiliary Hilbert spaces. The number of logic gates required improves on earlier results on simulating arbitrary $n$-qubit Fredkin gates. In particular, the optimal result for a one-controlled-qubit Fredkin gate (which requires three qutrit-qubit partial-swap gates) breaks the theoretical nonconstructive lower bound of five two-qubit gates. Furthermore, using an additional spatial-mode degree of freedom, we design a possible architecture to implement a polarization-encoded Fredkin gate with linear optical elements.

arXiv:2011.14713•Physical Review Applied•Nov 23, 2020•63 citations

Optimal implementation of quantum gates with two controls

Jens Palsberg, Nengkun Yu

We give a detailed proof of a well-known theorem in quantum computing. The theorem characterizes the number of two-qubit gates that is necessary for implementing three-qubit quantum gates with two controls. For example, the theorem implies that five 2-qubit gates are necessary for implementing the Toffoli gate. No detailed proof was available earlier.

Linear Algebra and its Applications•Apr 4, 2024•3 citations

Five two-bit quantum gates are sufficient to implement the quantum Fredkin gate

John A. Smolin, David Peter Divincenzo

We present an analytic construction of the three-bit quantum conditional swap (Fredkin) gate that uses only five quantum gates, each acting on only two qubits. Our implementation is based on previous work on the three-bit quantum conditional-NOT (Toffoli) gate. Numerical evidence suggests that this is a minimal implementation. \textcopyright{} 1996 The American Physical Society.

Physical Review A•Apr 1, 1996•276 citations

Practicality of time-optimal two-qubit Hamiltonian simulation

Henry L. Haselgrove, Michael A. Nielsen, Tobias J. Osborne

What is the time-optimal way of using a set of control Hamiltonians to obtain a desired interaction? Vidal, Hammerer, and Cirac [Phys. Rev. Lett. $88,$ 237902 (2002)] have obtained a set of powerful results characterizing the time-optimal simulation of a two-qubit quantum gate using a fixed interaction Hamiltonian and fast local control over the individual qubits. How practically useful are these results? We prove that there are two-qubit Hamiltonians such that time-optimal simulation requires infinitely many steps of evolution, each infinitesimally small, and thus is physically impractical. A procedure is given to determine which two-qubit Hamiltonians have this property, and we show that almost all Hamiltonians do. Finally, we determine some bounds on the penalty that must be paid in the simulation time if the number of steps is fixed at a finite number, and show that the cost in simulation time is not too great.

arXiv:quant-ph/0303070•Physical Review A•Oct 6, 2003•10 citations
In this paper, we study the optimal simulation of the three-qubit unitary using two-qubit gates. First, we completely characterize the two-qubit gate cost of simulating the Deutsch gate (controlled-controlled gate) by generalizing our result on the two-qubit cost of the Toffoli gate. The function of any Deutsch gate is simply a three-qubit controlled-unitary gate and can be intuitively explained as follows: The gate outputs the states of the two control qubits directly, and applies the given one-qubit unitary uuu on the target qubit only if both the states of the control qubits are ∣1\ensuremath⟩|1\ensuremath{\rangle}∣1\ensuremath⟩. Previously, it was only known that five two-qubit gates are sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. We show that if the determinant of uuu is 1, four two-qubit gates are optimal. Otherwise, five two-qubit gates are required. For the Fredkin gate (the controlled-swap gate), we prove that five two-qubit gates are necessary and sufficient, which settles the open problem introduced in Smolin and DiVincenzo [Phys. Rev. A 53, 2855 (1996)].
In this paper, we study the optimal simulation of three-qubit unitary by using two-qubit gates. First, we give a lower bound on the two-qubit gates cost of simulating a multi-qubit gate. Secondly, we completely characterize the two-qubit gate cost of simulating a three-qubit controlled controlled gate by generalizing our result on the cost of Toffoli gate. The function of controlled controlled gate is simply a three-qubit controlled unitary gate and can be intuitively explained as follows: the gate will output the states of the two control qubit directly, and apply the given one-qubit unitary uuu on the target qubit only if both the states of the control are ∣1⟩\ket{1}∣1⟩. Previously, it is only known that five two-qubit gates is sufficient for implementing such a gate [Sleator and Weinfurter, Phys. Rev. Lett. 74, 4087 (1995)]. Our result shows that if the determinant of uuu is 1, four two-qubit gates is achievable optimal. Otherwise, five is optimal. Thirdly, we show that five two-qubit gates are necessary and sufficient for implementing the Fredkin gate(the controlled swap gate), which settles the open problem introduced in [Smolin and DiVincenzo, Phys. Rev. A, 53, 2855 (1996)]. The Fredkin gate is one of the most important quantum logic gates because it is universal alone for classical reversible computation, and thus with little help, universal for quantum computation. Before our work, a five two-qubit gates decomposition of the Fredkin gate was already known, and numerical evidence of showing five is optimal is found.
Effective quantum information processing is tantamount in part to minimization of the quantum resources needed by quantum logic gates. Here, we propose an optimization of an nnn-controlled-qubit Fredkin gate with a maximum of 2n+12n+12n+1 two-qubit gates and 2n2n2n single-qudit gates by exploiting auxiliary Hilbert spaces. The number of logic gates required improves on earlier results on simulating arbitrary nnn-qubit Fredkin gates. In particular, the optimal result for a one-controlled-qubit Fredkin gate (which requires three qutrit-qubit partial-swap gates) breaks the theoretical nonconstructive lower bound of five two-qubit gates. Furthermore, using an additional spatial-mode degree of freedom, we design a possible architecture to implement a polarization-encoded Fredkin gate with linear optical elements.
What is the time-optimal way of using a set of control Hamiltonians to obtain a desired interaction? Vidal, Hammerer, and Cirac [Phys. Rev. Lett. 88,88,88, 237902 (2002)] have obtained a set of powerful results characterizing the time-optimal simulation of a two-qubit quantum gate using a fixed interaction Hamiltonian and fast local control over the individual qubits. How practically useful are these results? We prove that there are two-qubit Hamiltonians such that time-optimal simulation requires infinitely many steps of evolution, each infinitesimally small, and thus is physically impractical. A procedure is given to determine which two-qubit Hamiltonians have this property, and we show that almost all Hamiltonians do. Finally, we determine some bounds on the penalty that must be paid in the simulation time if the number of steps is fixed at a finite number, and show that the cost in simulation time is not too great.