REVIEW
The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
Quantum Physics · Submitted 28 Sep 2026 · 61 references
Pith's verdict: Matching Theta bounds for abelian StateHSP in both copy and query models; the quadratic coherent-access speedup is real and the proofs hold up on inspection.
T0 · AI review
Why Pith says this
Highlight any text to comment on it.
Referee report
The paper
The paper claims
The abelian state hidden subgroup problem now has exact optimal costs — $\Theta(\log(|G/H|)/\epsilon)$ copies of the unknown state, or $\Theta(\log(|G/H|)/\sqrt{\epsilon})$ queries to its state-preparation circuit and inverse — and the…
The reading
What carries the argument
The argument runs through the Fourier sampling circuit $U_F = (F_G \otimes I)U_R(U_G \otimes U_\varphi)$, which maps the unknown state to a superposition over characters in the dual subgroup $H^\perp$ with sampling distribution $P(\lambda)$. The load-bearing estimate is the anti-concentration bound of Lemma 3.7: for every proper subgroup $K^\perp < H^\perp$ of the current span, the probability of drawing a sample outside $K^\perp$ is at least $\epsilon/2$. In the copy model this makes each span-increasing generator cost $O(1/\epsilon)$ samples, and an adaptive budget-walk stopping rule converts the naive $\log|G|$ sample count into $\log|G/H|$ without knowing $|H|$ in advance. In the query model, a subspace identifier $U_\perp$ coherently flags Fourier labels outside the current span, and a modified fixed-point amplitude amplification with amplitude lower bound $\gamma = \sqrt{\epsilon/2}$ boosts the per-generator cost to $O(1/\sqrt{\epsilon})$. The lower bounds use an adversary argument with the relative $\gamma_2$ norm, where the fractional padded Simon oracles differ by a $\sqrt{\epsilon}$ factor that rescales the adversary bound by $1/\sqrt{\epsilon}$, and, for the copy model, Fano's inequality sandwiched against a Holevo bound on phase-averaged $t$-copy states whose sector decomposition shows each copy carries at most $2\epsilon m$ bits about the hidden subgroup.
Extended reading notes
Core claim
The paper's central claim is a tight characterization of the abelian StateHSP in two access models. With copies of the unknown state, $\Theta(\log(|G/H|)/\epsilon)$ copies are sufficient and information-theoretically necessary, a lower bound that holds even when the algorithm may perform arbitrary collective measurements on all copies at once. With query access to the state-preparation unitary $U_\varphi$ and its inverse $U_\varphi^{-1}$, $\Theta(\log(|G/H|)/\sqrt{\epsilon})$ queries are sufficient and necessary, where the lower bound survives even the stronger conjugate-query and controlled-query settings. Because the two bounds coincide except for the $\sqrt{\epsilon}$ versus $\epsilon$ factor, the paper concludes that the quadratic improvement genuinely arises from coherent access to the preparation circuit: amplitude amplification is all there is to exploit. Along the way it achieves the $\log|G/H|$ dependence without prior knowledge of the hidden subgroup's size, via an adaptive stopping rule that converts a redundant $\log|G|$ sampling budget into a random-walk budget that automatically detects completion.
Load-bearing premise
The entire result rests on the StateHSP promise that the fidelity gap is uniform and known: every group element outside the hidden subgroup $H$ satisfies $|\langle\varphi|R(g)|\varphi\rangle| \le 1-\epsilon$ for a single input-known $\epsilon$, and every element of $H$ leaves the state exactly invariant, so the anti-concentration bound $P(H^\perp\setminus K^\perp) \ge \epsilon/2$ and both $\Theta$ scalings collapse if $\epsilon$ is unknown or the gap varies between elements.
Editorial extensions
If this is right
- Larger hidden subgroups are provably easier: the resource count is set by $\log|G/H|$, not $\log|G|$, and the algorithms achieve this without being told $|H|$ in advance.
- The $\epsilon$-dependence is closed: prior $O(\log|G|/\epsilon)$ Fourier sampling was already essentially optimal for copies, and no algorithm in either access model can beat the $1/\epsilon$ or $1/\sqrt{\epsilon}$ scaling.
- Coherent access to the preparation circuit is worth exactly a quadratic improvement in $\epsilon$, and nothing more: amplitude amplification is the only source of the gap between the two models.
- Controlled and conjugate queries add no worst-case advantage, since the upper bounds need neither while the lower bounds tolerate both.
- The stated bounds give faster algorithms for locating unentanglement, learning stabilizer groups, and identifying translation symmetries, the improvement passing directly through the StateHSP reductions.
Reading between the lines
- The adaptive budget-walk stopping rule is a transferable mechanism: any generator-accumulation learning task whose progress can be recognized and coherently flagged can replace a $\log|G|$ resource term by $\log|G/H|$ the same way.
- The paper leaves forward-only oracle access open; by analogy with the known result that amplitude amplification requires inverses, one can conjecture that forward-only access reverts to the $1/\epsilon$ scaling, a testable claim the paper does not make.
- The hard instance families double as benchmarks: candidate pseudoentanglement or pseudorandom-state constructions can be stress-tested against the coherent-query StateHSP attack at the $O(\log|G/H|/\sqrt{\epsilon})$ rate.
- The sector-entropy Holevo sandwich used for the copy lower bound may extend to other promise-gap learning problems whose states split into an informative branch and a nearly uninformative branch.
Original 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.
The compiled record
The paper's own sentences, arranged, kept beside the review and separate from it. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
The abstract, sentence by sentence
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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | 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. | background 1.00 | 0.05 | 0.03 | asserted 0.89 |
| s1 | 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. | contribution 0.57 | 0.43 | 0.03 | asserted 0.82 |
| s2 | 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. | gap 0.82 | 0.04 | 0.04 | asserted 1.00 |
| s3 | 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. | contribution 0.99 | 0.89 | 0.17 | asserted 0.99 |
| s4 | 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. | result 0.93 | 0.97 | 0.34 | asserted 1.00 |
| s5 | 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. | result 1.00 | 0.93 | 0.24 | asserted 1.00 |
| s6 | Thus, the quadratic improvement in $\epsilon$ genuinely arises from coherent access to the preparation circuit. | interpretation 1.00 | 0.87 | 0.51 | asserted 1.00 |
| s7 | As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries. | contribution 0.64 | 0.90 | 0.05 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
Figures
Figures reproduced from arXiv:2609.35656 by the authors.
References
Discussion
Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.