Skip to content
Preprint

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

Sep 2026 · 1 citation
Physics

TL;DR

The complexity of the abelian StateHSP is settled 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.

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.

View source

Similar papers

Preprint Oct 2026

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Random circuit sampling experiments, the leading demonstrations of quantum computational advantage, are tested with the linear cross-entropy benchmark (XEB), which scores outcomes by their ideal probabilities. We study what a high XEB score certifies about an untrusted quantum device. In the quantum query model, we sho...

Keshav Bhateja, Mehdi Esmaili, A. Mantri · 0 citations
Sep 2026

Verifiable quantum advantage based on polynomials with planted structures

A central question in the theory of quantum advantage is whether there are quantum advantage protocols with similar resource requirements as random circuit sampling that are also verifiable just from the classical outputs of the quantum computation. Here, we develop the idea of simulation secrets for verifiable advanta...

Markus Bläser, M. Gullans, Dominik Hangleiter et al. · 1 citation
Preprint Nov 2026

Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis

The hidden subgroup problem (HSP) unifies many of the best-known quantum speed-ups. For abelian groups it is solved efficiently by weak Fourier sampling, but for non-abelian groups, which include the cases relevant to graph isomorphism and lattice-based cryptography, the right measurement basis is crucial and often unk...

Oliver O'Brien · 0 citations

UvA-DARE (Digital

The first complete post-quantum security proof of the textbook Fujisaki-Okamoto transformation is presented, i.e, without adjustments to facilitate the proof, including concrete security bounds, including concrete security bounds.

Jelle Don, S. Fehr, Christian Majenz et al. · 0 citations
Preprint Oct 2026

Random-Oracle Unitary Synthesis is Impossible

A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any classical function in superposition? Inspired by a recent work by Brakerski and Yuen (CRYPTO 2026), we propose an ``average-case''unitary synth...

Andrew Huang, Akshar Ramkumar, John Wright · 1 citation
Sep 2026

A Separation Between Types of Quantum Oracle Separations

The notion of meta-complexity of quantum relativization of oracles is introduced, and it is shown that this meta-complexity can be nontrivial by giving a complete classification, within the family of oracle pantheons defined in this paper, of which models can separate the complexity classes.

S. Aaronson, Adam Bouland, Jordan Docter et al. · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.