Toward Super-polynomial Quantum Speedup of Equivariant Quantum Algorithms with SU($d$) Symmetry
This work addresses the challenge of achieving quantum advantage in machine learning for physical systems with symmetries, though it appears incremental as it builds upon existing permutational quantum computing.
The authors tackled the problem of enhancing quantum algorithms for machine learning tasks on systems with SU(d) symmetries by introducing an equivariant convolutional framework, resulting in a new model called PQC+ that shows evidence of super-polynomial quantum speedup over classical methods for a specific problem.
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)$ symmetries. It allows us to enhance a natural model of quantum computation -- permutational quantum computing (PQC) -- and define a more powerful model: PQC+. While PQC was shown to be efficiently classically simulatable, we exhibit a problem which can be efficiently solved on PQC+ machine, whereas no classical polynomial time algorithm is known; thus providing evidence against PQC+ being classically simulatable. We further discuss practical quantum machine learning algorithms which can be carried out in the paradigm of PQC+.