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:2609.35656

The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 1 citation
arXivHTMLPDF

Abstract

In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use $O(\log(|G|)/ε)$ copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using $O(\log(|G/H|)/\sqrtε)$ forward and inverse queries, and prove a matching $Ω(\log(|G/H|)/\sqrtε)$ lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, $Θ(\log(|G/H|)/ε)$ copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in $ε$ genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.

AI Summary

The paper studies how input access changes the complexity of the abelian state hidden subgroup problem (StateHSP): recover the subgroup $H\leq G$ fixing an unknown pure state, promised that every element outside $H$ has overlap at most $1-\epsilon$ with it. It compares access to independent state copies with coherent access to a preparation unitary $U_\varphi$ and its inverse. For constant success probability, it establishes worst-case sample complexity $\Theta(\log|G/H|/\epsilon)$ and query complexity $\Theta(\log|G/H|/\sqrt{\epsilon})$. The algorithms do not require knowing $|H|$. Their upper bounds extend to failure probability $\delta$ by replacing $\log|G/H|$ with $\log|G/H|+\log(1/\delta)$. Fourier sampling accumulates generators of $H^\perp$; an adaptive stopping budget yields the quotient-size dependence. In the query model, coherent membership tests and fixed-point amplitude amplification reduce the cost of obtaining a new generator from $O(1/\epsilon)$ to $O(1/\sqrt{\epsilon})$. Matching lower bounds use fractional padded Simon instances and an adversary argument for queries, and phase-randomized subgroup states with Fano’s inequality and the Holevo bound for copies. They cover controlled and conjugate queries, and arbitrary collective measurements, respectively. The improvements transfer to locating tensor-product factors, learning stabilizer groups, and identifying translation symmetries. Time efficiency assumes efficient controlled representation actions; the analysis assumes exact Fourier transforms. The general lower bounds do not establish optimality for these applications. Forward-only preparation access and improvements exploiting explicit circuit descriptions remain open.

Little sign of AI-generated textAI use disclosed
ChatGPT 5.6 Sol, 6 Astra, and Opus 5 assisted the authors in revising the document and provided feedback.

Error found: For the allowed case H=G, the abstract’s upper bounds incorrectly imply zero input accesses; the body’s valid bounds retain an additive constant in the numerator at constant success probability.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Abelian State Hidden Subgroup Problem: Learning Stabilizer Groups and Beyond

Marcel Hinsche, Jens Eisert, José A. Carrasco

Identifying the symmetry properties of quantum states is a central theme in quantum information theory and quantum many-body physics. In this work, we investigate quantum learning problems in which the goal is to identify a hidden symmetry of an unknown quantum state. Building on the recent formulation of the state hidden subgroup problem (StateHSP), we focus on abelian groups and develop an efficient quantum algorithm that learns any hidden symmetry subgroup using a generalized form of Fourier sampling. We showcase the versatility of the approach in three concrete applications: These are learning (i) qubit and qudit stabilizer groups, (ii) cuts along which a state is unentangled, and (iii) hidden translation symmetries. Through these applications, we reveal that well-known quantum learning primitives, such as Bell sampling and Bell difference sampling, are, in fact, special cases of Fourier sampling. Our results highlight the broad potential of the StateHSP framework for symmetry-based quantum learning tasks and provide protocols that are easier to implement on near-term quantum devices.

arXiv:2505.15770•PRX Quantum•Feb 25, 2026•11 citations

The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts

Cristopher Moore, Daniel N. Rockmore, Alexander C. Russell +1 more

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup H of a group G must be determined from a quantum state $\psi$ over G that is uniformly supported on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling: the quantum Fourier transform of $\psi$ is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups H of the q-hedral groups, i.e., semidirect products ${\mathbb Z}_q \ltimes {\mathbb Z}_p$, where $q \mid (p-1)$, and in particular the affine groups $A_p$, can be information-theoretically reconstructed using the strong standard method. Moreover, if $|H| = p/ {\rm polylog}(p)$, these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

arXiv:quant-ph/0503095•SIAM Journal on Computing•Jan 1, 2007•59 citations

A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Greg Kuperberg

We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity $2^{O(\sqrt{\log\ N})}$. In this problem an oracle computes a function f on the dihedral group $D_N$ which is invariant under a hidden reflection in $D_N$. By contrast, the classical query complexity of DHSP is $O(\sqrt{N})$. The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of $D_N$ is essentially the abelian quantum Fourier transform. This yields the name of a group representation of $D_N$, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of $D_N$. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.

arXiv:quant-ph/0302112•SIAM Journal on Computing•Jan 1, 2005•406 citations

The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling

Cristopher Moore, Daniel N. Rockmore, Alexander C. Russell +1 more

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state y uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of y is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of Z_p by Z_q, where q divides (p-1) and q = p / polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We extend this to an information-theoretic solution for the hidden subgroup problem over semidirect products of Z_p by \Z_q where q divides (p-1) and, in particular, the Affine groups A_p. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

arXiv:quant-ph/0211124•Nov 20, 2002•29 citations

Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis

Oliver O'Brien

