The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
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|)/√ε) forward and inverse queries, and prove a matching Ω(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|)/ε) 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.
Related
- Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis
- EFI Pairs Without One-Way Puzzles: Oracle Separations from Communication Complexity
- A simple solution to the monopole problem: SU(5) GUT with symmetry breaking into special subgroup
- The Hidden Subgroup Problem in Semidirect Products and Quasi-Hamiltonian Groups
- On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
BibTeX
@misc{liu2026power,
title = {{The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem}},
author = {Yuhan Liu and Jose Carrasco and Jens Eisert and Armando Bellante},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35656},
eprint = {2609.35656},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35656},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
AU - Yuhan Liu
AU - Jose Carrasco
AU - Jens Eisert
AU - Armando Bellante
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35656
UR - https://arxiv.org/abs/2609.35656
AB - 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|)/√ε) forward and inverse queries, and prove a matching Ω(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|)/ε) 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.
ER -