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

arXivarxiv/2609.35656Sep 28, 2026quant-phscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.35656
curl -X POST /api/v1/records/arxiv/2609.35656/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.35656/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'