aiqbench analysis
This study resolves the optimal sample and query complexity for the abelian state hidden subgroup problem, demonstrating that coherent access to state-preparation circuits yields a genuine quadratic improvement over standard sampling methods. By establishing tight lower bounds even under strong conjugate-query settings, the work clarifies the fundamental limits of quantum algorithms seeking superpolynomial speed-ups in symmetry identification tasks. These findings directly advance the theoretical understanding of quantum advantage in problems involving stabilizer groups and hidden translation symmetries.
The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
arXiv:2609.35656v1 Announce Type: new 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|)/\epsilon)$ 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{\epsilon})$ forward and inverse queries, and prove a matching $\Omega(\log(|G/H|)/\sqrt{\epsilon})$ lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, $\Theta(\log(|G/H|)/\epsilon)$ copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in $\epsilon$ 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.
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|)/\epsilon)$ 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{\epsilon})$ forward and inverse queries, and prove a matching $\Omega(\log(|G/H|)/\sqrt{\epsilon})$ lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, $\Theta(\log(|G/H|)/\epsilon)$ copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in $\epsilon$ 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.
arXiv:2609.35656 [quant-ph]
(or arXiv:2609.35656v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2609.35656 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 304 words
