pith. machine review for the scientific record. sign in

arxiv: 2605.12615 · v1 · submitted 2026-05-12 · 🪐 quant-ph · cs.CC

Recognition: unknown

Quantum state isomorphism problems for groups

Alexandru Gheorghiu , Dale Jacobs , Saeed Mehraban , Arsalan Motamedi
Authors on Pith no claims yet

Pith reviewed 2026-05-14 20:27 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC
keywords quantum state isomorphismgroup actionsQSZKBQPhidden subgroup problemmixed quantum statesgraph isomorphismPauli group
0
0 comments X

The pith

The quantum state isomorphism problem for mixed states under nontrivial finite group actions is QSZK-complete.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the complexity of deciding whether two states prepared by quantum circuits are related by a group action. For pure states the decision is BQP-hard for every nontrivial group and sits inside QCMA intersect QCSZK. For mixed states the same decision is QSZK-complete when the group is nontrivial, finite, and efficiently representable. This also establishes that the abelian mixed-state hidden-subgroup problem is QSZK-hard, ruling out an efficient quantum algorithm unless QSZK equals BQP.

Core claim

The authors establish that the mixed-state quantum state isomorphism problem is QSZK-complete for nontrivial finite efficiently representable groups. The pure-state version is BQP-hard for all nontrivial groups and contained in QCMA intersect QCSZK, with tighter placements such as BQP-completeness for the Pauli group and polynomial-time equivalence to graph isomorphism for the Clifford group. The bosonic linear-optical case under the stellar representation is at least graph-isomorphism hard and contained in NP intersect SZK.

What carries the argument

The quantum state isomorphism decision problem under group actions on states supplied by quantum circuits.

If this is right

  • No efficient quantum algorithm exists for the mixed-state abelian hidden-subgroup problem unless QSZK equals BQP.
  • Pure-state versions remain at least BQP-hard, so they lie outside efficient classical simulation unless BQP equals P.
  • The Clifford-group case is at least as hard as graph isomorphism under polynomial reductions.
  • The Pauli-group case is BQP-complete.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Symmetry-aware verification of quantum states in experiments must distinguish mixed-state distinctions that pure-state methods ignore.
  • Similar hardness may extend to other infinite groups once suitable representations are supplied.
  • The results separate the pure-state and mixed-state regimes more sharply than earlier work on the symmetric group alone.

Load-bearing premise

States arrive as quantum circuits and groups are nontrivial, finite, and admit efficient representations or the stellar wave-function description.

What would settle it

A polynomial-time quantum algorithm that solves the mixed-state isomorphism problem for the cyclic group of order four would falsify the QSZK-completeness claim.

read the original 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 $\cap$ 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 $\cap$ 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies the computational complexity of deciding whether two quantum states (pure or mixed), each prepared by a given quantum circuit, are related by the action of a specified group. For pure states it establishes BQP-hardness for all nontrivial groups with containment in QCMA ∩ QCSZK, plus refined results: reduction to state HSP over the generalized dihedral group for abelian groups, GI-hardness for the Clifford group, and BQP-completeness for the Pauli group. For mixed states it proves QSZK-completeness for nontrivial finite efficiently representable groups. For bosonic linear optical unitaries in the stellar representation it shows GI-hardness and containment in NP ∩ SZK. The work resolves an open question from [HEC25] by proving that the abelian mixed-state hidden subgroup problem is QSZK-hard in the worst case.

Significance. If the stated reductions hold, the results provide a broad complexity map for quantum state isomorphism problems that extends prior work limited to the symmetric group. The QSZK-completeness for mixed states and the explicit QSZK-hardness for the abelian mixed-state HSP are the strongest contributions, as they rule out efficient quantum algorithms unless QSZK = BQP. The polynomial-time reductions to graph isomorphism for Clifford and bosonic cases, together with the pure-state containments, give concrete anchors in the quantum complexity hierarchy. The handling of both finite and infinite groups (via stellar representation) and the circuit-model input assumption are technically useful.

major comments (2)
  1. [Mixed-state isomorphism theorem] The QSZK-completeness claim for mixed-state isomorphism (abstract and main theorem on finite groups) rests on an explicit reduction whose tightness is not visible in the provided abstract; the proof must confirm that the reduction preserves the worst-case hardness for efficiently representable groups without additional assumptions on the group action.
  2. [Abelian mixed-state HSP section] The resolution of the [HEC25] open question via QSZK-hardness of the abelian mixed-state HSP is load-bearing; the reduction must be shown to apply directly to the standard circuit-model input and the generalized dihedral group without hidden parameters that would weaken the implication that no efficient quantum algorithm exists unless QSZK = BQP.
