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:1609.08103 · Physical Review A

Quantum circuits for quantum channels

Raban Iten, Roger Colbeck, Matthias Christandl

Published May 9, 2017• 33 citations
arXivHTMLPDF

Abstract

We study the implementation of quantum channels with quantum computers while minimizing the experimental cost, measured in terms of the number of controlled-not (cnot) gates required (single-qubit gates are free). We consider three different models. In the first, the quantum circuit model (QCM), we consider sequences of single-qubit and cnot gates and allow qubits to be traced out at the end of the gate sequence. In the second (RandomQCM), we also allow external classical randomness. In the third (MeasuredQCM) we also allow measurements followed by operations that are classically controlled on the outcomes. We prove lower bounds on the number of cnot gates required and give near-optimal decompositions in almost all cases. Our main result is a MeasuredQCM circuit for any channel from $m$ qubits to $n$ qubits that uses at most one ancilla and has a low cnot count. We give explicit examples for small numbers of qubits that provide the lowest known cnot counts.

DOI
10.1103/physreva.95.052316

Related papers

Quantum circuits for isometries

Raban Iten, Roger Colbeck, Ivan Kukuljan +2 more

We consider the decomposition of arbitrary isometries into a sequence of single-qubit and controlled-not (cnot) gates. In many experimental architectures, the cnot gate is relatively costly and hence we aim to keep the number of these as low as possible. We derive a theoretical lower bound on the number of cnot gates required to decompose an arbitrary isometry from $m$ to $n$ qubits and give three explicit gate decompositions that achieve this bound up to a factor of about 2 in the leading order. We also perform some further optimizations for certain cases where $m$ and $n$ are small. In addition, we show how to apply our result for isometries to give a decomposition scheme for an arbitrary quantum operation via Stinespring's theorem and derive a lower bound on the number of cnot gates in this case too. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.

arXiv:1501.06911•Physical Review A•Mar 11, 2016•218 citations

Modelling of Grover’s quantum search algorithms: implementations of Simple quantum simulators on classical computers

Sergey Victorovich Ulyanov, Andrey G. Reshetnikov, Olga Tyatyushkina

Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.

System Analysis in Science and Education•Sep 30, 2020•4 citations

Optimizing the number of CNOT gates in one-dimensional nearest-neighbor quantum Fourier transform circuit

Byeongyong Park, Doyeol Ahn

The physical limitations of quantum hardware often require nearest-neighbor qubit structures, in which two-qubit gates are required to construct nearest-neighbor quantum circuits. However, two-qubit gates are considered a major cost of quantum circuits because of their high error rate as compared with single-qubit gates. The controlled-not (CNOT) gate is the typical choice of a two-qubit gate for universal quantum circuit implementation together with the set of single-qubit gates. In this study, we construct a one-dimensional nearest-neighbor circuit of quantum Fourier transform (QFT), which is one of the most frequently used quantum algorithms. Compared with previous studies on n-qubit one-dimensional nearest-neighbor QFT circuits, it is found that our method reduces the number of CNOT gates by ~60%. Additionally, we showed that our results for the one-dimensional nearest-neighbor circuit can be applied to quantum amplitude estimation.

arXiv:2208.14249•Aug 30, 2022•0 citations

Efficient Realizations of CNOT gates in IBM’s Quantum Computers

Alexandre A. A. de Almeida, Gerhard W. Dueck, Alexandre César Rodrigues da Silva

IBM's quantum computers implement gates from Clifford +T gate library. All single qubit gates are implemented, but only a subset of the possible CNOT are provided. It is well known that the functionally of the missing gates can be achieved by a sequence of gates. The sequence of gates is based on SWAP gates. Up to seven elementary gates are required to implement a SWAP gate. In this paper we show how the same effect can be achieved with fewer gates. To show the potential of the proposed transformations, an example is presented where a reduction of 44% in the gate count and a 26% reduction in the number of levels for IBM's QX5 computer is achieved. An algorithm that is considered state of the art, is used for the comparison.

International Symposium on Embedded Computing and System Design (ISED)•Dec 1, 2018•6 citations

Linear Decomposition of Approximate Multicontrolled Single Qubit Gates

Jefferson D. S. Silva, Thiago Melo D. Azevedo, Israel F. Araujo +1 more

We provide a method for compiling approximate multicontrolled single qubit gates into quantum circuits. Without ancilla qubits, the total number of elementary gates to decompose an n-qubit multicontrolled gate is proportional to 32n elementary operations. The proposed decomposition depends on an optimization technique that minimizes the CNOT gate count for multitarget and multicontrolled CNOT and SU(2) gates. We also provide an approximate decomposition with ancilla qubits with lower-circuit complexity. Computational experiments show the reduction of CNOT gates when multicontrolled U(2) gates are applied. As multicontrolled single-qubit gates serve as fundamental components of quantum algorithms, the proposed decomposition offers a comprehensive solution that can significantly decrease the count of elementary operations employed in quantum computing applications.

arXiv:2310.14974•IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems•Oct 1, 2024•5 citations

Constructing quantum circuits with global gates

John van de Wetering

Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.

