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:quant-ph/0404089 · Physical Review Letters

Quantum Circuits for General Multiqubit Gates

Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, Martti M. Salomaa

Published Sep 20, 2004• 431 citations
arXivHTMLPDF

Abstract

We consider a generic elementary gate sequence which is needed to implement a general quantum gate acting on n qubits-a unitary transformation with 4(n) degrees of freedom. For synthesizing the gate sequence, a method based on the so-called cosine-sine matrix decomposition is presented. The result is optimal in the number of elementary one-qubit gates, 4(n), and scales more favorably than the previously reported decompositions requiring 4(n)-2(n+1) controlled NOT gates.

DOI
10.1103/physrevlett.93.130502

Related papers

Efficient Decomposition of Quantum Gates

Juha J. Vartiainen, Mikko Möttönen, Martti M. Salomaa

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 O(4(n)) which coincides with the theoretical lower bound.

arXiv:quant-ph/0312218•Physical Review Letters•Apr 29, 2004•256 citations

Decompositions of general quantum gates

Mikko Möttönen, Juha J. Vartiainen

Quantum algorithms may be described by sequences of unitary transformations called quantum gates and measurements applied to the quantum register of n quantum bits, qubits. A collection of quantum gates is called universal if it can be used to construct any n-qubit gate. In 1995, the universality of the set of one-qubit gates and controlled NOT gate was shown by Barenco et al. using QR decomposition of unitary matrices. Almost ten years later the decomposition was improved to include essentially fewer elementary gates. In addition, the cosine-sine matrix decomposition was applied to efficiently implement decompositions of general quantum gates. In this chapter, we review the different types of general gate decompositions and slightly improve the best known gate count for the controlled NOT gates to (23/48)4^n in the leading order. In physical realizations, the interaction strength between the qubits can decrease strongly as a function of their distance. Therefore, we also discuss decompositions with the restriction to nearest-neighbor interactions in a linear chain of qubits.

arXiv:quant-ph/0504100•Apr 14, 2005•123 citations

An arbitrary twoqubit computation In 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2003•4 citations

Optimal quantum circuits for general two-qubit gates

Farrokh Vatan, Colin P. Williams

In order to demonstrate nontrivial quantum computations experimentally, such as the synthesis of arbitrary entangled states, it will be useful to understand how to decompose a desired quantum computation into the shortest possible sequence of one-qubit and two-qubit gates. We contribute to this effort by providing a method to construct an optimal quantum circuit for a general two-qubit gate that requires at most 3 controlled-NOT (CNOT) gates and 15 elementary one-qubit gates. Moreover, if the desired two-qubit gate corresponds to a purely real unitary transformation, we provide a construction that requries at most 2 CNOT and 12 one-qubit gates. We then prove that these constructions are optimal with respect to the family of CNOT, $y$-rotation, $z$-rotation, and phase gates.

arXiv:quant-ph/0308006•Physical Review A•Mar 22, 2004•478 citations

An arbitrary twoqubit computation In 23 elementary gates or less

Stephen S. Bullock, Igor L. Markov

Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.

ACM/IEEE Design Automation Conference (DAC)•Jun 2, 2003•22 citations

From the control of quantum systems to multiqubit logic

Ville Bergholm

Quantum computing and quantum information science are two recently discovered and rapidly growing fields of physics that show substantial promise in providing new and valuable technologies in the foreseeable future. Large-scale quantum computers, if ever realized experimentally, are likely to outperform their classical counterparts in a number of important computational tasks, the most important of which may be the accurate simulation of many-body quantum systems such as the ones encountered in physics, chemistry and life sciences. This thesis investigates the problem of controlling quantum systems for the purpose of performing quantum information processing tasks. The problem is approached from a theoretical and simulational viewpoint. The work contained here encompasses a range of levels of abstraction. Firstly, we discuss the decomposition of abstract multiqubit logic gates into sequences of simple elementary gates. Secondly, we study the local commutational properties of two-qubit gates using local gate invariants. Thirdly, we develop methods for the physical implementation of the elementary gates through the control of specific quantum systems, possibly in the presence of noise and decoherence. We present a new, almost optimal n-qubit gate decomposition based on the cosine-sine decomposition, which utilizes a likewise new intermediate quantum circuit structure we call a uniformly controlled gate. We then show how they can be used in constructing a general state transformation circuit. Both of the resulting circuits can be efficiently implemented using nearest-neighbor gates which makes their physical realization simpler. A local gate invariant is introduced which can be used to assess the suitability of two-qubit gates for serving as the entangling gate in elementary gate libraries. Finally, we develop numerical optimization methods for finding near-optimal control sequences for generating oneand two-qubit gates, both in closed quantum systems and in the presence of Markovian noise.

