One of the central issues in the hidden subgroup problem is to bound the sample complexity, i.e., the number of identical samples of coset states sufficient and necessary to solve the problem. In this paper, we present general bounds for the sample complexity of the identification and decision versions of the hidden subgroup problem. As a consequence of the bounds, we show that the sample complexity for both of the decision and identification versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden subgroups in the case \REVISE{where the candidate nontrivial subgroups} have the same prime order $p$ , which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important \REVISE{cases} such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained \REVISE{by a variant of the pretty good measurement}. \REVISE{This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity}.One of the central issues in the hidden subgroup problem is to bound the sample complexity, i.e., the number of identical samples of coset states sufficient and necessary to solve the problem. In this paper, we present general bounds for the sample complexity of the identification and decision versions of the hidden subgroup problem. As a consequence of the bounds, we show that the sample complexity for both of the decision and identification versions is $\Theta(\log|\HH|/\log p)$ for a candidate set $\HH$ of hidden subgroups in the case \REVISE{where the candidate nontrivial subgroups} have the same prime order $p$, which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important \REVISE{cases} such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained \REVISE{by a variant of the pretty good measurement}. \REVISE{This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity}.

arXiv:quant-ph/0604174Quantum Information and ComputationMar 1, 200835 citations

The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

Yuhan Liu, Jose Carrasco, Jens Eisert +1 more

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|)/\sqrtε)$ forward and inverse queries, and prove a matching $Ω(\log(|G/H|)/\sqrtε)$ 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.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|)/\sqrtε)$ forward and inverse queries, and prove a matching $Ω(\log(|G/H|)/\sqrtε)$ 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.

quant-pharXiv:2609.35656Sep 29, 20260 citations

p

, which implies that the decision version is at least as hard as the identification version in this case. In particular, it does so for the important \REVISE{cases} such as the dihedral and the symmetric hidden subgroup problems. Moreover, the upper bound of the identification is attained \REVISE{by a variant of the pretty good measurement}. \REVISE{This implies that the concept of the pretty good measurement is quite useful for identification of hidden subgroups over an arbitrary group with optimal sample complexity}.

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|)/\sqrtε)

forward and inverse queries, and prove a matching

Ω(\log(|G/H|)/\sqrtε)

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.