minor comments (2)
  1. [Abstract and introduction] The abbreviation QCSZK appears in the pure-state containment statement; a brief definition or reference to its standard meaning should be added on first use.
  2. [Bosonic linear optical section] For the bosonic case, the stellar representation is invoked for the classical description; a short paragraph clarifying how the wave-function representation is encoded as input would improve readability for readers outside quantum optics.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the positive recommendation of minor revision. The comments highlight important aspects of our proofs that we will clarify in the revised manuscript. We address each major comment below.

read point-by-point responses

  1. Referee: [Mixed-state isomorphism theorem] The QSZK-completeness claim for mixed-state isomorphism (abstract and main theorem on finite groups) rests on an explicit reduction whose tightness is not visible in the provided abstract; the proof must confirm that the reduction preserves the worst-case hardness for efficiently representable groups without additional assumptions on the group action.

    Authors: The reduction establishing QSZK-completeness for mixed-state isomorphism under nontrivial finite efficiently representable groups is fully detailed in Section 4 of the full manuscript. It is a direct polynomial-time many-one reduction from a canonical QSZK-complete problem (the mixed-state version of the hidden subgroup problem) that preserves the worst-case hardness. The group action is the standard one (unitary conjugation for mixed states), and efficient representability is defined precisely as the existence of polynomial-size quantum circuits for group elements, with no additional assumptions required. The abstract summarizes the result, but to address visibility, we will expand the abstract slightly and add a remark in the theorem statement highlighting that the reduction is tight and applies without hidden parameters. revision: partial

  2. Referee: [Abelian mixed-state HSP section] The resolution of the [HEC25] open question via QSZK-hardness of the abelian mixed-state HSP is load-bearing; the reduction must be shown to apply directly to the standard circuit-model input and the generalized dihedral group without hidden parameters that would weaken the implication that no efficient quantum algorithm exists unless QSZK = BQP.

    Authors: In Section 5, we provide an explicit reduction from a QSZK-complete problem to the abelian mixed-state hidden subgroup problem over the generalized dihedral group. This reduction takes as input the standard circuit-model descriptions of the mixed states and directly constructs instances for the generalized dihedral group without any hidden parameters or additional assumptions. The construction ensures that the hardness is worst-case, directly implying that an efficient quantum algorithm for this problem would collapse QSZK to BQP. We will revise the manuscript to include a dedicated paragraph in Section 5 explicitly stating these properties of the reduction to make the load-bearing nature clear. revision: yes

Circularity Check

0 steps flagged

No significant circularity; results via explicit reductions to known problems

full rationale

The paper derives its complexity results (BQP-hardness, QSZK-completeness, reductions to graph isomorphism and hidden subgroup problems) through explicit polynomial-time reductions and containments in standard classes like QCMA ∩ QCSZK. These steps rely on established definitions of group actions, quantum circuits, and prior results from [LG17] and [HEC25] without any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations that collapse the argument. The resolution of the [HEC25] open question follows directly from the new reductions rather than presupposing them. No equations or steps in the provided text reduce by construction to the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on standard assumptions from quantum complexity theory and group representation theory without introducing new free parameters or postulated entities.

axioms (2)
  • domain assumption Quantum states are prepared by polynomial-size quantum circuits in the standard circuit model.
    The problem input is defined via quantum circuits that prepare the states.
  • domain assumption Group actions and representations are efficiently computable or representable as stated for the groups considered.
    Required for the reductions and completeness claims for specific groups such as Pauli, Clifford, and bosonic linear optical unitaries.