•Dec 4, 2007•0 citations
We consider a generic elementary gate sequence which is needed to implement a general quantum gate acting on n qubits-a unitary transformation with 4(n) degrees of freedom. For synthesizing the gate sequence, a method based on the so-called cosine-sine matrix decomposition is presented. The result is optimal in the number of elementary one-qubit gates, 4(n), and scales more favorably than the previously reported decompositions requiring 4(n)-2(n+1) controlled NOT gates.
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 O(4(n)) which coincides with the theoretical lower bound.
Quantum algorithms may be described by sequences of unitary transformations called quantum gates and measurements applied to the quantum register of n quantum bits, qubits. A collection of quantum gates is called universal if it can be used to construct any n-qubit gate. In 1995, the universality of the set of one-qubit gates and controlled NOT gate was shown by Barenco et al. using QR decomposition of unitary matrices. Almost ten years later the decomposition was improved to include essentially fewer elementary gates. In addition, the cosine-sine matrix decomposition was applied to efficiently implement decompositions of general quantum gates. In this chapter, we review the different types of general gate decompositions and slightly improve the best known gate count for the controlled NOT gates to (23/48)4^n in the leading order. In physical realizations, the interaction strength between the qubits can decrease strongly as a function of their distance. Therefore, we also discuss decompositions with the restriction to nearest-neighbor interactions in a linear chain of qubits.
Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.
In order to demonstrate nontrivial quantum computations experimentally, such as the synthesis of arbitrary entangled states, it will be useful to understand how to decompose a desired quantum computation into the shortest possible sequence of one-qubit and two-qubit gates. We contribute to this effort by providing a method to construct an optimal quantum circuit for a general two-qubit gate that requires at most 3 controlled-NOT (CNOT) gates and 15 elementary one-qubit gates. Moreover, if the desired two-qubit gate corresponds to a purely real unitary transformation, we provide a construction that requries at most 2 CNOT and 12 one-qubit gates. We then prove that these constructions are optimal with respect to the family of CNOT, yyy-rotation, zzz-rotation, and phase gates.
Quantum circuits currently constitute a dominant model for quantum computation [14]. Our work addresses the problem of constructing quantum circuits to implement an arbitrary given quantum computation, in the special case of two qubits. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates [1, 9] as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 17 gates: 15 one-qubit rotations and 2 CNOTs. To this end, we constructively prove a worstcase upper bound of 23 elementary gates, of which at most 4 (CNOTs) entail multi-qubit interactions. Our analysis shows that previously known synthesis algorithms, although more general, entail much larger quantum circuits than ours in the special case of two qubits. One such algorithm [4] has a worst case of 61 gates of which 18 may be CNOTs. Our techniques rely on the KAK decomposition from Lie theory as well as the polar and spectral (symmetric Shur) matrix decompositions from numerical analysis. They are related to the canonical decomposition of a two-qubit gate with respect to the "magic basis" of phase-shifted Bell states [11, 12]. We extend this decomposition in terms of elementary gates for quantum computation.
Quantum computing and quantum information science are two recently discovered and rapidly growing fields of physics that show substantial promise in providing new and valuable technologies in the foreseeable future. Large-scale quantum computers, if ever realized experimentally, are likely to outperform their classical counterparts in a number of important computational tasks, the most important of which may be the accurate simulation of many-body quantum systems such as the ones encountered in physics, chemistry and life sciences. This thesis investigates the problem of controlling quantum systems for the purpose of performing quantum information processing tasks. The problem is approached from a theoretical and simulational viewpoint. The work contained here encompasses a range of levels of abstraction. Firstly, we discuss the decomposition of abstract multiqubit logic gates into sequences of simple elementary gates. Secondly, we study the local commutational properties of two-qubit gates using local gate invariants. Thirdly, we develop methods for the physical implementation of the elementary gates through the control of specific quantum systems, possibly in the presence of noise and decoherence. We present a new, almost optimal n-qubit gate decomposition based on the cosine-sine decomposition, which utilizes a likewise new intermediate quantum circuit structure we call a uniformly controlled gate. We then show how they can be used in constructing a general state transformation circuit. Both of the resulting circuits can be efficiently implemented using nearest-neighbor gates which makes their physical realization simpler. A local gate invariant is introduced which can be used to assess the suitability of two-qubit gates for serving as the entangling gate in elementary gate libraries. Finally, we develop numerical optimization methods for finding near-optimal control sequences for generating oneand two-qubit gates, both in closed quantum systems and in the presence of Markovian noise.