Practical framework for simulating permutation-equivariant quantum circuits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908884292075520 |
|---|---|
| author | Chang, Su Yeon Larocca, Martin Cerezo, M. |
| author_facet | Chang, Su Yeon Larocca, Martin Cerezo, M. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_13072 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Practical framework for simulating permutation-equivariant quantum circuits Chang, Su Yeon Larocca, Martin Cerezo, M. Quantum Physics 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. |
| title | Practical framework for simulating permutation-equivariant quantum circuits |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2603.13072 |