We formulate the generalized hidden shift problem over arbitrary finite groups and obtain upper and lower bounds for the sample complexity in terms of group theoretic data.
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∣)/ε) forward and inverse queries, and prove a matching Ω(log(∣G/H∣)/ε) 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.
We develop a mixing time method for estimating the sample complexity of quantum state discrimination. We start with considering the minimum-error discrimination of geometrically uniform pure state ensembles, and prove that its sample complexity has a tight estimate given by a quantum homogeneous mixing time [George et al., 2026] and a quantum version of the generalized Dobrushin coefficient [Wolfer, 2020]. This quantum mixing time further reduces to a classical one when the generating group G forms a Gelfand pair with the stabilizer subgroup H of the generator state. In this case the generalized Dobrushin coefficient can be fully expressed by representation-theoretic quantities of the commutative Hecke algebra EndG(C[G/H]). In particular, this method reduces the sample complexity estimation of learning quantum coupon collector states [Arunachalam et al., 2020] and learning phase states to classical mixing time problems. We apply this framework to answer the open problems of learning degree-d phase states over Fq in [Alrabiah et al., 2026] and generalized Boolean phase states over Zq [Arunachalam et al., 2023]. The framework also applies to hypergraph state ensembles, giving estimates expressed fully in terms of hypergraph data and recovering estimates for graph state ensembles in [Montanaro and Shao, 2022]. Finally, we extend the discussion to arbitrary mixed state ensembles with uniform priors, prove a sandwiched bound for minimum-error discrimination sample complexity by a quantum weakly mixing time, and provide a tight estimate for the minimax discrimination sample complexity from [D'Ariano et al., 2005] by a Dobrushin-type coefficient. We also discuss the method of strengthened data processing inequality [Gao and Rouz{é}, 2022] and give an upper bound in terms of a strengthened data processing inequality constant.