Quantum state isomorphism problems for groups
Abstract
We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA ∩ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP ∩ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.
Related
- Quantum Knowledge Distillation: State-of-the-art, Applications and Open Problems
- Solving wave propagation problems via geometric quantum state preparation on dispersion manifolds
- Choi-Jamiołkowski isomorphism(s) and channel/state duality, naturally!
- Testing graph isomorphism using simple quantum circuits
- Complexity and Applications of Nearest Stabilizer Product State Problems
BibTeX
@misc{gheorghiu2026quantum,
title = {{Quantum state isomorphism problems for groups}},
author = {Alexandru Gheorghiu and Dale Jacobs and Saeed Mehraban and Arsalan Motamedi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.12615},
eprint = {2605.12615},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.12615},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum state isomorphism problems for groups
AU - Alexandru Gheorghiu
AU - Dale Jacobs
AU - Saeed Mehraban
AU - Arsalan Motamedi
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2605.12615
UR - https://arxiv.org/abs/2605.12615
AB - We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA ∩ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP ∩ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.
ER -