# The state hidden subgroup problem and an efficient algorithm for locating unentanglement

arXiv: https://arxiv.org/abs/2410.12706 · HTML: https://mlsanity.com/paper/2410.12706/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Oct 2024.

## Built on by (most cited first, 4 of 4)

- [Spectral methods: crucial for machine learning, natural for quantum computers?](https://mlsanity.com/paper/2603.24654/) (2026)
- [Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more](https://mlsanity.com/paper/2510.06848/) (2025)
- [Fragmentation is Efficiently Learnable by Quantum Neural Networks](https://mlsanity.com/paper/2512.00751/) (2025)
- [Symmetry Discovery in Quantum Learning: Observable-Level and Task-Level Inference from Finite Measurements](https://mlsanity.com/paper/2610.00157/) (2026)

## Abstract (arXiv)

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.