Quantum state isomorphism problems for groups

arXiv:2605.12615 · quant-ph, cs.CC · Submitted 2026-05-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Quantum state isomorphism problems for groups".

Mira: Quantum state isomorphism problems for groups investigate whether two quantum circuits preparing states are related by an action of a group,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So, we're diving into "Quantum state isomorphism problems for groups" today. It sounds like a paper that tackles how to tell if two quantum states are related by some kind of symmetry group action. I'm curious what the authors were trying to achieve with this specific problem framing.

Mira: Exactly, Kai; it’s about checking if two quantum circuits preparing states are equivalent under an action of a group. It’s like asking if two different preparations are just different views of the same underlying physical structure, which is really interesting when you think about how we characterize physical systems.

Lev: From a complexity standpoint, I'm interested in whether this problem lands in BQP or something harder; for real hardware running these kinds of checks, knowing the complexity class is crucial for planning any kind of experimental verification.

Kai: Right, Lev; the paper does show that for pure states, this problem is BQP-hard for all nontrivial groups. That’s a significant result because it tells us there’s no easy way to check this equivalence without potentially solving a hard problem in quantum computation itself.

Mira: I think what's compelling is how they relate this to the State Hidden Subgroup Problem, which is already known for classical groups, so they're extending that idea into the quantum realm.

Lev: And when you talk about BQP-hard, that means any efficient quantum algorithm we have for solving it would imply a major complexity collapse unless P equals BQP or something similar.

Kai: That's the point; it sets a high bar for what we expect to be able to do efficiently in this area. This paper is looking at the state hidden subgroup problem in a quantum context, which is basically finding that group action from just two states.

Mira: It’s moving beyond just abstract math and connecting these isomorphism questions directly to the actual physical preparation of quantum states we use today.

Lev: And I wonder how much overhead we'd need for error correction if we tried to run the verification protocols suggested by this result on a noisy device.

The paper's summary: Kai: So, looking at the summary of "Quantum state isomorphism problems for groups," it seems the authors tackle both pure and mixed states under group actions. They establish that for pure states, we have BQP-hardness, and for mixed states, they show QSZK-completeness across all nontrivial finite groups G.

Mira: That's a substantial claim; proving QSZK-completeness for every nontrivial finite group G in the mixed state version suggests this problem is quite versatile and hard across a whole family of physical systems.

Lev: Being QSZK-complete means that if you could solve this problem efficiently, you could solve any problem in the QSZK class, which is already a pretty strong statement about computational difficulty.

Kai: It’s not just about pure states; they also show containment results, like that the pure state version is contained in QCMA and QCSZK for certain parameters. This gives us some upper bounds on what might be achievable efficiently.

Mira: And for the abelian groups specifically, they connect it to an approximate version of StateHSP over the generalized dihedral group, which is a more classical structure that we can actually analyze with existing tools.

Lev: That reduction to approximate StateHSP is encouraging because it means we have a concrete classical problem we can work on, even if the quantum version is harder.

Kai: It really highlights how these quantum state isomorphism problems are deeply connected to both high-level complexity theory and specific structural problems in group theory.

The paper's improvements: Mira: Now let's discuss the improvements suggested by this work; one key improvement is the connection between mixed states and the QSZK-complete nature for any nontrivial finite group G.

Kai: That’s because they reduce from Quantum State Distinguishability, QSD, showing that if states aren't isomorphic under a group action, their twirled versions become distinguishable with large trace distance. That’s a very practical link to experimental distinguishability.

Lev: If it reduces from QSD, then any efficient way to solve state isomorphism would immediately give us a way to efficiently distinguish non-isomorphic quantum states, which is useful for error detection in experiments.

Kai: Also, the paper points out that for abelian groups containing an involution or the Pauli group, Mixed StateHSP becomes QSZK-hard, which implies we can’t expect efficient quantum algorithms unless QSZK equals BQP.

Mira: And they also showed containment results where (α, β)-PSGIG is contained in QCSZK for some constant α and β equal to one minus one over a polynomial in n for any efficiently represented finite group G.

Lev: That containment result is important because it shows that while the problem might be hard in general, there are certain restrictions where we can manage the complexity with small errors or parameters.

Kai: It seems they’re providing both a high-level hardness proof and some practical ways to bound the difficulty based on group structure, which is very useful for experimentalists trying to set realistic goals.

Conclusion: Mira: So, wrapping up the discussion on "Quantum state isomorphism problems for groups," we’ve seen that the paper shows pure state versions are BQP-hard and mixed states are QSZK-complete across all nontrivial finite groups G.

