Efficient construction of three- and four-qubit quantum gates by global entangling gates

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.