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:2207.14102 · Pure and Applied Mathematics Quarterly

Quantum complexity of permutations

Andrew T. Yu

Published Jan 1, 2023• 1 citation
arXivHTMLPDF

Abstract

Let $S_n$ be the symmetric group of all permutations of $\{1, \cdots, n\}$ with two generators: the transposition switching $1$ with $2$ and the cyclic permutation sending $k$ to $k+1$ for $1\leq k\leq n-1$ and $n$ to $1$ (denoted by $σ$ and $τ$). In this article, we study quantum complexity of permutations in $S_n$ using $\{σ, τ, τ^{-1}\}$ as logic gates. We give an explicit construction of permutations in $S_n$ with quadratic quantum complexity lower bound $\frac{n^2-2n-7}{4}$. We also prove that all permutations in $S_n$ have quadratic quantum complexity upper bound $3(n-1)^2$. Finally, we show that almost all permutations in $S_n$ have quadratic quantum complexity lower bound when $n\rightarrow \infty$.

DOI
10.4310/pamq.2023.v19.n2.a6

Related papers

Quantum circuits for permutation matrices

Jason Hanson

Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on $2^n$ letters. All circuits involve $n$ qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved.

quant-pharXiv:2512.11938•Dec 15, 2025•2 citations

Permutation Algebra for Constructing Reversible Circuits

Shah Mohammad Bahauddin, Abu Ashik Irfan

In this paper, we show that the algebra of permutation group is one of the inherent structures of reversible logic for quantum computation. In this venture, we discuss necessary properties of cycle and transposition to reveal the potential of permutation algebra for reversible logic. Then we present an efficient method which naturally interconnects the structure of reversible logic with the expression of cycle and corresponding transpositions. Finally we discuss several examples which show that the algebra can be effectively used to construct complex gates as well.

Journal of Quantum Information Science•Jan 1, 2012•3 citations

New quantum algorithms and quantum lower bounds

Andrew Chi-Chih Yao, Shengyu Zhang

The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems. We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases. Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.

•Jan 1, 2006•3 citations

Matching upper bounds on symmetric predicates in quantum communication complexity

Daiki Suruga

