Quantum state isomorphism problems for groups

This paper investigates the computational complexity of quantum state isomorphism problems under group actions, establishing that the pure-state version is BQP-hard for nontrivial groups with specific hardness results for abelian, Clifford, and Pauli groups, while proving the mixed-state version is QSZK-complete and resolving an open question regarding the existence of efficient quantum algorithms for the abelian state hidden subgroup problem on mixed states.

The Gist

Imagine you have two complex recipes for baking a cake. One recipe is written in a secret code, and the other is written in a different secret code. You want to know: Are these two recipes actually describing the exact same cake, just written by someone who rearranged the ingredients or changed the order of steps?

This is the core question of the paper "Quantum state isomorphism problems for groups." The authors are studying a specific type of puzzle in the quantum world: Can we tell if two quantum states (the "cakes") are the same, even if one has been transformed by a specific set of rules (the "group")?

Here is a breakdown of their findings using everyday analogies:

1. The Basic Puzzle: The "Shape-Shifting" Game

In the quantum world, a "state" is like a specific arrangement of energy or information. A "group" is a collection of allowed moves, like shuffling a deck of cards, rotating a cube, or flipping switches.

The problem asks:

• Scenario A (YES): If I take Recipe 1 and apply a specific shuffle from our rulebook, does it become identical to Recipe 2?
• Scenario B (NO): No matter how many times I shuffle Recipe 1 using our rulebook, it never looks like Recipe 2.

The authors investigated how hard it is for a computer to solve this puzzle.

2. The "Pure" Cake vs. The "Mixed" Cake

The paper splits the problem into two types of ingredients:

• Pure States (The Perfect Cake): These are quantum states that are perfectly defined, like a pristine, unblemished sphere.

  • The Finding: For almost any set of rules (groups), figuring out if two pure states are the same is extremely hard for a quantum computer. It's as hard as solving the most difficult problems a quantum computer can theoretically handle (BQP-hard).
  • The Exception (The Pauli Group): If the rules are very specific (the "Pauli group," which is like a simple set of on/off switches), the problem becomes easy. It's like realizing that if you only have two types of moves, you can solve the puzzle instantly.
  • The Graph Connection: If the rules involve the "Clifford group" (a more complex set of quantum moves), the problem is just as hard as the famous Graph Isomorphism problem. Imagine trying to figure out if two complex social networks are the same structure, just with different names for the people. This is a problem that has stumped mathematicians for decades.

• Mixed States (The Blended Smoothie): These are quantum states that are a bit "fuzzy" or a mixture of possibilities, like a smoothie where the ingredients aren't perfectly separated.

  • The Finding: For mixed states, the problem is universally hard (QSZK-complete) for almost any set of rules. It doesn't matter if the rules are simple or complex; the "fuzziness" of the mixture makes it impossible to solve efficiently with current quantum technology.
  • The Implication: This answers a big question in the field: It suggests that we likely cannot build a fast quantum algorithm to solve certain "hidden subgroup" problems if the states involved are mixed. The "fuzziness" acts as a shield against easy solutions.

3. The "Infinite" Cake: Bosonic Systems

The authors also looked at a different kind of quantum system involving light (bosons), which can be thought of as having an infinite number of ingredients (like a smoothie that can have infinite variations of sweetness).

