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.07250 · Physical Review A

Toward superpolynomial quantum speedup of equivariant quantum algorithms with SU ( d ) symmetry

Han Zheng, Zimu Li, Sergii Strelchuk, Risi Kondor, Junyu Liu

Published Nov 19, 2025• 5 citations
arXivHTMLPDF

Abstract

We introduce a framework of the equivariant convolutional quantum algorithms which is tailored for a number of machine-learning tasks on physical systems with arbitrary $\mathrm{SU}(d)$ symmetries. It allows us to enhance a natural model of quantum computation---permutational quantum computing (PQC) [Jordan, Quantum Inf. Comput. 10, 470 (2010)]---and define a more powerful model: $\mathrm{PQC}+$. While PQC was shown to be efficiently classically simulatable, we exhibit a problem which can be efficiently solved on a $\mathrm{PQC}+$ machine, whereas no classical polynomial time algorithm is known, thus providing evidence against $\mathrm{PQC}+$ being classically simulatable. We further discuss practical quantum machine learning algorithms which can be carried out in the paradigm of $\mathrm{PQC}+$.

DOI
10.1103/pt27-v2nj

Related papers

Speeding Up Learning Quantum States Through Group Equivariant Convolutional Quantum Ansätze

Han Zheng, Zimu Li, Junyu Liu +2 more

We develop a theoretical framework for S n -equivariant convolutional quantum circuits with SU(d) symmetry, building on and significantly generalizing Jordan's permutational quantum computing formalism based on Schur-Weyl duality connecting both SU(d) and S n actions on qudits.In particular, we utilize the Okounkov-Vershik approach to prove Harrow's statement on the equivalence between SU(d) and S n irrep bases and to establish the S n -equivariant convolutional quantum alternating ansätze (S n -CQA) using Young-Jucys-Murphy elements.We prove that S n -CQA is able to generate any unitary in any given S n irrep sector, which may serve as a universal model for a wide array of quantum machine-learning problems with the presence of SU(d) symmetry.Our method provides another way to prove the universality of the quantum approximate optimization algorithm and verifies that four-local SU(d)-symmetric unitaries are sufficient to build generic SU(d)-symmetric quantum circuits up to relative phase factors.We present numerical simulations to showcase the effectiveness of the ansätze to find the ground-state energy of the J 1 -J 2 antiferromagnetic Heisenberg model on the rectangular and kagome lattices.Our work provides the first application of the celebrated Okounkov-Vershik S n representation theory to quantum physics and machine learning, from which to propose quantum variational ansätze that strongly suggests to be classically intractable tailored towards a specific optimization problem.

arXiv:2112.07611•PRX Quantum•May 15, 2023•48 citations

Resource-efficient equivariant quantum convolutional neural networks

Koki Chinzei, Quoc Hoan Tran, Yasuhiro Endo +1 more

Abstract Equivariant quantum neural networks (QNNs) are promising variational models that exploit symmetries to improve machine learning capabilities. Despite theoretical developments in equivariant QNNs, their implementation on near-term quantum devices remains challenging due to limited computational resources. This study proposes a resource-efficient model of equivariant quantum convolutional networks (QCNNs) called equivariant split-parallelizing QCNN (sp-QCNN). Using a group-theoretical approach, we encode general symmetries into our model beyond the translational symmetry addressed by previous sp-QCNNs. We achieve this by splitting the circuit at the pooling layer while preserving symmetry. This splitting structure effectively parallelizes QCNNs to improve measurement efficiency in estimating the expectation value of an observable and its gradient by order of the number of qubits. Our model also exhibits high trainability and generalization performance, including the absence of barren plateaus. Numerical experiments demonstrate that the equivariant sp-QCNN can be trained and generalized with fewer measurement resources than a conventional equivariant QCNN in a noisy quantum data classification task. Our results contribute to the advancement of practical quantum machine learning algorithms.

arXiv:2410.01252•Quantum Machine Intelligence•Apr 27, 2026•1 citation

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

Theory for Equivariant Quantum Neural Networks

Quynh T. Nguyen, Louis Schatzki, Paolo Braccia +5 more

