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:2406.01350

Realization of permutation groups by quantum circuit

Junchi Liu, Yangyang Ren, Yan Cao, Hanyi Sun, Lin Chen

Published Jun 3, 2024• 3 citations
arXivHTMLPDF

Abstract

In this paper, we exclusively utilize CNOT gates for implementing permutation groups generated by more than two elements. In Lemma 1, we recall that three CNOT gates are both necessary and sufficient to execute a two-qubit swap gate operation. Subsequently, in Lemma 2, we show that the maximum number of CNOT gates needed to carry out an n-qubit substitution operation is 3(n-1). Moving forward, our analysis in Section 3 reveals that utilizing five or fewer CNOT gates is insufficient for implementing a three-qubit swap gate corresponding to the permutation element (123). Hence six CNOT gates are both necessary and sufficient for implementing (123). This is done by employing a graph-theoretic approach to rigorously validate the results in terms of at most five CNOT gates. Using computational tools, we exhaustively explore all valid circuit diagrams containing exactly six CNOT gates to successfully execute the swap gate for (123), by explaining the equivalence classes in Remark 6 and Table 2. We conclude them in Theorem 7.To extend our analysis to the multiqubit scenario, we present the reducible and irreducible permutation elements in Definition 8. We clarify the equivalence between rows in the multi-qubit space and provide an approximate upper bound for multi-qubits to perform the aforementioned operations in Theorem 9. The comprehensive exploration of this paper aims to pave the way for further advancements in understanding quantum circuit optimization via multiple use of a specific two-qubit gate.

DOI
10.48550/arxiv.2406.01350

Related papers

Combining SWAPs and Remote CNOT Gates for Quantum Circuit Transformation

Philipp Niemann, Luca Mueller, Rolf Drechsler

Quantum computers offer enormous speed advantages over their classical counterparts. Still, optimization on quantum circuits is necessary to further increase their potential. Additionally, physical realizations of quantum computers place restrictions on quantum circuits, regarding the available quantum gates. In order to satisfy these restrictions, non-native gates need to be expressed as an equivalent cascade of natively available quantum gates which induces a mapping overhead. Two complementary approaches to this problem are to move around the qubits (using SWAP gates) or to apply so-called remote gates, i.e. pre-computed cascades of native gates which keep the qubit placement.In this paper, we explore how combinations of movements and remote gates can be employed to reduce the required overhead regarding the number of native gates as well as the circuit depth. We also discuss ways to find out which qubits to address with the movements in order to optimize these metrics. Our general evaluation is supplemented by evaluations on two IBM quantum computer architectures to show how quantum circuits can be optimized by the presented patterns.

Euromicro Conference on Digital System Design (DSD)•Sep 1, 2021•2 citations

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•387 citations

On interchanging the states of a pair of qudits

Colin Wilmott, Peter Wild

The qubit SWAP gate has been shown to be an integral component of quantum circuitry design. It permutes the states of two qubits and allows for the storage quantum information, teleportation of atomic or ionic states, and is a fundamental element in the circuit implementation of Shor's algorithm. We consider the problem of generalising the SWAP gate beyond the qubit setting. We show that quantum circuit architectures completely described by instances of the CNOT gate can not implement a transposition of a pair of qudits for dimensions $d \equiv 3 (mod 4)$. The task of constructing generalised SWAP gates based on transpositions of qudit states is argued in terms of the signature of a permutation.

arXiv:0811.1545•Nov 10, 2008•3 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•60 citations

CNOT Gate Optimizations via Qubit Permutations for IBM's Quantum Architectures

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

IBM offers a number of quantum processors on which scientist can perform experiments. All single qubit gates from the Clifford+T gate library 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 obtained with 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. Then, we propose an approach to find all the possible mappings for the missing CNOT gates. IBM's QX5 is used as target architecture. The proposed approach was compared to an algorithm that maps quantum circuits to IBM architectures. The benchmarks without optimizations techniques showed that our approach found circuits with up to 50% fewer gates and with up to 47% fewer levels. To optimize the benchmark circuits the quantum computing framework Qiskit was used. Comparing the optimized mapped circuits, our approach found circuits with up to 50% fewer gates and with up to 49% fewer levels.

Journal of Low Power Electronics•Jun 1, 2019•5 citations

Quantum circuits for incompletely specified two-qubit operators

Vivek Shende, Igor L. Markov

