Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups

Polynomial-Time Quantum Algorithm for Symmetric-Group Hidden Subgroups

Definitions and mathematical statement

Let $S_n$ be the group of permutations of $\{1,\ldots,n\}$. In the hidden-subgroup model an oracle $f:S_n\to\mathcal Y$ satisfies $f(g)=f(g')$ exactly when $gH=g'H$ for an unknown subgroup $H\le S_n$. Quantum access means coherent evaluation of an encoded $f$. Recovering $H$ means outputting a generating set, with the bounded success probability and oracle encoding conventions of the cited model. The requested algorithm must use time polynomial in $n$ (equivalently polynomial in the standard permutation encoding size), including oracle calls and ordinary quantum computation. Query bounds alone, or an algorithm for only special hidden subgroups, do not supply the all-subgroups polynomial-time target. Explicitly listing every element of $H$ is not required.

Formulation and concept references: [S1].

Short English statement

Can a quantum algorithm efficiently recover an arbitrary subgroup of a symmetric group from an oracle that labels its cosets?

Research attempt

Current frontier.

The defining source's Section 6 gives the coset-oracle problem and distinguishes the symmetric-group difficulty from abelian Fourier sampling [S1]. Polynomial query complexity is known for arbitrary finite groups, but this is not a polynomial-time algorithm [E1]. The coset-state limitations for graph isomorphism require collective information from $\Omega(n\log n)$ registers in a relevant involution family [E2]. The 2025 survey continues to distinguish these information-theoretic and algorithmic issues [E3]. Its existence, and recent algorithms for other variants of HSP, do not establish the all-subgroups $S_n$ target.

Attack route.

The promising route is collective measurement followed by efficient subgroup reconstruction. Two shortcuts merit testing: distinguish hidden subgroups through purity, or implement a joint measurement after a polynomial number of samples. The first can be analyzed exactly. For the second, a sufficient missing lemma would give polynomial-size circuits for a separating measurement on polynomially many coset states uniformly over all $H\le S_n$, together with polynomial-time decoding to generators. Existence of a positive operator-valued measurement does not provide those circuits.

Attempt.

Let $G$ be finite, $N=|G|$, and use the orthonormal basis $|g\rangle$. Let $R_h|g\rangle=|gh^{-1}\rangle$. Tracing out a coset label from the uniform oracle state yields \begin{equation}\label{wsref-0-65-71-31-38-35-3a-72-68-6f} \rho_H=\frac1N\sum_{h\in H}R_h=\frac{|H|}{N}P_H, \qquad P_H^2=P_H=P_H^*. \end{equation} The inverse in the right regular action does not change the sum over a subgroup. Since $\operatorname{Tr}R_g=N$ for $g=1$ and zero otherwise, \begin{equation}\label{wsref-0-65-71-31-38-35-3a-6f-76-65-72-6c-61-70} \operatorname{Tr}(\rho_H\rho_K)=\frac{|H\cap K|}{N}, \qquad \operatorname{Tr}\rho_H^2=\frac{|H|}{N}. \end{equation} Thus the purity difference between the trivial subgroup and an order-two subgroup is only $1/N$. The usual swap measurement estimates purity through a bounded random variable. A plan that estimates this quantity to additive order $1/N$ by direct independent repetitions has a factorial-size sampling cost for $S_n$. This is a failure of that estimator, not a lower bound on arbitrary quantum algorithms.

A stronger calculation isolates the information hidden by the unknown subgroup. Suppose $n$ is even and let $\mathcal C$ be the fixed-point-free involutions in $S_n$: \[ M=|\mathcal C|=\frac{n!}{2^{n/2}(n/2)!}. \] For $h\in\mathcal C$, put $H_h=\{1,h\}$. On $k$ registers consider \[ \sigma_k=\frac1M\sum_{h\in\mathcal C}\rho_{H_h}^{\otimes k}, \qquad \tau_k=\frac{I}{N^k}. \] The same $h$ is used on every register. Replacing $\sigma_k$ by the tensor power of its one-register average would model a different experiment.

Lemma (mixture obstruction). The trace distance obeys \begin{equation}\label{wsref-0-65-71-31-38-35-3a-64-69-73-74-61-6e-63-65} \frac12\|\sigma_k-\tau_k\|_1 \le\frac12\sqrt{\frac{2^k-1}{M}}. \end{equation} Indeed, distinct order-two subgroups intersect trivially, so (eq185:overlap) gives \[ \operatorname{Tr}\sigma_k^2=N^{-k}\left(1+\frac{2^k-1}{M}\right), \qquad \operatorname{Tr}(\sigma_k-\tau_k)^2=N^{-k}\frac{2^k-1}{M}. \] Apply $\|A\|_1\le\sqrt{N^k}\|A\|_2$. Under equal prior probabilities, success at least $2/3$ in distinguishing the two ensembles requires trace distance at least $1/3$. Hence \[ 2^k-1\ge\frac49M,\qquad k\ge\log_2M-O(1)=\Omega(n\log n). \] This derivation makes a standard coset-state obstruction transparent; it is not claimed as a new lower-bound theorem beyond [E2].

For comparison, when the particular $h$ is known, \[ \rho_{H_h}-I/N=R_h/N, \qquad \tfrac12\|\rho_{H_h}-I/N\|_1=\tfrac12. \] Thus the obstruction is not that an individual state is intrinsically close to the trivial-subgroup state. It is the need to distinguish an unknown member of a very large family. A measurement adapted to the unknown $h$ cannot be installed for free.

The calculation suggests taking $k$ somewhat larger than $\log_2M$ and exploiting the permutation symmetry of the ensemble. However, block diagonalizing the average density operator is only one part of a decoder. One still needs efficiently realizable transformations inside its representation-theoretic multiplicity spaces, control of small eigenvalues if inverses are used, and a way to output a generating set. We have not constructed these operations. Even success on the displayed involutions would leave arbitrary subgroups untreated.

Stress test.

The lower bound applies to algorithms whose relevant quantum input consists of the indicated coset states. It is not asserted for arbitrary coherent oracle-query strategies. It is also only a polynomial sample lower bound, so it is compatible with the requested polynomial running time. The source does not fix every machine-level gate and output-encoding convention; the trace identities are independent of those choices and no unbounded-precision gate is being proposed. The exact checks enumerate the involutions and verify one-register overlaps for $S_4$; small instances cannot establish an efficient asymptotic measurement construction. Finally, efficient symmetric-group HSP would give an efficient quantum route to graph isomorphism through the standard reduction, which is a substantial dependency, not a reason to accept a putative decoder without proof [E2], [E3].

Outcome.

Outcome: Exploratory approach with unresolved gap. We obtained exact overlap and mixture formulas and ruled out two misleading shortcuts: direct purity estimation and treating independently averaged registers as samples with one common hidden subgroup. The decisive missing step is a uniform polynomial-time implementation and decoding of an appropriate collective measurement for every subgroup. No such algorithm, and no impossibility theorem for it, is supplied.

Sources

• S1 Maria Isabel Gonzalez Vasco, Delaram Kahrobaei, and Eilidh McKemmie, Applications of Finite Non-Abelian Simple Groups to Cryptography in the Quantum Era, Section 6, La Matematica 3 $2024$, 588-603. https://link.springer.com/article/10.1007/s44007-024-00096-z. Catalogue formulation source.
• E1 Mark Ettinger, Peter Høyer and Emanuel Knill, The quantum query complexity of the hidden subgroup problem is polynomial, Information Processing Letters 91 $2004$, 43--48; arXiv:quant-ph/0401083, main query-complexity theorem. https://arxiv.org/abs/quant-ph/0401083. Research reference; consulted 27 September 2026.
• E2 Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell and Pranab Sen, Limitations of quantum coset states for graph isomorphism, Journal of the ACM 57$6$ $2010$, article 34; DOI 10.1145/1857914.1857918. The earlier three-author manuscript is arXiv:quant-ph/0511148. https://arxiv.org/abs/quant-ph/0511148. Research reference; consulted 27 September 2026.
• E3 Simone Dutto, Pietro Mercuri, Nadir Murru and Lorenzo Romano, A survey about Hidden Subgroup Problem from a mathematical and cryptographic perspective, arXiv:2512.02087v1 (1 December 2025), nonabelian and symmetric-group discussion. https://arxiv.org/html/2512.02087v1. Research reference; consulted 27 September 2026.