Kai: It really seems like this paper solidifies the idea that checking symmetry in quantum states isn't a trivial task, especially when dealing with different group structures.

Lev: For me, the implication is that we need to be very careful when designing experiments involving state preparation because we have to consider these computational bottlenecks before we even start worrying about decoherence.

Kai: Exactly; this paper gives us concrete complexity bounds, showing where the computational limits lie for characterizing quantum states based on their group properties.

Mira: It opens up avenues for applying these ideas to understand the fundamental structure of quantum information and how symmetry plays a role in state classification across different physical regimes.

IBM Research · Tufts University · University of Waterloo

quant-ph, cs.CC

Submitted: 2026-05-12

Updated: 2026-09-30

Comments: Updated definition of PSGI to a more natural version which ignores global phase; updated proofs to fit this new definition

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 90/100

The gist: Quantum state isomorphism problems for groups investigate whether two quantum circuits preparing states are related by an action of a group, establishing that mixed-state isomorphism over finite

Key concepts

Pure State Group Isomorphism (PSGI)
This problem asks if two quantum states can be transformed into each other by applying a specific action of a finite group G. The paper shows that for any non-trivial, efficiently representable group G, solving this is at least as hard as the BQP problem, meaning it requires significant computational power.
Mixed State Group Isomorphism
This version asks if two mixed quantum states are related by a group action. The paper demonstrates that this problem is QSZK-complete for any finite group G. This means it is one of the hardest problems in the complexity class QCSZK, making it difficult to solve efficiently.
Bosonic Group Isomorphism
This extends the study to infinite-dimensional systems using bosonic linear optical unitaries (transformations). For certain core states, this problem is shown to be at least as hard as Graph Isomorphism for three photons, establishing a lower bound on its computational difficulty.

Terminology

Summary

Quantum state isomorphism problems for groups investigate whether two quantum circuits preparing states are related by an action of a group, establishing that mixed-state isomorphism over finite groups is QSZK-complete and providing complexity results across various group families.

The gist

Mixed-state isomorphism over finite groups is QSZK-complete, and pure state versions are BQP-hard for all nontrivial groups, with specific hardness results for the Pauli group (BQP-complete) and the Clifford group (Graph Isomorphism-hard).

Pure State Group Isomorphism Problems

The paper proves several results concerning the pure state version of the problem. For any nontrivial, efficiently representable finite group G, (α, β)-PSGI[G] is shown to be BQP-hard. Specific hardness results include:

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.

The paper also establishes containment results:

  1. (α, β)-PSGI[G] is contained in QCSZK for some constant α and β = 1 − 1/poly(n) for any efficiently represented finite group G.

  2. For abelian G, (α, β)-PSGI[G] reduces to an approximate version of StateHSP[G⋉Z2].

Mixed State Group Isomorphism Problems

The mixed-state version of the problem is shown to be QSZK-complete for any nontrivial finite group G. The paper demonstrates this by reducing from the canonical QSZK-complete problem, Quantum State Distinguishability (QSD). Specifically, it shows that if two states are not isomorphic under a group action, the resulting twirled states will have large trace distance for sufficiently large k, making them distinguishable. Furthermore, for abelian groups containing an involution or the Pauli group, Mixed StateHSP is shown to be QSZK-hard.

Bosonic Group Isomorphism Problems

The study extends to infinite-dimensional systems using bosonic linear optical unitaries as the group action. For succinctly represented families of bosonic states (core states), the problem is shown to be at least as hard as Graph Isomorphism for r=3 photons, establishing a GI-hardness lower bound. The general problem is contained in NP and SZK for certain parameter choices.

Applications and Connections

The paper connects state isomorphism problems to other computational problems:

  1. State isomorphism is the quantum analog of the Hidden Shift Problem, where one wishes to find a “shift,” given by the action of a group element, that maps one quantum state to another.

  2. The pure-state problem for abelian groups reduces to StateHSP for the generalized dihedral group.

  3. For mixed states, it is shown that the mixed StateHSP problem is QSZK-hard for any abelian group containing an involution or the Pauli group, ruling out efficient quantum algorithms unless QSZK = BQP.

The work also addresses open questions regarding tighter bounds and the possibility of extending the abelian StateHSP framework to mixed states in general. The bosonic variant initiates a study of Gaussian isomorphism problems between states under linear optical transformations.

Technical Tools and Reductions