Quantum neural network architectures that have little to no inductive biases are known to face trainability and generalization issues. Inspired by a similar problem, recent breakthroughs in machine learning address this challenge by creating models encoding the symmetries of the learning task. This is materialized through the usage of equivariant neural networks the action of which commutes with that of the symmetry. In this work, we import these ideas to the quantum realm by presenting a comprehensive theoretical framework to design equivariant quantum neural networks (EQNNs) for essentially any relevant symmetry group. We develop multiple methods to construct equivariant layers for EQNNs and analyze their advantages and drawbacks. Our methods can find unitary or general equivariant quantum channels efficiently even when the symmetry group is exponentially large or continuous. As a special implementation, we show how standard quantum convolutional neural networks (QCNNs) can be generalized to group-equivariant QCNNs where both the convolution and pooling layers are equivariant to the symmetry group. We then numerically demonstrate the effectiveness of a S U ( 2 ) -equivariant QCNN over symmetry-agnostic QCNN on a classification task of phases of matter in the bond-alternating Heisenberg model. Our framework can be readily applied to virtually all areas of quantum machine learning. Lastly, we discuss about how symmetry-informed models such as EQNNs provide hopes to alleviate central challenges such as barren plateaus, poor local minima, and sample complexity. Published by the American Physical Society 2024

arXiv:2210.08566•PRX Quantum•May 6, 2024•113 citations

SnCQA: A hardware-efficient equivariant quantum convolutional circuit architecture

Han Zheng, Christopher Kang, Gokul Subramanian Ravi +4 more

We propose SnCQA, a set of hardware-efficient variational circuits of equivariant quantum convolutional circuits respective to permutation symmetries and spatial lattice symmetries with the number of qubits n. By exploiting permutation symmetries of the system, such as lattice Hamiltonians common to many quantum many-body and quantum chemistry problems, Our quantum neural networks are suitable for solving machine learning problems where permutation symmetries are present, which could lead to significant savings of computational costs. Aside from its theoretical novelty, we find our simulations perform well in practical instances of learning ground states in quantum computational chemistry, where we could achieve comparable performances to traditional methods with few tens of parameters. Compared to other traditional variational quantum circuits, such as the pure hardware-efficient ansatz (pHEA), we show that SnCQA is more scalable, accurate, and noise resilient (with 20× better performance on 3 × 4 square lattice and 200% - 1000% resource savings in various lattice sizes and key criterions such as the number of layers, parameters, and times to converge in our cases), suggesting a potentially favorable experiment on near-time quantum devices.

arXiv:2211.12711•IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•8 citations

An efficient quantum algorithm for generative machine learning

Xun Gao, Zhengyu Zhang, Luming Duan

A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup. Several quantum algorithms for discriminative machine learning have been found based on efficient solving of linear algebraic problems, with potential exponential speedup in runtime under the assumption of effective input from a quantum random access memory. In machine learning, generative models represent another large class which is widely used for both supervised and unsupervised learning. Here, we propose an efficient quantum algorithm for machine learning based on a quantum generative model. We prove that our proposed model is exponentially more powerful to represent probability distributions compared with classical generative models and has exponential speedup in training and inference at least for some instances under a reasonable assumption in computational complexity theory. Our result opens a new direction for quantum machine learning and offers a remarkable example in which a quantum algorithm shows exponential improvement over any classical algorithm in an important application field.

