We present improved circuits for the Toffoli gate and the control-swap (Fredkin) gate using three and four global two-qubit gates, respectively. This is a nearly double speedup compared to the conventional circuits, which require five (for Toffoli) and seven (for Fredkin) local two-qubit gates. We apply the same approach to construct the conditional four-qubit phase gate by seven global two-qubit gates. We also present construction of the Toffoli and Fredkin gates with five global gates in systems with nearest-neighbor interactions. Our constructions do not employ ancilla qubits or ancilla internal states and are particularly well suited for ion qubits and for circuit QED systems, where the entangling operations can be implemented by global addressing.
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
∣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.
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)].
We present numerical results which show how two-bit logic gates can be used in the design of a quantum computer. We show that the Toffoli gate, which is the universal gate for all classical reversible computation, can be implemented using a particular sequence of exactly five two-bit gates. An arbitrary three-bit unitary gate, which can be used to build up any arbitrary quantum computation, can be implemented exactly with six two-bit gates. The ease of implementation of any particular quantum operation is dependent upon a very nonclassical feature of the operation, its exact quantum phase factor.>
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.