arXiv:2012.09061•New Journal of Physics•Mar 24, 2021•37 citations
We study the implementation of quantum channels with quantum computers while minimizing the experimental cost, measured in terms of the number of controlled-not (cnot) gates required (single-qubit gates are free). We consider three different models. In the first, the quantum circuit model (QCM), we consider sequences of single-qubit and cnot gates and allow qubits to be traced out at the end of the gate sequence. In the second (RandomQCM), we also allow external classical randomness. In the third (MeasuredQCM) we also allow measurements followed by operations that are classically controlled on the outcomes. We prove lower bounds on the number of cnot gates required and give near-optimal decompositions in almost all cases. Our main result is a MeasuredQCM circuit for any channel from mmm qubits to nnn qubits that uses at most one ancilla and has a low cnot count. We give explicit examples for small numbers of qubits that provide the lowest known cnot counts.
We consider the decomposition of arbitrary isometries into a sequence of single-qubit and controlled-not (cnot) gates. In many experimental architectures, the cnot gate is relatively costly and hence we aim to keep the number of these as low as possible. We derive a theoretical lower bound on the number of cnot gates required to decompose an arbitrary isometry from mmm to nnn qubits and give three explicit gate decompositions that achieve this bound up to a factor of about 2 in the leading order. We also perform some further optimizations for certain cases where mmm and nnn are small. In addition, we show how to apply our result for isometries to give a decomposition scheme for an arbitrary quantum operation via Stinespring's theorem and derive a lower bound on the number of cnot gates in this case too. These results will have an impact on experimental efforts to build a quantum computer, enabling them to go further with the same resources.
Models of Grover’s search algorithm is reviewed to build the foundation for the other algorithms. Thereafter, some preliminary modifications of the original algorithms by others are stated, that increases the applicability of the search procedure. A general quantum computation on an isolated system can be represented by a unitary matrix. In order to execute such a computation on a quantum computer, it is common to decompose the unitary into a quantum circuit, i.e., a sequence of quantum gates that can be physically implemented on a given architecture. There are different universal gate sets for quantum computation. Here we choose the universal gate set consisting of CNOT and single-qubit gates. We measure the cost of a circuit by the number of CNOT gates as they are usually more difficult to implement than single qubit gates and since the number of single-qubit gates is bounded by about twice the number of CNOT’s.
The physical limitations of quantum hardware often require nearest-neighbor qubit structures, in which two-qubit gates are required to construct nearest-neighbor quantum circuits. However, two-qubit gates are considered a major cost of quantum circuits because of their high error rate as compared with single-qubit gates. The controlled-not (CNOT) gate is the typical choice of a two-qubit gate for universal quantum circuit implementation together with the set of single-qubit gates. In this study, we construct a one-dimensional nearest-neighbor circuit of quantum Fourier transform (QFT), which is one of the most frequently used quantum algorithms. Compared with previous studies on n-qubit one-dimensional nearest-neighbor QFT circuits, it is found that our method reduces the number of CNOT gates by ~60%. Additionally, we showed that our results for the one-dimensional nearest-neighbor circuit can be applied to quantum amplitude estimation.
IBM's quantum computers implement gates from Clifford +T gate library. All single qubit gates are implemented, but only a subset of the possible CNOT are provided. It is well known that the functionally of the missing gates can be achieved by a sequence of gates. The sequence of gates is based on SWAP gates. Up to seven elementary gates are required to implement a SWAP gate. In this paper we show how the same effect can be achieved with fewer gates. To show the potential of the proposed transformations, an example is presented where a reduction of 44% in the gate count and a 26% reduction in the number of levels for IBM's QX5 computer is achieved. An algorithm that is considered state of the art, is used for the comparison.
We provide a method for compiling approximate multicontrolled single qubit gates into quantum circuits. Without ancilla qubits, the total number of elementary gates to decompose an n-qubit multicontrolled gate is proportional to 32n elementary operations. The proposed decomposition depends on an optimization technique that minimizes the CNOT gate count for multitarget and multicontrolled CNOT and SU(2) gates. We also provide an approximate decomposition with ancilla qubits with lower-circuit complexity. Computational experiments show the reduction of CNOT gates when multicontrolled U(2) gates are applied. As multicontrolled single-qubit gates serve as fundamental components of quantum algorithms, the proposed decomposition offers a comprehensive solution that can significantly decrease the count of elementary operations employed in quantum computing applications.
Abstract There are various gate sets that can be used to describe a quantum computation. A particularly popular gate set in the literature on quantum computing consists of arbitrary single-qubit gates and two-qubit CNOT gates. A CNOT gate is however not always the natural multi-qubit interaction that can be implemented on a given physical quantum computer, necessitating a compilation step that transforms these CNOT gates to the native gate set. An especially interesting case where compilation is necessary is for ion trap quantum computers, where the natural entangling operation can act on more than two qubits and can even act globally on all qubits at once. This calls for an entirely different approach to constructing efficient circuits. In this paper we study the problem of converting a given circuit that uses two-qubit gates to one that uses global gates. Our three main contributions are as follows. First, we find an efficient algorithm for transforming an arbitrary circuit consisting of Clifford gates and arbitrary phase gates into a circuit consisting of single-qubit gates and a number of global interactions proportional to the number of non-Clifford phases present in the original circuit. Second, we find a general strategy to transform a global gate that targets all qubits into one that targets only a subset of the qubits. This approach scales linearly with the number of qubits that are not targeted, in contrast to the exponential scaling reported in (Maslov and Nam 2018 New J. Phys. 20 033018). Third, we improve on the number of global gates required to synthesise an arbitrary n-qubit Clifford circuit from the 12n − 18 reported in (Maslov and Nam 2018 New J. Phys. 20 033018) to 6n − 8.