The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unknown. We experimentally study the HSP over the $q$-hedral groups $\mathbb{Z}_q \ltimes \mathbb{Z}_p$, which interpolate between the dihedral and affine groups and mark a boundary between instances that are efficiently solvable and those that are only information-theoretically solvable. On the IonQ Forte trapped-ion quantum computer, with $p \le 7$, we implement weak Fourier sampling, strong Fourier sampling in an adapted basis, strong Fourier sampling of adjacent pairs, and forgetful abelian sampling. We demonstrate that the theoretical predictions of Moore, Rockmore, Russell and Schulman survive on a noisy device: weak sampling reveals nothing about the hidden subgroup, the adapted basis succeeds for large $q$, adjacent pairs succeed for small $q$, and forgetful sampling saturates below unit success. For $p=7$, $q=6$, the hardware exceeds the success probability of an exhaustively optimised classical algorithm for up to three oracle queries.

arXiv:2611.06716•Nov 4, 2026•0 citations

Quantum fourier sampling, the hidden subgroup problem, and beyond

Sean Hallgren, Umesh V. Vazirani

The Hidden Subgroup Problem (HSP) provides the fundamental framework for most quantum algorithms. Until very recently, all known problems where quantum computation provides a super-polynomial speedup over classical algorithms have been variants of the HSP for particular abelian groups. Examples include factoring integers and computing the discrete log, for which Shor found efficient quantum algorithms. The algorithm for these problems may be viewed as consisting of the main HSP solution plus an ad hoc method of dealing with the particular variant. In this dissertation, we give a systematic way of dealing with all these variants. The key component of our solution is a new theorem about the robustness of Fourier sampling. The purpose of this theorem is to better understand the structure underlying existing algorithms as well as to provide an algorithmic tool for the construction of future quantum algorithms. In addition, we also derive a new algorithm for computing the quantum Fourier transform which is asymptotically faster than any previously known algorithm. By contrast, the nonabelian HSP is wide open. It includes as a special case the longstanding open question of graph isomorphism, where the group is the symmetric group, S n . It is natural to carry over the abelian HSP algorithm to the nonabelian case. We show that in the case that the hidden subgroup is normal, this algorithm succeeds in reconstructing the subgroup in polynomial time. On the other hand, we give evidence that this algorithm is inadequate to even distinguish a trivial subgroup from an involution in t...

