Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.35656

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

Yuhan Liu, Jose Carrasco, Jens Eisert, Armando Bellante

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

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|)/ε)$ 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.

Related papers

Abelian State Hidden Subgroup Problem: Learning Stabilizer Groups and Beyond

Marcel Hinsche, Jens Eisert, José A. Carrasco

Identifying the symmetry properties of quantum states is a central theme in quantum information theory and quantum many-body physics. In this work, we investigate quantum learning problems in which the goal is to identify a hidden symmetry of an unknown quantum state. Building on the recent formulation of the state hidden subgroup problem (StateHSP), we focus on abelian groups and develop an efficient quantum algorithm that learns any hidden symmetry subgroup using a generalized form of Fourier sampling. We showcase the versatility of the approach in three concrete applications: These are learning (i) qubit and qudit stabilizer groups, (ii) cuts along which a state is unentangled, and (iii) hidden translation symmetries. Through these applications, we reveal that well-known quantum learning primitives, such as Bell sampling and Bell difference sampling, are, in fact, special cases of Fourier sampling. Our results highlight the broad potential of the StateHSP framework for symmetry-based quantum learning tasks and provide protocols that are easier to implement on near-term quantum devices.

arXiv:2505.15770•PRX Quantum•Feb 25, 2026•1 citation

The Origami ISA and the State Hidden Subgroup Problem: SPLAT as Fourier Sampling

Ian Richard C Buckley

PENDING QUALITY AUDIT (2026-08). The file is restricted while this record is reviewed as part of a systematic audit of the author's corpus. It has not yet been assessed. Metadata and DOI remain public, and access can be requested. Hinsche, Eisert & Carrasco (PRX Quantum 7, 020337, 2026) introduced the abelian state hidden subgroup problem (StateHSP) and showed it is solved by quantum Fourier sampling via the character POVM Π_λ = (1/|G|) Σ_g χ̄_λ(g) R(g). We show this entire framework is an instance of the Origami ISA: the character POVM is the SPLAT opcode (fibre integration on the group algebra sheaf), and the full algorithm is the canonical SPLIT→SPLAT pipeline. Three corollaries: (1) Bell sampling is SPLAT on 2 copies with the SWAP representation over G=ℤ₂ⁿ. (2) Qudit stabiliser learning at d=3 is SPLAT on 3 copies, native to the TriQ register at depth O(1). (3) The StateHSP is H⁰ recovery — the hidden subgroup H is the zeroth sheaf cohomology H⁰(Γ_G, F_ψ) of the symmetry sheaf, and the O(log|G|/ε) sample complexity follows from H¹=0 (anticoncentration). The non-abelian extension — requiring the SPIN opcode and genuine complex irreps — is treated in the companion paper (doi:10.5281/zenodo.20667170). Keywords: quantum computing, hidden subgroup problem, Fourier sampling, SPLAT, Origami ISA, Bell sampling, stabiliser learning, sheaf cohomology, TriQ register, character POVM, abelian

•Jun 12, 2026•0 citations

Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP

Lee, Gideon, Jonathan A. Gross, Masaya Fukami +1 more

The state hidden subgroup problem (StateHSP) is a recent generalization of the hidden subgroup problem. We present an algorithm that solves the non-abelian StateHSP over $N$ copies of the dihedral group of order $8$ (the symmetries of a square). This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy. Our algorithm is polynomial in the number of samples and computational time, and requires only constant depth circuits. This result extends previous work on the abelian StateHSP and, as a special case, provides a solution for the ordinary hidden subgroup problem on this specific non-abelian group.

arXiv:2510.07872•Oct 9, 2025•0 citations

Learning quantum symmetries

Isaac Holt, Sathyawageeswar Subramanian

Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.

quant-pharXiv:2609.38085•Sep 30, 2026•0 citations

The State Hidden Subgroup Problem and an Efficient Algorithm for Locating Unentanglement

Adam Bouland, Tudor Giurgică-Tiron, John Wright