pith-pipeline@v0.9.0 · 5647 in / 1388 out tokens · 58610 ms · 2026-05-14T20:27:43.329225+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages · 12 internal anchors

  1. [1]

    Physical Review A , volume=

    Multiphoton states related via linear optics , author=. Physical Review A , volume=. 2014 , publisher=

    work page 2014

  2. [2]

    Is Quantum Mechanics An Island In Theoryspace?

    Is quantum mechanics an island in theoryspace? , author=. arXiv preprint quant-ph/0401062 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    arXiv preprint arXiv:2102.05227 , year=

    Continuous variable quantum advantages and applications in quantum optics , author=. arXiv preprint arXiv:2102.05227 , year=

    work page arXiv

  4. [4]

    Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    The state hidden subgroup problem and an efficient algorithm for locating unentanglement , author=. Proceedings of the 57th Annual ACM Symposium on Theory of Computing , pages=

    work page

  5. [5]

    arXiv preprint arXiv:2505.15770 , year=

    The abelian state hidden subgroup problem: Learning stabilizer groups and beyond , author=. arXiv preprint arXiv:2505.15770 , year=

    work page arXiv

  6. [6]

    Physical Review Letters , volume=

    Stellar representation of non-Gaussian quantum states , author=. Physical Review Letters , volume=. 2020 , publisher=

    work page 2020

  7. [7]

    Journal of the ACM (JACM) , volume=

    A complete problem for statistical zero knowledge , author=. Journal of the ACM (JACM) , volume=. 2003 , publisher=

    work page 2003

  8. [8]

    Physical Review Letters , volume=

    Quantum computation over continuous variables , author=. Physical Review Letters , volume=. 1999 , publisher=

    work page 1999

  9. [9]

    Physical review letters , volume=

    How to decompose arbitrary continuous-variable quantum operations , author=. Physical review letters , volume=. 2011 , publisher=

    work page 2011

  10. [10]

    arXiv preprint arXiv:2510.08545 , year=

    Energy, bosons and computational complexity , author=. arXiv preprint arXiv:2510.08545 , year=

    work page arXiv

  11. [11]

    arXiv preprint arXiv:2509.14658 , year=

    Composable logical gate error in approximate quantum error correction: reexamining gate implementations in Gottesman-Kitaev-Preskill codes , author=. arXiv preprint arXiv:2509.14658 , year=

    work page arXiv

  12. [12]

    arXiv preprint arXiv:2509.18854 , year=

    Trading modes against energy , author=. arXiv preprint arXiv:2509.18854 , year=

    work page arXiv

  13. [13]

    Nature Communications , year=

    Factoring an integer with three oscillators and a qubit , author=. Nature Communications , year=

    work page

  14. [14]

    Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems

    Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems , author=. arXiv preprint arXiv:2604.19625 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  15. [15]

    Proceedings of the Royal Society of London

    On the multiplication of successions of Fourier constants , author=. Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character , volume=. 1912 , publisher=

    work page 1912

  16. [16]

    How to generate random matrices from the classical compact groups

    How to generate random matrices from the classical compact groups , author=. arXiv preprint math-ph/0609050 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  17. [17]

    The Church of the Symmetric Subspace

    The church of the symmetric subspace , author=. arXiv preprint arXiv:1308.6595 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    Energy-constrained diamond norm with applications to the uniform continuity of continuous variable channel capacities

    Energy-constrained diamond norm with applications to the uniform continuity of continuous variable channel capacities , author=. arXiv preprint arXiv:1712.10267 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  19. [19]

    2018 , publisher=

    High-dimensional probability: An introduction with applications in data science , author=. 2018 , publisher=

    work page 2018

  20. [20]

    Bosonic Quantum Computational Complexity

    Bosonic quantum computational complexity , author=. arXiv preprint arXiv:2410.04274 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  21. [21]

    PRX Quantum , volume=

    Hybrid oscillator-qubit quantum processors: Instruction set architectures, abstract machine models, and applications , author=. PRX Quantum , volume=. 2026 , publisher=

    work page 2026

  22. [22]

    Canadian Journal of Physics , volume=

    Matrix decompositions in quantum optics: Takagi/autonne, bloch--messiah/euler, iwasawa, and williamson , author=. Canadian Journal of Physics , volume=. 2024 , publisher=

    work page 2024

  23. [23]

    Gaussian states in continuous variable quantum information

    Gaussian states in continuous variable quantum information , author=. arXiv preprint quant-ph/0503237 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  24. [24]

    Reviews of modern physics , volume=

    Gaussian quantum information , author=. Reviews of modern physics , volume=. 2012 , publisher=

    work page 2012

  25. [25]

    2023 , publisher=

    Quantum continuous variables: a primer of theoretical methods , author=. 2023 , publisher=

    work page 2023

  26. [26]

    Operational interpretation of the Stabilizer Entropy

    Operational interpretation of the Stabilizer Entropy , author=. arXiv preprint arXiv:2507.22883 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  27. [27]

    Physical review letters , volume=

    Most quantum states are too entangled to be useful as computational resources , author=. Physical review letters , volume=. 2009 , publisher=

    work page 2009

  28. [28]

    Spectral Theory , pages=

    The singular numbers of the sum of completely continuous operators , author=. Spectral Theory , pages=. 1969 , publisher=

    work page 1969

  29. [29]

    Quantum statistical zero-knowledge

    Quantum statistical zero-knowledge , author=. arXiv preprint quant-ph/0202111 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  30. [30]

    Quantum State Isomorphism

    Quantum state isomorphism , author=. arXiv preprint arXiv:1709.09622 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  31. [31]

    arXiv preprint arXiv:2510.01610 , year=

    Higher moment theory and learnability of bosonic states , author=. arXiv preprint arXiv:2510.01610 , year=

    work page arXiv

  32. [32]

    Quantum , volume=

    Holomorphic representation of quantum computations , author=. Quantum , volume=. 2022 , publisher=

    work page 2022

  33. [33]

    Results in Physics , volume=

    No-go theorems for photon state transformations in quantum linear optics , author=. Results in Physics , volume=. 2023 , publisher=

    work page 2023

  34. [34]

    Science , volume=

    Random unitaries in extremely low depth , author=. Science , volume=. 2025 , publisher=

    work page 2025

  35. [35]

    Quantum interactive proofs and the complexity of separability testing

    Quantum interactive proofs and the complexity of separability testing , author=. arXiv preprint arXiv:1308.5788 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  36. [36]

    Communications in Mathematical Physics , volume=

    Local random quantum circuits are approximate polynomial-designs , author=. Communications in Mathematical Physics , volume=. 2016 , publisher=

    work page 2016

  37. [37]

    The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002

    Limits on the power of quantum statistical zero-knowledge , author=. The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. , pages=. 2002 , organization=

    work page 2002

  38. [38]

    Nature Physics , volume=

    Predicting many properties of a quantum system from very few measurements , author=. Nature Physics , volume=. 2020 , publisher=

    work page 2020

  39. [39]

    SIAM Journal on Computing , volume=

    Quantum algorithms for some hidden shift problems , author=. SIAM Journal on Computing , volume=. 2006 , publisher=

    work page 2006

  40. [40]

    Quantum algorithm for a generalized hidden shift problem

    Quantum algorithm for a generalized hidden shift problem , author=. arXiv preprint quant-ph/0507190 , year=

    work page internal anchor Pith review Pith/arXiv arXiv

  41. [41]

    Proceedings of the 50th annual ACM SIGACT symposium on theory of computing , pages=

    Shadow tomography of quantum states , author=. Proceedings of the 50th annual ACM SIGACT symposium on theory of computing , pages=

    work page

  42. [42]

    arXiv preprint arXiv:2210.03394 , year=

    One-wayness in quantum cryptography , author=. arXiv preprint arXiv:2210.03394 , year=

    work page arXiv

  43. [43]

    Mathematical Methods in Computer Science: Essays in Memory of Thomas Beth , pages=

    An efficient quantum algorithm for the hidden subgroup problem over Weyl-Heisenberg groups , author=. Mathematical Methods in Computer Science: Essays in Memory of Thomas Beth , pages=. 2008 , publisher=

    work page 2008

  44. [44]

    SIAM Journal on Computing , volume=

    The parallel complexity of abelian permutation group problems , author=. SIAM Journal on Computing , volume=. 1987 , publisher=

    work page 1987

  45. [45]

    2010 , publisher=

    Quantum computation and quantum information , author=. 2010 , publisher=

    work page 2010

  46. [46]

    2005 , url=

    The complexity zoo , author=. 2005 , url=

    work page 2005

  47. [47]

    SIAM Journal on Computing , volume=

    Hidden translation and translating coset in quantum computing , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

    work page 2014

  48. [48]

    arXiv preprint arXiv:2203.15993 , year=

    Improved quantum algorithms for fidelity estimation , author=. arXiv preprint arXiv:2203.15993 , year=

    work page arXiv

  49. [49]

    SIAM Journal on Computing , volume=

    A subexponential-time quantum algorithm for the dihedral hidden subgroup problem , author=. SIAM Journal on Computing , volume=. 2005 , publisher=

    work page 2005

  50. [50]

    Physical review b , volume=

    Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order , author=. Physical review b , volume=. 2010 , publisher=

    work page 2010

  51. [51]

    Quantum , volume=

    Introduction to Haar measure tools in quantum information: A beginner's tutorial , author=. Quantum , volume=. 2024 , publisher=

    work page 2024