arXiv:2609.38085
Learning quantum symmetries
Isaac Holt, Sathyawageeswar Subramanian
Abstract
Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.
AI Summary
The paper studies learning symmetry subgroups of quantum objects from copies of states or oracle access. It extends the State Hidden Subgroup Problem (StateHSP), which learns exact invariance, to non-abelian groups, invariance up to phase, and projective representations. For a finite group $G$, a linear representation $R$, and a mixed state $\rho$, weak Fourier sampling recovers the normal core $C$ of the symmetry subgroup using $O((\log|\mathcal M|+\log(1/\delta))/\epsilon)$ copies, where $\mathcal M$ consists of minimal nontrivial subgroups of $G/C$, $\epsilon$ is the promised asymmetry gap, and $\delta$ is the failure probability. This yields full subgroup learning for groups whose Baer norm has polylogarithmic index, subject to efficient Fourier transforms over the required subgroups. The phase-insensitive problem seeks $S=\{g:|\operatorname{Tr}(R(g)\rho)|=1\}$. For abelian linear representations, subtracting Fourier samples reduces this to StateHSP. For projective representations of finite abelian groups, tensor-product constructions cancel cocycles; their construction is organised through free self-orthogonal linear codes. This gives efficient learning and an application to mixed-state stabiliser learning in arbitrary local qudit dimension, with an advertised $O(n)$-copy bound under the gap promise. Further reductions encode unitary symmetries in Choi states and Hamiltonian symmetries in short-time evolution; abelian unitary learning uses $O(\log|G|/\epsilon^2)$ queries. The results require exact symmetries, separation promises, and efficient controlled representations; projective learning additionally assumes an efficiently implementable gauge choice. General non-abelian learning and noise-tolerant approximate symmetry learning remain open.
We used Gemini and ChatGPT to assist with the proofs of some technical lemmas
Central claim may not hold: The efficient projective symmetry-learning algorithm assumes a known, efficiently implementable gauge transformation to bilinear cocycle form, a qualification absent from the abstract. The claimed O(n)-copy exact stabiliser-learning algorithm for arbitrary mixed states cannot hold uniformly without an asymmetry-gap assumption, because states with different exact stabilisers can be arbitrarily close. The non-abelian AnyonicSL-to-BoseSL reduction violates its target promise because incorrectly phase-labelled genuine symmetries remain modulus-one overlaps outside the proposed hidden subgroup. The unitary-to-BoseSL reduction derives only a real-part overlap bound and incorrectly asserts the absolute-value bound required by its target promise.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 50 pages, 1 figure