We study a generalization of entanglement testing which we call the “hidden cut problem.” Taking as input copies of an n-qubit pure state which is product across an unknown bipartition, the goal is to learn precisely where the state is unentangled, i.e. to determine which of the exponentially many possible cuts separates the state. We give a polynomial-time quantum algorithm which can find the cut using O(n/є2) many copies of the state, which is optimal up to logarithmic factors. Our algorithm also generalizes to learn the entanglement structure of arbitrary product states. In the special case of Haar-random states, we further show that our algorithm requires circuits of only constant depth. To develop our algorithm, we introduce a state generalization of the hidden subgroup problem (StateHSP) which might be of independent interest, in which one is given a quantum state invariant under an unknown subgroup action, with the goal of learning the hidden symmetry subgroup. We show how the hidden cut problem can be formulated as a StateHSP with a carefully chosen Abelian group action. We then prove that Fourier sampling on the hidden cut state produces similar outcomes as a variant of the well-known Simon’s problem, allowing us to find the hidden cut efficiently. Therefore, our algorithm can be interpreted as an extension of Simon’s algorithm to entanglement testing. We discuss possible applications of StateHSP and hidden cut problems to cryptography and pseudorandomness.

arXiv:2410.12706•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•3 citations

Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries

Natsuto Isogai, Satoshi Yoshida, Mio Murao

Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.

