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

Communication Complexity of Distributed Unitary Synthesis

Longcheng Li, Xiaoming Sun, Jialin Zhang +1 more

We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general $n$-qubit unitaries, we improve upon the trivial $O(4^n)$ communication bound. Considering $k$ pairwise-connected processors (each with $n/k$ data qubits and $m$ ancillas), we prove the communication complexity satisfies $O\left(\max\{4^{(1-1/k)n - m}, n\}\right)$ -- for example, $O(2^n)$ when $m=0$ and $k=2$ -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.

quant-pharXiv:2511.04250•IEEE Transactions on Information Theory•Nov 7, 2025•0 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•2 citations

Practical framework for simulating permutation-equivariant quantum circuits

Su Yeon Chang, Martin Larocca, M. Cerezo

Understanding which subclasses of quantum circuits are efficiently classically simulable is fundamental to delineating the boundary between classical and quantum computation. In this context, it is well known that certain tasks based on permutation-equivariant unitaries-i.e., $n$-qubit circuits whose action commutes with the qubit-permuting representation of the symmetric group $S_n$-can be simulated in polynomial time. However, existing approaches scale as $O(n^7)$, and can rapidly become prohibitively expensive. In this work, we introduce a practical algorithm for simulating $S_n$-equivariant circuits under the assumption that the gate generators are at most $k$-local, with $k\in O(1)$. The resulting method runs in $O(n^{ω+1})$ time for constant depth, where $ω$ is the matrix multiplication exponent, significantly lowering the polynomial degree compared to existing techniques. Finally, we numerically validate this scaling by simulating the dynamical evolution of the Lipkin-Meshkov-Glick model, and show that for $n=512$ spins, a standard laptop can compute the concurrence of the evolved state in under two minutes.

quant-pharXiv:2603.13072•Mar 16, 2026•0 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.
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.
We study space-bounded communication complexity for unitary implementation in distributed quantum processors, where we restrict the number of qubits per processor to ensure practical relevance and technical non-triviality. We model distributed quantum processors using distributed quantum circuits with nonlocal two-qubit gates, defining the distributed communication complexity of a unitary as the minimum number of such nonlocal gates required for its realization, up to permutations of data qubit positions. Our contributions are twofold. First, for general nnn-qubit unitaries, we improve upon the trivial O(4n)O(4^n)O(4n) communication bound. Considering kkk pairwise-connected processors (each with n/kn/kn/k data qubits and mmm ancillas), we prove the communication complexity satisfies O(max⁡{4(1−1/k)n−m,n})O\left(\max\{4^{(1-1/k)n - m}, n\}\right)O(max{4(1−1/k)n−m,n}) -- for example, O(2n)O(2^n)O(2n) when m=0m=0m=0 and k=2k=2k=2 -- and establish the tightness of this upper bound. We further extend the analysis to approximation models and general network topologies. Second, for special unitaries, we show that both the Quantum Fourier Transform (QFT) and Clifford circuits admit linear upper bounds on communication complexity in the exact model, outperforming the trivial quadratic bounds applicable to these cases. In the approximation model, QFT's communication complexity reduces drastically from linear to logarithmic, while Clifford circuits retain a linear lower bound. These results offer fundamental insights for optimizing communication in distributed quantum unitary implementation, advancing the feasibility of large-scale DQC systems.
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.
Understanding which subclasses of quantum circuits are efficiently classically simulable is fundamental to delineating the boundary between classical and quantum computation. In this context, it is well known that certain tasks based on permutation-equivariant unitaries-i.e., nnn-qubit circuits whose action commutes with the qubit-permuting representation of the symmetric group SnS_nSn​-can be simulated in polynomial time. However, existing approaches scale as O(n7)O(n^7)O(n7), and can rapidly become prohibitively expensive. In this work, we introduce a practical algorithm for simulating SnS_nSn​-equivariant circuits under the assumption that the gate generators are at most kkk-local, with k∈O(1)k\in O(1)k∈O(1). The resulting method runs in O(nω+1)O(n^{ω+1})O(nω+1) time for constant depth, where ωωω is the matrix multiplication exponent, significantly lowering the polynomial degree compared to existing techniques. Finally, we numerically validate this scaling by simulating the dynamical evolution of the Lipkin-Meshkov-Glick model, and show that for n=512n=512n=512 spins, a standard laptop can compute the concurrence of the evolved state in under two minutes.