Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
The authors resolve the exact computational complexity of the abelian state hidden subgroup problem (StateHSP) by establishing matching upper and lower bounds across both copy-based sample access and unitary query models. They prove that coherent access to a state-preparation circuit enables a time-efficient quantum algorithm with an optimal $\Theta(\log(|G/H|)/\sqrt{\epsilon})$ query complexity, quadratically beating the $\Theta(\log(|G/H|)/\epsilon)$ lower bound they establish for passive state samples under arbitrary collective measurements. This settles the long-standing optimality of Fourier sampling for state symmetries and yields improved runtimes for practical tasks like stabilizer group learning and unentanglement detection.
Coherent oracle access unlocks an unconditional quadratic speedup in error tolerance over passive quantum state copies, settling the fundamental complexity of learning abelian quantum 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.