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

Quantum circuits for isometries

Raban Iten, Roger Colbeck, Ivan Kukuljan, Jonathan Home, Matthias Christandl

Published Mar 11, 2016• 218 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.93.032318

Related papers

Quantum-state preparation with universal gate decompositions

Martin Plesch, Časlav Brukner

In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of $2$. It also reduces the total number of cnot gates from ${2}^{n}$ to $\frac{23}{24}{2}^{n}$ in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from $11$ cnot gates to $9$ and the depth from $11$ to $5$ steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.

arXiv:1003.5760•Physical Review A•Mar 3, 2011•335 citations

Arbitrary two-qubit computation in 23 elementary gates

Stephen S. Bullock, Igor L. Markov

We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least $17$ gates: $15$ one-qubit rotations and $2$ controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of $23$ elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of $61$ gates, of which $18$ may be CNOT gates.

arXiv:quant-ph/0211002•Physical Review A•Jul 22, 2003•59 citations

Quantum circuits for quantum channels

Raban Iten, Roger Colbeck, Matthias Christandl

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.

arXiv:1609.08103•Physical Review A•May 9, 2017•33 citations

Optimal design of two-qubit quantum circuits

Farrokh Vatan, Colin P. Williams

In order to demonstrate non-trivial quantum computations experimentally, such as the synthesis of arbitrary entangled states, it will be useful to nderstand 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 CNOT gates and 15 elementary 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.

•Jan 5, 2004•0 citations

Quantum Circuits for Sparse Isometries

Emanuel Malvetti, Raban Iten, Roger Colbeck

We consider the task of breaking down a quantum computation given as an isometry into C-NOTs and single-qubit gates, while keeping the number of C-NOT gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.

arXiv:2006.00016•Quantum•Mar 15, 2021•48 citations

Quantum Circuits for Sparse Isometries

Emanuel Malvetti, Raban Iten, Roger Colbeck

We consider the task of breaking down a quantum computation given as an isometry into C-nots and single-qubit gates, while keeping the number of C-not gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.

•Mar 15, 2021•36 citations
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.
In quantum computation every unitary operation can be decomposed into quantum circuits---a series of single-qubit rotations and a single type entangling two-qubit gates, such as controlled-not(cnot) gates. Two measures are important when judging the complexity of the circuit: the total number of cnot gates needed to implement it and the depth of the circuit, measured by the minimal number of computation steps needed to perform it. Here we give an explicit and simple quantum circuit scheme for preparation of arbitrary quantum states, which can directly utilize any decomposition scheme for arbitrary full quantum gates, thus connecting the two problems. Our circuit reduces the depth of the best currently known circuit by a factor of 222. It also reduces the total number of cnot gates from 2n{2}^{n}2n to 23242n\frac{23}{24}{2}^{n}2423​2n in the leading order for even number of qubits. Specifically, the scheme allows us to decrease the upper bound from 111111 cnot gates to 999 and the depth from 111111 to 555 steps for four qubits. Our results are expected to help in designing and building small-scale quantum circuits using present technologies.
We address the problem of constructing quantum circuits to implement an arbitrary two-qubit quantum computation. We pursue circuits without ancilla qubits and as small a number of elementary quantum gates as possible. Our lower bound for worst-case optimal two-qubit circuits calls for at least 171717 gates: 151515 one-qubit rotations and 222 controlled-NOT (CNOT) gates. We also constructively prove a worst-case upper bound of 232323 elementary gates, of which at most four (CNOT gates) entail multiqubit interactions. Our analysis shows that synthesis algorithms suggested in previous work, although more general, entail larger quantum circuits than ours in the special case of two qubits. One such algorithm has a worst case of 616161 gates, of which 181818 may be CNOT gates.
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.
In order to demonstrate non-trivial quantum computations experimentally, such as the synthesis of arbitrary entangled states, it will be useful to nderstand 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 CNOT gates and 15 elementary 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.
We consider the task of breaking down a quantum computation given as an isometry into C-NOTs and single-qubit gates, while keeping the number of C-NOT gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.
We consider the task of breaking down a quantum computation given as an isometry into C-nots and single-qubit gates, while keeping the number of C-not gates small. Although several decompositions are known for general isometries, here we focus on a method based on Householder reflections that adapts well in the case of sparse isometries. We show how to use this method to decompose an arbitrary isometry before illustrating that the method can lead to significant improvements in the case of sparse isometries. We also discuss the classical complexity of this method and illustrate its effectiveness in the case of sparse state preparation by applying it to randomly chosen sparse states.