{"id":"arxiv/2609.35656","url":"https://arxiv.org/abs/2609.35656","tags":["quant-ph"],"score":0,"title":"The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem","domain":"quant-ph","source":"arxiv","authors":["Yuhan Liu","Jose Carrasco","Jens Eisert","Armando Bellante"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}