The proofs utilize several key techniques:

Classical shadows procedure:

The containment in QCSZK for pure states is proven by replacing quantum messages with classical shadows, which is possible for pure states using an efficient procedure to construct the classical shadow.

Reductions:

BQP-hardness is established via reduction from the BQP-complete problem of deciding whether a quantum circuit accepts or rejects. Graph Isomorphism hardness for Clifford groups is shown by constructing specific states involving graph states and magic states, leveraging Lemma 4.7 to show that a high overlap implies the unitary must be a permutation.

Bosonic Equivalence:

The isomorphism of core states under linear optical transformations is equivalent to an isomorphism over qudits with large d, specifically relating it to the product unitary group. This connection is formalized using the notation where R(U) denotes the corresponding unitary on the Hilbert space of n modes.

Robust Reductions:

For mixed states, a robust reduction from PSGI to approximate StateHSP over G⋊Z2 is presented, which allows for completeness error ε and soundness α to be controlled by polynomial functions of n. This shows that the problem remains hard even under imperfect completeness and soundness parameters.

Complexity Classes:

The results place pure state isomorphism between BQP and QCSZK ∩ QCMA, while mixed-state isomorphism is QSZK-complete for all finite groups G. The bosonic problem is shown to be at least as hard as Graph Isomorphism for r=3 photons.

Improvements for AI systems

As a fastidious and diligent researcher, I have analyzed this paper on quantum state isomorphism problems under group actions. The results provide several deep theoretical connections between complexity theory (BQP, QCSZK), classical problems (Graph Isomorphism), and physical systems (bosonic/continuous variable states).

Here are the specific improvements to AI systems that can be derived from these findings:

)AI System Improvements Derived from the Paper"

The core improvements focus on developing quantum-aware decision-making, learning hidden symmetries, and robust verification protocols. Specifically:

  1. //Quantum Symmetry Learning and Classification

  2. //Robust Quantum State Verification Protocols (QSZK/QCSZK)

  3. //Efficient Group Structure Inference in Quantum Data

  4. //Modeling Continuous Variable Systems for Complex Tasks

Here are the specific capabilities the improved AI system can possess:

  1. //Quantum Symmetry Learning and Classification

  2. This system can perform complex classification tasks on quantum data by identifying hidden symmetries, which is analogous to solving State Isomorphism Problems (PSGI).

  3. It can determine if two quantum circuits or states are related by an arbitrary group action (e.g., Pauli, Clifford, or other finite groups), effectively classifying them up to that symmetry.

  4. It can distinguish between different classes of quantum states based on their relationship under group actions (e.g., distinguishing pure vs. mixed state orbits).

3//Robust Quantum State Verification Protocols (QSZK/QCSZK)

  1. The system can implement highly efficient, zero-knowledge verification protocols for quantum states that are related by a group action, leveraging the QCSZK containment results.

  2. It can verify the relationship between two quantum inputs without revealing the underlying structure of the group action itself, provided a classical shadow procedure exists (for pure states) or an approximate t-design is used (for mixed states).

  3. For mixed states, it can distinguish whether two density matrices are isomorphic under a group action by checking if they are far from each other under all possible group actions, using the QSZK-hard result.

4//Efficient Group Structure Inference in Quantum Data

  1. The system can infer the underlying symmetry group of a quantum process or state from noisy measurements, especially when the system is modeled using Gaussian/continuous variable formalisms (e.g., in condensed matter physics).

  2. It can use statistical sampling techniques (like Fourier sampling over group elements) to efficiently search for hidden subgroups or specific group elements that stabilize a given quantum state, which is crucial for solving State Hidden Subgroup Problems (SHSP).

  3. It can utilize the reduction from Group Isomorphism to solve Graph Isomorphism problems in specific regimes (e.g., using Clifford groups), implying it can solve related classical structure problems efficiently when mapped to quantum states.

5//Modeling Continuous Variable Systems for Complex Tasks

  1. The system can model and analyze continuous variable bosonic systems (like those described by the stellar representation) to perform isomorphism checks under Gaussian transformations (linear optical unitaries).

  2. It can determine if two continuous-variable quantum states are related by a linear optical transformation, which is vital for simulating quantum optics experiments or analyzing topological phases in condensed matter.

  3. It can assess the complexity of state equivalence in infinite-dimensional Hilbert spaces using tools like stellar rank and Gaussian orbits, allowing for the characterization of physical states relevant to continuous variable computation.

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.

Sources

Related papers