While the question ``how many CNOT gates are needed to simulate an arbitrary two-qubit operator'' has been conclusively answered -- three are necessary and sufficient -- previous work on this topic assumes that one wants to simulate a given unitary operator up to global phase. However, in many practical cases additional degrees of freedom are allowed. For example, if the computation is to be followed by a given projective measurement, many dissimilar operators achieve the same output distributions on all input states. Alternatively, if it is known that the input state is $\ket{0}$, the action of the given operator on all orthogonal states is immaterial. In such cases, we say that the unitary operator is incompletely specified; in this work, we take up the practical challenge of satisfying a given specification with the smallest possible circuit. In particular, we identify cases in which such operators can be implemented using fewer quantum gates than are required for generic completely specified operators.

arXiv:quant-ph/0401162•Quantum Information and Computation•Jan 1, 2005•60 citations
In this paper, we exclusively utilize CNOT gates for implementing permutation groups generated by more than two elements. In Lemma 1, we recall that three CNOT gates are both necessary and sufficient to execute a two-qubit swap gate operation. Subsequently, in Lemma 2, we show that the maximum number of CNOT gates needed to carry out an n-qubit substitution operation is 3(n-1). Moving forward, our analysis in Section 3 reveals that utilizing five or fewer CNOT gates is insufficient for implementing a three-qubit swap gate corresponding to the permutation element (123). Hence six CNOT gates are both necessary and sufficient for implementing (123). This is done by employing a graph-theoretic approach to rigorously validate the results in terms of at most five CNOT gates. Using computational tools, we exhaustively explore all valid circuit diagrams containing exactly six CNOT gates to successfully execute the swap gate for (123), by explaining the equivalence classes in Remark 6 and Table 2. We conclude them in Theorem 7.To extend our analysis to the multiqubit scenario, we present the reducible and irreducible permutation elements in Definition 8. We clarify the equivalence between rows in the multi-qubit space and provide an approximate upper bound for multi-qubits to perform the aforementioned operations in Theorem 9. The comprehensive exploration of this paper aims to pave the way for further advancements in understanding quantum circuit optimization via multiple use of a specific two-qubit gate.
Quantum computers offer enormous speed advantages over their classical counterparts. Still, optimization on quantum circuits is necessary to further increase their potential. Additionally, physical realizations of quantum computers place restrictions on quantum circuits, regarding the available quantum gates. In order to satisfy these restrictions, non-native gates need to be expressed as an equivalent cascade of natively available quantum gates which induces a mapping overhead. Two complementary approaches to this problem are to move around the qubits (using SWAP gates) or to apply so-called remote gates, i.e. pre-computed cascades of native gates which keep the qubit placement.In this paper, we explore how combinations of movements and remote gates can be employed to reduce the required overhead regarding the number of native gates as well as the circuit depth. We also discuss ways to find out which qubits to address with the movements in order to optimize these metrics. Our general evaluation is supplemented by evaluations on two IBM quantum computer architectures to show how quantum circuits can be optimized by the presented patterns.
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.
The qubit SWAP gate has been shown to be an integral component of quantum circuitry design. It permutes the states of two qubits and allows for the storage quantum information, teleportation of atomic or ionic states, and is a fundamental element in the circuit implementation of Shor's algorithm. We consider the problem of generalising the SWAP gate beyond the qubit setting. We show that quantum circuit architectures completely described by instances of the CNOT gate can not implement a transposition of a pair of qudits for dimensions d≡3(mod4)d \equiv 3 (mod 4)d≡3(mod4). The task of constructing generalised SWAP gates based on transpositions of qudit states is argued in terms of the signature of a permutation.
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.
IBM offers a number of quantum processors on which scientist can perform experiments. All single qubit gates from the Clifford+T gate library 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 obtained with 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. Then, we propose an approach to find all the possible mappings for the missing CNOT gates. IBM's QX5 is used as target architecture. The proposed approach was compared to an algorithm that maps quantum circuits to IBM architectures. The benchmarks without optimizations techniques showed that our approach found circuits with up to 50% fewer gates and with up to 47% fewer levels. To optimize the benchmark circuits the quantum computing framework Qiskit was used. Comparing the optimized mapped circuits, our approach found circuits with up to 50% fewer gates and with up to 49% fewer levels.
While the question ``how many CNOT gates are needed to simulate an arbitrary two-qubit operator'' has been conclusively answered -- three are necessary and sufficient -- previous work on this topic assumes that one wants to simulate a given unitary operator up to global phase. However, in many practical cases additional degrees of freedom are allowed. For example, if the computation is to be followed by a given projective measurement, many dissimilar operators achieve the same output distributions on all input states. Alternatively, if it is known that the input state is ∣0⟩\ket{0}∣0⟩, the action of the given operator on all orthogonal states is immaterial. In such cases, we say that the unitary operator is incompletely specified; in this work, we take up the practical challenge of satisfying a given specification with the smallest possible circuit. In particular, we identify cases in which such operators can be implemented using fewer quantum gates than are required for generic completely specified operators.