• The Finding: Even in this infinite world, if the "cake" is simple enough (has a low "stellar rank," meaning it's not too complex), the problem of checking if two light patterns are the same is still as hard as the Graph Isomorphism problem.
• The Upper Limit: However, they found that if you have a powerful enough verifier, you can prove the answer is "No" using a method that reveals no secrets (Zero-Knowledge), meaning you can be sure the cakes are different without learning why they are different.

4. The "Magic" of Zero-Knowledge

A major part of the paper is about Zero-Knowledge Proofs. Imagine you want to prove to a friend that you know the secret combination to a safe, but you don't want to tell them the combination.

• The authors showed that for these quantum puzzles, you can prove the answer is "No, these states are different" without revealing the specific group move that would have made them match.
• They improved on previous work by showing that for "pure" states, this proof can be done using classical messages (like text on a screen) rather than sending fragile quantum particles back and forth. This makes the verification process much more practical.

Summary of the "Takeaway"

• It's Hard: Generally, checking if two quantum states are the same under a set of rules is a very difficult computational task.
• It Depends on the Rules: If the rules are the simple "Pauli" switches, it's easy. If the rules are complex (Clifford) or the states are "fuzzy" (mixed), it's very hard.
• It's Like Graph Isomorphism: For many important quantum groups, this problem is just as tough as figuring out if two complex networks are structurally identical.
• No Free Lunch: The "fuzziness" of mixed states prevents us from using efficient quantum algorithms to solve these problems, suggesting a fundamental limit to what quantum computers can do in this specific area.

In short, the paper maps out the "difficulty terrain" of a new quantum puzzle, showing us exactly where the mountains are (hard problems) and where the flat plains are (easy problems), and proving that for many cases, the terrain is too rugged for a quick quantum solution.

Technical Summary

Technical Summary: Quantum State Isomorphism Problems for Groups

1. Problem Definition

This paper investigates the computational complexity of Quantum State Isomorphism Problems under group actions. The core problem, termed the Pure State Group Isomorphism Problem (PSGI), is defined as follows:

Given two quantum circuits $C_1$ and $C_2$ preparing pure states $|\psi_1\rangle = C_1|0^n\rangle$ and $|\psi_2\rangle = C_2|0^n\rangle$, and a finite group $G$ with an efficient unitary representation $R: G \to U(2^n)$, the task is to decide whether:

• YES: There exists a group element $g \in G$ such that the real part of the overlap satisfies $\text{Re}(\langle \psi_1 | R(g) | \psi_2 \rangle) \ge \beta$.
• NO: For all $g \in G$, the magnitude of the overlap satisfies $|\langle \psi_1 | R(g) | \psi_2 \rangle| \le \alpha$.

The paper also defines a Mixed State Group Isomorphism Problem (MSGI) where the inputs are circuits preparing density matrices $\rho_1$ and $\rho_2$, and the metric is the square-root fidelity $F(\rho_1, R(g)\rho_2 R(g)^\dagger)$. Additionally, the authors study a Bosonic variant involving infinite-dimensional systems (linear optical unitaries) and states represented by their "stellar" (holomorphic) functions.

This problem is framed as the quantum state analog of the Hidden Shift Problem. Just as the Hidden Subgroup Problem (HSP) seeks a subgroup stabilizing a state, PSGI seeks a "shift" (group element) mapping one state to another.

2. Methodology and Technical Tools

The authors employ a combination of complexity-theoretic reductions, interactive proof protocols, and specific properties of quantum groups:

• Interactive Proofs (QCSZK/QSZK): To establish upper bounds, the authors utilize Quantum Classical Statistical Zero-Knowledge (QCSZK) and Quantum Statistical Zero-Knowledge (QSZK) protocols. A key innovation is replacing the quantum messages in standard QSZK protocols with classical shadows (randomized measurements) for pure states, allowing the communication to be entirely classical.
• Reductions to StateHSP: For abelian groups, the paper reduces PSGI to the State Hidden Subgroup Problem (StateHSP) over the generalized dihedral group $G \rtimes \mathbb{Z}_2$. This leverages the connection between the Hidden Shift and Hidden Subgroup problems.
• Group-Specific Properties:
  • Pauli Group: The authors exploit the fact that the two-copy Pauli group is abelian, allowing the problem to be solved via weak Fourier sampling.
  • Clifford Group: Hardness is established by constructing specific states (involving "magic" states and graph states) that force any Clifford isomorphism to be a permutation, thereby reducing the problem to Graph Isomorphism (GI).
  • Bosonic Systems: The authors utilize the stellar representation of bosonic states. They leverage the mathematical fact that linear transformations preserving the $\ell_3$ norm (associated with cubic terms in the stellar polynomial) must be permutations, enabling a reduction from GI.
• Trace Inequalities: For mixed states, the proof of containment in QSZK relies on Rotfel'd's inequality to bound the fidelity of twirled states, demonstrating that non-isomorphic states become statistically distinguishable after averaging over the group.

3. Key Contributions and Results

A. Pure State Complexity

• General Upper Bound: For any efficiently representable finite group, PSGI is contained in QCSZK. This improves upon previous results for the symmetric group by eliminating the need for quantum communication in the verifier-prover protocol.
• General Lower Bound: PSGI is BQP-hard for all nontrivial, efficiently representable groups.
• Pauli Group: The problem is BQP-complete. The authors show that while the Pauli group is non-abelian, its "two-copy" version is abelian, allowing efficient quantum solution via StateHSP techniques.
• Clifford Group: The problem is GI-hard (at least as hard as Graph Isomorphism). This holds even when states are restricted to polynomial stabilizer-rank states (which are classically simulatable).
• Abelian Groups: PSGI for abelian groups reduces to StateHSP over the generalized dihedral group.

B. Mixed State Complexity

• QSZK-Completeness: For any nontrivial, finite, and efficiently representable group (satisfying a trace condition ensuring no non-identity element acts as a global phase), the Mixed State Group Isomorphism Problem is QSZK-complete.
• Implication for StateHSP: As a corollary, the Mixed StateHSP problem is shown to be QSZK-hard for abelian groups containing an involution (e.g., $\mathbb{Z}_2^n$). This resolves an open question regarding the existence of efficient quantum algorithms for mixed-state versions of the StateHSP framework, suggesting they are unlikely to exist unless $\text{QSZK} = \text{BQP}$.

C. Bosonic (Infinite-Dimensional) Complexity

• Linear Optical Isomorphism: The authors study isomorphism of core bosonic states under linear optical unitaries (Gaussian transformations).
• Hardness: For states with 3 photons, the problem is GI-hard.
• Upper Bounds: The problem is contained in SZK and NP for specific parameter regimes. The containment in SZK is achieved by reducing the problem to the Statistical Difference problem using random sampling and Gaussian noise.

4. Significance and Claims

The paper claims to establish a comprehensive complexity landscape for quantum state isomorphism, generalizing previous work limited to the symmetric group [LG17].

• Resolution of Open Questions: The work resolves an open question from [HEC25] by proving that the StateHSP framework does not extend efficiently to mixed states in the worst case (due to QSZK-hardness).
• Unification of Problems: It identifies state isomorphism as the quantum analog of the Hidden Shift Problem, unifying the study of isomorphism across different group structures (finite, infinite, abelian, non-abelian).
• Complexity Class Characterization: The results delineate the boundaries between BQP, QCMA, QCSZK, QSZK, and GI. Notably, it shows that while pure-state isomorphism for Pauli groups is in BQP, the mixed-state version jumps to QSZK-complete, highlighting a significant complexity gap between pure and mixed states.
• Applications: The paper motivates the relevance of these problems to quantum error correction (Pauli frames), entanglement classification, topological phases, and cryptographic transformations, viewing them as decision problems for determining equivalence modulo symmetries.

The authors maintain a modest tone regarding future implications, noting that while they establish hardness and containment, tighter bounds (e.g., improving the upper bound for Clifford groups to BQPGI) and the development of tools for general infinite groups remain open challenges.