Optimal implementation of quantum gates is crucial for designing a quantum computer. We consider the matrix representation of an arbitrary multiqubit gate. By ordering the basis vectors using the Gray code, we construct the quantum circuit which is optimal in the sense of fully controlled single-qubit gates and yet is equivalent with the multiqubit gate. In the second step of the optimization, superfluous control bits are eliminated, which eventually results in a smaller total number of the elementary gates. In our scheme the number of controlled NOT gates is O4 n which coincides with the theoretical lower bound. DOI: 10.1103/PhysRevLett.92.177902 PACS numbers: 03.67.Lx, 03.65.Fd Since the early proposal of a quantum-mechanical computer [1], quantum superposition and entanglement has been discovered to be potentially useful for computing. For example, Shor's integer factorization [2] and Grover's database search [3] show considerable speedup compared to the known classical algorithms. Moreover, the framework of quantum computing can be used to describe intriguing entanglement-related phenomena, such as quantum teleportation and quantum cryptography. Quantum circuits [4] provide a method to implement an arbitrary quantum algorithm. The building blocks of quantum circuits are quantum gates, i.e., unitary transformations acting on a set of qubits. It has previously been shown that a general quantum gate can be simulated exactly [5] [6] [7] or approximately [8,9] using a quantum circuit built of elementary gates which operate only on one and two qubits. Some individual gates operating on n qubits, such as the quantum Fourier transform, reduce to a polynomial number of elementary gates in n. Unfortunately, this is not the case for an arbitrary n-qubit gate, i.e., a unitary operation having 4 n degrees of freedom. From the practical point of view, the maximum coherent operation time of the quantum computer is limited by undesirable interactions with the environment, i.e., decoherence. On the other hand, the number of the elementary gates involved in the decomposition governs the execution time of the quantum algorithm. Hence the complexity of these quantum-circuit constructions is of great interest. The conventional approach of reducing an arbitrary n-qubit gate into elementary gates is given in Ref. [5] and studied with the help of examples in Refs. [10, 11] . The main idea is to decompose the unitary matrix U, which represents the quantum gate, into two-level matrices and to find a sequence of C nÿ1 V and C nÿ1 NOT gates which implements each of them. Here we refer with C k V to the one-qubit gate V having k control bits. The control bits, each of which has the value zero or one, specify the subspace in which the gate V operates. This 2 nÿk -dimensional subspace consists of those basis vectors for which the values of the controlled qubits match with those of the control bits. In this approach, a number of C nÿ1 NOT gates is required to change the computational basis, such that the two-level matrix under consideration represents the desired C nÿ1 V gate. For the purpose of their physical implementation, all the C nÿ1 V gates can be further decomposed into a sequence of elementary gates, for instance, using the quantum circuit of Ref. [5] . For the simulation of a C nÿ1 NOT or C nÿ1 V gate, a quantum circuit of On 2 elementary gates is required while C nÿ1 W requires only On gates, provided that W is unimodular. In Ref. [5], it was considered that since On C nÿ1 NOT gates are needed between each of the O4 n C nÿ1 V gates, the total circuit complexity is On 3 4 n . It has recently been shown with the help of palindromic optimization [12] , that the number of C nÿ1 NOT gates required in the simulation can be reduced to O4 n which results in circuit complexity On 2 4 n .A constructive upper bound for the optimal circuit complexity has been reported [9] to be On4 n [13] which may also be achieved by combining the previous results [5, 12] with the fact that C nÿ1 NOT gates may be replaced with proper controlled NOT (CNOT) gates upon changing the computational basis [11] . The theoretical lower bound [14] for the number of CNOT gates needed to simulate an arbitrary quantum gate is d4 n ÿ 3n ÿ 1=4e. However, no circuit construction yielding a complexity less than On4 n has been reported, nor could be trivially combined from the previous results. In this Letter, we show how to construct a quantum circuit equivalent to an arbitrary n-qubit gate. The circuit obtained has complexity O4 n which scales according to the predicted theoretical lower bound. The scheme utilizes the reordering of the basis vectors, i.e., instead of labeling the basis vectors through the binary coding, we rather employ Gray codes [15] . The special property of any Gray code basis (GCB) is that only 1 bit changes between the adjacent basis vectors. Hence no C nÿ1 NOT gates are needed in the decomposition. Furthermore, we find that only a small fraction of the control bits appears to be essential for the final result of the decomposition.
In the literature of quantum computing, a Givens rotation is commonly referred to as a twolevel unitary matrix; a generic n-qubit unitary operator can be factorized in such two-level matrices with O (4 n ) elementary quantum gates REF ).
Efficient Decomposition of Quantum Gates
Physical review letters
Physical review letters
Medicine Physics