•Jan 1, 2000•4 citations
In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use O(log⁡(∣G∣)/ε)O(\log(|G|)/ε)O(log(∣G∣)/ε) copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using O(log⁡(∣G/H∣)/ε)O(\log(|G/H|)/\sqrtε)O(log(∣G/H∣)/ε​) forward and inverse queries, and prove a matching Ω(log⁡(∣G/H∣)/ε)Ω(\log(|G/H|)/\sqrtε)Ω(log(∣G/H∣)/ε​) lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, Θ(log⁡(∣G/H∣)/ε)Θ(\log(|G/H|)/ε)Θ(log(∣G/H∣)/ε) copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in εεε genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.
The paper studies how input access changes the complexity of the abelian state hidden subgroup problem (StateHSP): recover the subgroup H≤GH\leq GH≤G fixing an unknown pure state, promised that every element outside HHH has overlap at most 1−ϵ1-\epsilon1−ϵ with it. It compares access to independent state copies with coherent access to a preparation unitary UφU_\varphiUφ​ and its inverse.
For constant success probability, it establishes worst-case sample complexity Θ(log⁡∣G/H∣/ϵ)\Theta(\log|G/H|/\epsilon)Θ(log∣G/H∣/ϵ) and query complexity Θ(log⁡∣G/H∣/ϵ)\Theta(\log|G/H|/\sqrt{\epsilon})Θ(log∣G/H∣/ϵ​). The algorithms do not require knowing ∣H∣|H|∣H∣. Their upper bounds extend to failure probability δ\deltaδ by replacing log⁡∣G/H∣\log|G/H|log∣G/H∣ with log⁡∣G/H∣+log⁡(1/δ)\log|G/H|+\log(1/\delta)log∣G/H∣+log(1/δ). Fourier sampling accumulates generators of H⊥H^\perpH⊥; an adaptive stopping budget yields the quotient-size dependence. In the query model, coherent membership tests and fixed-point amplitude amplification reduce the cost of obtaining a new generator from O(1/ϵ)O(1/\epsilon)O(1/ϵ) to O(1/ϵ)O(1/\sqrt{\epsilon})O(1/ϵ​). Matching lower bounds use fractional padded Simon instances and an adversary argument for queries, and phase-randomized subgroup states with Fano’s inequality and the Holevo bound for copies. They cover controlled and conjugate queries, and arbitrary collective measurements, respectively.
The improvements transfer to locating tensor-product factors, learning stabilizer groups, and identifying translation symmetries. Time efficiency assumes efficient controlled representation actions; the analysis assumes exact Fourier transforms. The general lower bounds do not establish optimality for these applications. Forward-only preparation access and improvements exploiting explicit circuit descriptions remain open.
Identifying the symmetry properties of quantum states is a central theme in quantum information theory and quantum many-body physics. In this work, we investigate quantum learning problems in which the goal is to identify a hidden symmetry of an unknown quantum state. Building on the recent formulation of the state hidden subgroup problem (StateHSP), we focus on abelian groups and develop an efficient quantum algorithm that learns any hidden symmetry subgroup using a generalized form of Fourier sampling. We showcase the versatility of the approach in three concrete applications: These are learning (i) qubit and qudit stabilizer groups, (ii) cuts along which a state is unentangled, and (iii) hidden translation symmetries. Through these applications, we reveal that well-known quantum learning primitives, such as Bell sampling and Bell difference sampling, are, in fact, special cases of Fourier sampling. Our results highlight the broad potential of the StateHSP framework for symmetry-based quantum learning tasks and provide protocols that are easier to implement on near-term quantum devices.
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup H of a group G must be determined from a quantum state ψ\psiψ over G that is uniformly supported on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling: the quantum Fourier transform of ψ\psiψ is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups H of the q-hedral groups, i.e., semidirect products Zq⋉Zp{\mathbb Z}_q \ltimes {\mathbb Z}_pZq​⋉Zp​, where q∣(p−1)q \mid (p-1)q∣(p−1), and in particular the affine groups ApA_pAp​, can be information-theoretically reconstructed using the strong standard method. Moreover, if ∣H∣=p/polylog(p)|H| = p/ {\rm polylog}(p)∣H∣=p/polylog(p), these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
We present a quantum algorithm for the dihedral hidden subgroup problem (DHSP) with time and query complexity 2O(log⁡ N)2^{O(\sqrt{\log\ N})}2O(log N​). In this problem an oracle computes a function f on the dihedral group DND_NDN​ which is invariant under a hidden reflection in DND_NDN​. By contrast, the classical query complexity of DHSP is O(N)O(\sqrt{N})O(N​). The algorithm also applies to the hidden shift problem for an arbitrary finitely generated abelian group. The algorithm begins as usual with a quantum character transform, which in the case of DND_NDN​ is essentially the abelian quantum Fourier transform. This yields the name of a group representation of DND_NDN​, which is not by itself useful, and a state in the representation, which is a valuable but indecipherable qubit. The algorithm proceeds by repeatedly pairing two unfavorable qubits to make a new qubit in a more favorable representation of DND_NDN​. Once the algorithm obtains certain target representations, direct measurements reveal the hidden subgroup.
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined from a quantum state y uniformly supported on a left coset of H. These hidden subgroup problems are then solved by Fourier sampling: the quantum Fourier transform of y is computed and measured. When the underlying group is non-Abelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups of semidirect products of Z_p by Z_q, where q divides (p-1) and q = p / polylog(p), can be efficiently determined by the strong standard method. Furthermore, the weak standard method and the ``forgetful'' Abelian method are insufficient for these groups. We extend this to an information-theoretic solution for the hidden subgroup problem over semidirect products of Z_p by \Z_q where q divides (p-1) and, in particular, the Affine groups A_p. Finally, we prove a closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unknown. We experimentally study the HSP over the qqq-hedral groups Zq⋉Zp\mathbb{Z}_q \ltimes \mathbb{Z}_pZq​⋉Zp​, which interpolate between the dihedral and affine groups and mark a boundary between instances that are efficiently solvable and those that are only information-theoretically solvable. On the IonQ Forte trapped-ion quantum computer, with p≤7p \le 7p≤7, we implement weak Fourier sampling, strong Fourier sampling in an adapted basis, strong Fourier sampling of adjacent pairs, and forgetful abelian sampling. We demonstrate that the theoretical predictions of Moore, Rockmore, Russell and Schulman survive on a noisy device: weak sampling reveals nothing about the hidden subgroup, the adapted basis succeeds for large qqq, adjacent pairs succeed for small qqq, and forgetful sampling saturates below unit success. For p=7p=7p=7, q=6q=6q=6, the hardware exceeds the success probability of an exhaustively optimised classical algorithm for up to three oracle queries.
The Hidden Subgroup Problem (HSP) provides the fundamental framework for most quantum algorithms. Until very recently, all known problems where quantum computation provides a super-polynomial speedup over classical algorithms have been variants of the HSP for particular abelian groups. Examples include factoring integers and computing the discrete log, for which Shor found efficient quantum algorithms. The algorithm for these problems may be viewed as consisting of the main HSP solution plus an ad hoc method of dealing with the particular variant. In this dissertation, we give a systematic way of dealing with all these variants. The key component of our solution is a new theorem about the robustness of Fourier sampling. The purpose of this theorem is to better understand the structure underlying existing algorithms as well as to provide an algorithmic tool for the construction of future quantum algorithms. In addition, we also derive a new algorithm for computing the quantum Fourier transform which is asymptotically faster than any previously known algorithm. By contrast, the nonabelian HSP is wide open. It includes as a special case the longstanding open question of graph isomorphism, where the group is the symmetric group, S n . It is natural to carry over the abelian HSP algorithm to the nonabelian case. We show that in the case that the hidden subgroup is normal, this algorithm succeeds in reconstructing the subgroup in polynomial time. On the other hand, we give evidence that this algorithm is inadequate to even distinguish a trivial subgroup from an involution in t...