We introduce the “hidden cut problem:” given as input which is product across an unknown bipartition, the goal is to learn precisely where the state is unentangled, i.e. to find the hidden cut. We give a polynomial time quantum algorithm for the hidden cut problem, which consumes O(n/ε^2) many copies of the state, and show that this asymptotic is optimal. In the special case of Haar-random states, the circuits involved are of merely constant depth, which could prove relevant to experimental implementations. 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 describe generalizations of this algorithm to products of multiple states, and discuss possible applications to cryptography and pseudorandomness. Joint work with Adam Bouland and John Wright.

Pizza and drinks will be served after the seminar in ATL 2117.