In this paper, we focus on the quantum communication complexity of functions of the form $f \circ G = f(G(X_1, Y_1), \ldots, G(X_n, Y_n))$ where $f: \Bset^n \to \Bset$ is a symmetric function, $G: \Bset^j \times \Bset^k \to \Bset$ is any function and Alice (resp. Bob) is given $(X_i)_{i \in [n]}$ (resp. $(Y_i)_{i \in [n]}$). Recently, Chakraborty et al. [STACS 2022] showed that the quantum communication complexity of $f \circ G$ is $O(Q(f)\QCCEX(G))$ when the parties are allowed to use shared entanglement, where $Q(f)$ is the query complexity of $f$ and $\QCCEX(G)$ is the exact communication complexity of $G$. }{In this paper, we first show that the same statement holds \emph{without both shared entanglement and shared randomness}, which generalizes their result. Based on the improved result, we next show tight upper bounds on $f \circ \mathrm{AND}_2$ for any symmetric function $f$ (where $\textrm{AND}_2 : \Bset \times \Bset \to \Bset$ denotes the 2-bit AND function) in both models: with shared entanglement and without shared entanglement. This matches the well-known lower bound by Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and improves Razborov's bound when shared entanglement is not allowed.

arXiv:2301.00370•Quantum Information and Computation•Oct 1, 2024•3 citations

Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates

Sherry Gong, Andrew Yu

In this article, we present an explicit family of invertible $n\times n$ matrices over $\mathbb Z_2$ whose CNOT and row complexity is at least $4n-\text{o}(n)$; equivalently, reducing these matrices to the identity requires at least $4n-\text{o}(n)$ elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let $G_n$ denote the permutation group generated by local logic gates acting on the set of binary strings of length $n$. We prove that $G_n$ is naturally isomorphic to the group of all invertible affine transformations of the vector space $\mathbb Z_2^n$, thus reducing the problem of estimating the quantum complexity of permutations in $G_n$ to the row reduction complexity of invertible matrices over $\mathbb Z_2$. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least $4n-\text{o}(n)$.

quant-pharXiv:2607.28598•Jul 31, 2026•2 citations

Lower bounds for the CNOT-complexity of linear reversible operators

Søren Fuglede Jørgensen

The CNOT-complexity of an invertible matrix over $\mathbb{F}_2$ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all $n \times n$ matrices is known to be $Θ(n^2 / \log n)$, no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity $3(n-1)$. We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least $4n - o(n)$, asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix $A \in \mathrm{GL}_{n}(\mathbb{F}_2)$, $n = 17167$, whose CNOT-complexity exceeds that of the cyclic permutation on $n$ symbols.

quant-pharXiv:2607.22248•Jul 27, 2026•4 citations
Let SnS_nSn​ be the symmetric group of all permutations of {1,⋯ ,n}\{1, \cdots, n\}{1,⋯,n} with two generators: the transposition switching 111 with 222 and the cyclic permutation sending kkk to k+1k+1k+1 for 1≤k≤n−11\leq k\leq n-11≤k≤n−1 and nnn to 111 (denoted by σσσ and τττ). In this article, we study quantum complexity of permutations in SnS_nSn​ using {σ,τ,τ−1}\{σ, τ, τ^{-1}\}{σ,τ,τ−1} as logic gates. We give an explicit construction of permutations in SnS_nSn​ with quadratic quantum complexity lower bound n2−2n−74\frac{n^2-2n-7}{4}4n2−2n−7​. We also prove that all permutations in SnS_nSn​ have quadratic quantum complexity upper bound 3(n−1)23(n-1)^23(n−1)2. Finally, we show that almost all permutations in SnS_nSn​ have quadratic quantum complexity lower bound when n→∞n\rightarrow \inftyn→∞.
Two different algorithms are presented for generating a quantum circuit realization of a matrix representing a permutation on 2n2^n2n letters. All circuits involve nnn qubits and only use multi--controlled Toffoli gates. The first algorithm constructs a circuit from any decomposition of the permutation into a product of transpositions, but uses one ancilla line. The second, which uses no ancillae, constructs a circuit from a decomposition into a product of transpositions that have a Hamming distance of one. We show that any permutation admits such a decomposition, and we give a strategy for reducing the number of transpositions involved.
In this paper, we show that the algebra of permutation group is one of the inherent structures of reversible logic for quantum computation. In this venture, we discuss necessary properties of cycle and transposition to reveal the potential of permutation algebra for reversible logic. Then we present an efficient method which naturally interconnects the structure of reversible logic with the expression of cycle and corresponding transpositions. Finally we discuss several examples which show that the algebra can be effectively used to construct complex gates as well.
The last decade witnessed a great surge of fruitful studies in the new paradigm of quantum computing. Remarkable progress has been made in all the areas including quantum algorithms, quantum complexity theory, quantum error-correcting code, quantum information theory, quantum cryptography and physical implementations of quantum computers. However, quantum algorithm design, probably the most important task in quantum computing, did not make as much progress as people expected. This thesis aims at both designing new quantum algorithms and studying why efficient quantum algorithms are so hard to design by proving many lower bounds on quantum query complexity for various problems. We first review (and generalize) known techniques for designing quantum algorithms and for proving quantum lower bounds. Using these techniques, we then study the quantum query complexity for many problems, including some specific problems such as Graph Matching and other natural graph properties, the general tuple search, and local search. We also study the lowest possible quantum query complexity for a class of functions as a whole, such as graph properties, circular functions, and functions invariant of a transitive permutation group, where tight results are given in all these cases. Finally for the quantum lower bounds techniques themselves, we study the main two techniques and show that they are incomparable in power. For the most widely used one, which has a lot of parameters to choose, we show limitations for it in terms of certificate complexity. This implies that we cannot use the method to prove better lower bounds for almost all known open problems in this area.
In this paper, we focus on the quantum communication complexity of functions of the form f∘G=f(G(X1,Y1),…,G(Xn,Yn))f \circ G = f(G(X_1, Y_1), \ldots, G(X_n, Y_n))f∘G=f(G(X1​,Y1​),…,G(Xn​,Yn​)) where $f: \Bset^n \to \Bset$ is a symmetric function, $G: \Bset^j \times \Bset^k \to \Bset$ is any function and Alice (resp. Bob) is given (Xi)i∈[n](X_i)_{i \in [n]}(Xi​)i∈[n]​ (resp. (Yi)i∈[n](Y_i)_{i \in [n]}(Yi​)i∈[n]​). Recently, Chakraborty et al. [STACS 2022] showed that the quantum communication complexity of f∘Gf \circ Gf∘G is $O(Q(f)\QCCEX(G))$ when the parties are allowed to use shared entanglement, where Q(f)Q(f)Q(f) is the query complexity of fff and $\QCCEX(G)$ is the exact communication complexity of GGG. }{In this paper, we first show that the same statement holds \emph{without both shared entanglement and shared randomness}, which generalizes their result. Based on the improved result, we next show tight upper bounds on f∘AND2f \circ \mathrm{AND}_2f∘AND2​ for any symmetric function fff (where $\textrm{AND}_2 : \Bset \times \Bset \to \Bset$ denotes the 2-bit AND function) in both models: with shared entanglement and without shared entanglement. This matches the well-known lower bound by Razborov~[Izv. Math. 67(1) 145, 2003] when shared entanglement is allowed and improves Razborov's bound when shared entanglement is not allowed.
Explicit Matrices over Z2\mathbb Z_2Z2​ with CNOT and Row Complexity 4n−o(n)4n-\mathrm{o}(n)4n−o(n) and Local Logic Gates
In this article, we present an explicit family of invertible n×nn\times nn×n matrices over Z2\mathbb Z_2Z2​ whose CNOT and row complexity is at least 4n−o(n)4n-\text{o}(n)4n−o(n); equivalently, reducing these matrices to the identity requires at least 4n−o(n)4n-\text{o}(n)4n−o(n) elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let GnG_nGn​ denote the permutation group generated by local logic gates acting on the set of binary strings of length nnn. We prove that GnG_nGn​ is naturally isomorphic to the group of all invertible affine transformations of the vector space Z2n\mathbb Z_2^nZ2n​, thus reducing the problem of estimating the quantum complexity of permutations in GnG_nGn​ to the row reduction complexity of invertible matrices over Z2\mathbb Z_2Z2​. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least 4n−o(n)4n-\text{o}(n)4n−o(n).
The CNOT-complexity of an invertible matrix over F2\mathbb{F}_2F2​ is the minimum number of CNOT gates needed to synthesize the corresponding linear reversible operator. While the maximum CNOT-complexity over all n×nn \times nn×n matrices is known to be Θ(n2/log⁡n)Θ(n^2 / \log n)Θ(n2/logn), no explicit family of matrices requiring a superlinear number of CNOT gates is known, and until now the hardest explicitly known family has been the cyclic permutations, with CNOT-complexity 3(n−1)3(n-1)3(n−1). We show that lower bounds for the additive complexity of not-necessarily-reversible linear operators can be lifted to the reversible setting with only a small loss. As an application, we use this to describe an explicit family of matrices, constructed from parity-check matrices of error-correcting codes, with CNOT-complexity at least 4n−o(n)4n - o(n)4n−o(n), asymptotically surpassing the cyclic permutations. Moreover, this construction yields an explicit matrix A∈GLn(F2)A \in \mathrm{GL}_{n}(\mathbb{F}_2)A∈GLn​(F2​), n=17167n = 17167n=17167, whose CNOT-complexity exceeds that of the cyclic permutation on nnn symbols.