arXiv:1711.02038•Nov 6, 2017•17 citations
We introduce a framework of the equivariant convolutional quantum algorithms which is tailored for a number of machine-learning tasks on physical systems with arbitrary SU(d)\mathrm{SU}(d)SU(d) symmetries. It allows us to enhance a natural model of quantum computation---permutational quantum computing (PQC) [Jordan, Quantum Inf. Comput. 10, 470 (2010)]---and define a more powerful model: PQC+\mathrm{PQC}+PQC+. While PQC was shown to be efficiently classically simulatable, we exhibit a problem which can be efficiently solved on a PQC+\mathrm{PQC}+PQC+ machine, whereas no classical polynomial time algorithm is known, thus providing evidence against PQC+\mathrm{PQC}+PQC+ being classically simulatable. We further discuss practical quantum machine learning algorithms which can be carried out in the paradigm of PQC+\mathrm{PQC}+PQC+.
We develop a theoretical framework for S n -equivariant convolutional quantum circuits with SU(d) symmetry, building on and significantly generalizing Jordan's permutational quantum computing formalism based on Schur-Weyl duality connecting both SU(d) and S n actions on qudits.In particular, we utilize the Okounkov-Vershik approach to prove Harrow's statement on the equivalence between SU(d) and S n irrep bases and to establish the S n -equivariant convolutional quantum alternating ansätze (S n -CQA) using Young-Jucys-Murphy elements.We prove that S n -CQA is able to generate any unitary in any given S n irrep sector, which may serve as a universal model for a wide array of quantum machine-learning problems with the presence of SU(d) symmetry.Our method provides another way to prove the universality of the quantum approximate optimization algorithm and verifies that four-local SU(d)-symmetric unitaries are sufficient to build generic SU(d)-symmetric quantum circuits up to relative phase factors.We present numerical simulations to showcase the effectiveness of the ansätze to find the ground-state energy of the J 1 -J 2 antiferromagnetic Heisenberg model on the rectangular and kagome lattices.Our work provides the first application of the celebrated Okounkov-Vershik S n representation theory to quantum physics and machine learning, from which to propose quantum variational ansätze that strongly suggests to be classically intractable tailored towards a specific optimization problem.
Abstract Equivariant quantum neural networks (QNNs) are promising variational models that exploit symmetries to improve machine learning capabilities. Despite theoretical developments in equivariant QNNs, their implementation on near-term quantum devices remains challenging due to limited computational resources. This study proposes a resource-efficient model of equivariant quantum convolutional networks (QCNNs) called equivariant split-parallelizing QCNN (sp-QCNN). Using a group-theoretical approach, we encode general symmetries into our model beyond the translational symmetry addressed by previous sp-QCNNs. We achieve this by splitting the circuit at the pooling layer while preserving symmetry. This splitting structure effectively parallelizes QCNNs to improve measurement efficiency in estimating the expectation value of an observable and its gradient by order of the number of qubits. Our model also exhibits high trainability and generalization performance, including the absence of barren plateaus. Numerical experiments demonstrate that the equivariant sp-QCNN can be trained and generalized with fewer measurement resources than a conventional equivariant QCNN in a noisy quantum data classification task. Our results contribute to the advancement of practical quantum machine learning algorithms.
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.
Quantum neural network architectures that have little to no inductive biases are known to face trainability and generalization issues. Inspired by a similar problem, recent breakthroughs in machine learning address this challenge by creating models encoding the symmetries of the learning task. This is materialized through the usage of equivariant neural networks the action of which commutes with that of the symmetry. In this work, we import these ideas to the quantum realm by presenting a comprehensive theoretical framework to design equivariant quantum neural networks (EQNNs) for essentially any relevant symmetry group. We develop multiple methods to construct equivariant layers for EQNNs and analyze their advantages and drawbacks. Our methods can find unitary or general equivariant quantum channels efficiently even when the symmetry group is exponentially large or continuous. As a special implementation, we show how standard quantum convolutional neural networks (QCNNs) can be generalized to group-equivariant QCNNs where both the convolution and pooling layers are equivariant to the symmetry group. We then numerically demonstrate the effectiveness of a S U ( 2 ) -equivariant QCNN over symmetry-agnostic QCNN on a classification task of phases of matter in the bond-alternating Heisenberg model. Our framework can be readily applied to virtually all areas of quantum machine learning. Lastly, we discuss about how symmetry-informed models such as EQNNs provide hopes to alleviate central challenges such as barren plateaus, poor local minima, and sample complexity. Published by the American Physical Society 2024
We propose SnCQA, a set of hardware-efficient variational circuits of equivariant quantum convolutional circuits respective to permutation symmetries and spatial lattice symmetries with the number of qubits n. By exploiting permutation symmetries of the system, such as lattice Hamiltonians common to many quantum many-body and quantum chemistry problems, Our quantum neural networks are suitable for solving machine learning problems where permutation symmetries are present, which could lead to significant savings of computational costs. Aside from its theoretical novelty, we find our simulations perform well in practical instances of learning ground states in quantum computational chemistry, where we could achieve comparable performances to traditional methods with few tens of parameters. Compared to other traditional variational quantum circuits, such as the pure hardware-efficient ansatz (pHEA), we show that SnCQA is more scalable, accurate, and noise resilient (with 20× better performance on 3 × 4 square lattice and 200% - 1000% resource savings in various lattice sizes and key criterions such as the number of layers, parameters, and times to converge in our cases), suggesting a potentially favorable experiment on near-time quantum devices.
A central task in the field of quantum computing is to find applications where quantum computer could provide exponential speedup over any classical computer. Machine learning represents an important field with broad applications where quantum computer may offer significant speedup. Several quantum algorithms for discriminative machine learning have been found based on efficient solving of linear algebraic problems, with potential exponential speedup in runtime under the assumption of effective input from a quantum random access memory. In machine learning, generative models represent another large class which is widely used for both supervised and unsupervised learning. Here, we propose an efficient quantum algorithm for machine learning based on a quantum generative model. We prove that our proposed model is exponentially more powerful to represent probability distributions compared with classical generative models and has exponential speedup in training and inference at least for some instances under a reasonable assumption in computational complexity theory. Our result opens a new direction for quantum machine learning and offers a remarkable example in which a quantum algorithm shows exponential improvement over any classical algorithm in an important application field.