quant-pharXiv:2609.38403•Oct 1, 2026•0 citations
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∣)/ε)O(\log(|G|)/ε)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∣)/ε)O(\log(|G/H|)/\sqrtε)O(log(∣G/H∣)/ε​) forward and inverse queries, and prove a matching Ω(log⁡(∣G/H∣)/ε)Ω(\log(|G/H|)/\sqrtε)Ω(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∣)/ε)Θ(\log(|G/H|)/ε)Θ(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.
Identifying the symmetry properties of quantum states is a central theme in quantum information theory and quantum many-body physics. In this work, we investigate quantum learning problems in which the goal is to identify a hidden symmetry of an unknown quantum state. Building on the recent formulation of the state hidden subgroup problem (StateHSP), we focus on abelian groups and develop an efficient quantum algorithm that learns any hidden symmetry subgroup using a generalized form of Fourier sampling. We showcase the versatility of the approach in three concrete applications: These are learning (i) qubit and qudit stabilizer groups, (ii) cuts along which a state is unentangled, and (iii) hidden translation symmetries. Through these applications, we reveal that well-known quantum learning primitives, such as Bell sampling and Bell difference sampling, are, in fact, special cases of Fourier sampling. Our results highlight the broad potential of the StateHSP framework for symmetry-based quantum learning tasks and provide protocols that are easier to implement on near-term quantum devices.
PENDING QUALITY AUDIT (2026-08). The file is restricted while this record is reviewed as part of a systematic audit of the author's corpus. It has not yet been assessed. Metadata and DOI remain public, and access can be requested. Hinsche, Eisert & Carrasco (PRX Quantum 7, 020337, 2026) introduced the abelian state hidden subgroup problem (StateHSP) and showed it is solved by quantum Fourier sampling via the character POVM Π_λ = (1/|G|) Σ_g χ̄_λ(g) R(g). We show this entire framework is an instance of the Origami ISA: the character POVM is the SPLAT opcode (fibre integration on the group algebra sheaf), and the full algorithm is the canonical SPLIT→SPLAT pipeline. Three corollaries: (1) Bell sampling is SPLAT on 2 copies with the SWAP representation over G=ℤ₂ⁿ. (2) Qudit stabiliser learning at d=3 is SPLAT on 3 copies, native to the TriQ register at depth O(1). (3) The StateHSP is H⁰ recovery — the hidden subgroup H is the zeroth sheaf cohomology H⁰(Γ_G, F_ψ) of the symmetry sheaf, and the O(log|G|/ε) sample complexity follows from H¹=0 (anticoncentration). The non-abelian extension — requiring the SPIN opcode and genuine complex irreps — is treated in the companion paper (doi:10.5281/zenodo.20667170). Keywords: quantum computing, hidden subgroup problem, Fourier sampling, SPLAT, Origami ISA, Bell sampling, stabiliser learning, sheaf cohomology, TriQ register, character POVM, abelian
The state hidden subgroup problem (StateHSP) is a recent generalization of the hidden subgroup problem. We present an algorithm that solves the non-abelian StateHSP over NNN copies of the dihedral group of order 888 (the symmetries of a square). This algorithm is of interest for learning non-Pauli stabilizers, as well as related symmetries relevant for the problem of Hamiltonian spectroscopy. Our algorithm is polynomial in the number of samples and computational time, and requires only constant depth circuits. This result extends previous work on the abelian StateHSP and, as a special case, provides a solution for the ordinary hidden subgroup problem on this specific non-abelian group.
Quantum algorithms are powerful tools for finding symmetries of classical objects, most famously through Shor's algorithm and the Hidden Subgroup Problem (HSP). In this work, we study quantum algorithms for learning symmetries of \emph{quantum} objects. Existing work in this area centres on the recently introduced State Hidden Subgroup Problem (StateHSP), a quantum generalisation of HSP in which the task is to learn the symmetry subgroup of a quantum state. We develop efficient quantum algorithms for non-abelian StateHSP when the hidden subgroup is normal and the ambient group belongs to a broad class of non-abelian groups, extending the previous general theory beyond the abelian setting. StateHSP learns \emph{Bose} symmetries, under which a state must be invariant exactly under the action of the symmetry group. In quantum mechanics, however, physically equivalent pure states are defined only up to global phase. Motivated by this, we introduce a natural notion of \emph{Anyonic} state symmetry learning, based on invariance up to global phase. We give an efficient quantum algorithm by reducing the problem to StateHSP, where the reduction rests on a new correspondence between linearisations of projective representations and linear error-correcting codes. As an application, we obtain an improved algorithm for learning stabiliser groups of mixed qudit states of arbitrary local dimension. Finally, we introduce symmetry learning problems for other quantum objects, including unitaries, Hamiltonians, and finite collections of states, and give efficient algorithms for them by reduction to state symmetry learning. Together, these results broaden the scope of state symmetry learning as a common algorithmic primitive for learning quantum symmetries.
We study a generalization of entanglement testing which we call the “hidden cut problem.” Taking as input copies of an n-qubit pure state which is product across an unknown bipartition, the goal is to learn precisely where the state is unentangled, i.e. to determine which of the exponentially many possible cuts separates the state. We give a polynomial-time quantum algorithm which can find the cut using O(n/є2) many copies of the state, which is optimal up to logarithmic factors. Our algorithm also generalizes to learn the entanglement structure of arbitrary product states. In the special case of Haar-random states, we further show that our algorithm requires circuits of only constant depth. To develop our algorithm, we introduce a state generalization of the hidden subgroup problem (StateHSP) which might be of independent interest, in which one is given a quantum state invariant under an unknown subgroup action, with the goal of learning the hidden symmetry subgroup. We show how the hidden cut problem can be formulated as a StateHSP with a carefully chosen Abelian group action. We then prove that Fourier sampling on the hidden cut state produces similar outcomes as a variant of the well-known Simon’s problem, allowing us to find the hidden cut efficiently. Therefore, our algorithm can be interpreted as an extension of Simon’s algorithm to entanglement testing. We discuss possible applications of StateHSP and hidden cut problems to cryptography and pseudorandomness.
Whether quantum computation can reduce the amount of data required for conventional machine learning is a central problem in quantum machine learning. In probably approximately correct (PAC) learning, a learner receives training examples sampled from an unknown probability distribution. Quantum PAC learning extends this framework by allowing access to quantum examples, which are quantum states that coherently encode this distribution, or to unitaries that prepare quantum examples, with or without inverse access. When only copies of quantum examples are available, the optimal worst-case sample complexity asymptotically matches that of classical learning. In contrast, access to both a preparation unitary and its inverse can improve the accuracy dependence of query complexity. However, it has remained open whether access to the preparation unitary alone suffices for this improvement. In this work, we resolve this question by determining the optimal query complexity with forward-only access, taking the worst case over compatible preparation unitaries and their dimensions. In both realizable and agnostic PAC learning, this complexity matches, up to constant factors, the optimal sample complexity achievable with classical examples or copies of quantum examples. To prove these results, we construct, for any algorithm with forward-only access, a simulator that approximates the algorithm's Haar-averaged output state using as many copies of the prepared state as the algorithm makes queries. These results show that inverse access is essential for the known improvement in accuracy dependence in this worst-case setting. Beyond PAC learning, our reduction provides a general tool for transferring lower bounds for state copies to query lower bounds for forward-only access to the corresponding preparation unitaries.