⚛️ quantum physics

Learning T-conjugated stabilizers: The multiple-squares dihedral StateHSP

This paper presents a polynomial-time, constant-depth quantum algorithm that solves the non-abelian state hidden subgroup problem over multiple copies of the dihedral group of order 8, enabling the learning of non-Pauli stabilizers and offering applications in Hamiltonian spectroscopy.

Original authors: Gideon Lee, Jonathan A. Gross, Masaya Fukami, Zhang Jiang

Published 2026-03-16

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Gideon Lee, Jonathan A. Gross, Masaya Fukami, Zhang Jiang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of looking for a missing person, you are looking for a hidden rule that governs a complex quantum system. This paper presents a new, highly efficient way to find that rule, even when the system is behaving in a "non-abelian" way (a fancy term for when the order of operations matters, like putting on socks before shoes is different from shoes before socks).

Here is the story of the paper, broken down into simple concepts and analogies.

The Big Mystery: The "Hidden Subgroup" Problem

In the quantum world, there's a classic puzzle called the Hidden Subgroup Problem (HSP). Imagine you have a magical machine that follows a secret set of rules (a subgroup). You can feed it inputs, and it gives you outputs. Your job is to figure out what the secret rules are just by watching the machine work.

For simple, "abelian" systems (where order doesn't matter), we already have a perfect solution. But for complex, "non-abelian" systems, it's been like trying to solve a Rubik's cube while blindfolded. Most experts thought this was nearly impossible to do quickly.

The New Twist: The "State" Version

This paper tackles a newer, more flexible version called the State Hidden Subgroup Problem (StateHSP).

Old Way: You get a function (like a black box).
New Way: You get a quantum state (a specific arrangement of qubits) that has been "stabilized" by the secret rule. Think of it like a spinning top that only stays balanced if you spin it in a specific, hidden direction.

The authors ask: Can we find this hidden direction even when the system is complex and non-abelian?

The Specific Case: The "Multiple Squares"

To test their theory, the authors focused on a specific group called the Dihedral Group of order 8 ( $D_4$ ).

The Analogy: Imagine a square piece of paper. It has 8 ways you can move it without changing its appearance: flip it left/right, flip it top/bottom, rotate it 90 degrees, 180, 270, etc.
The Setup: They took N copies of this square (imagine N squares lined up in a row). Each square can be flipped or rotated independently.
The Goal: One specific combination of flips and rotations is the "hidden involution" (the secret rule). The quantum state they are given is perfectly balanced (stable) only if you apply this specific combination.

The Problem: Why Was This Hard Before?

Usually, to find a hidden rule in quantum mechanics, scientists use a technique called Fourier Sampling. It's like shining a light through a prism to see the hidden colors.

The Catch: For these "Multiple Squares" systems, the "colors" (mathematical representations) are so huge and complex that shining the light directly just gives you static noise. It's like trying to hear a whisper in a hurricane. Previous methods required massive, impossible quantum computers to handle the noise.

The Solution: The "Magic Filter" Strategy

The authors invented a clever, step-by-step algorithm that acts like a multi-stage filter. Instead of trying to see the whole picture at once, they peel away layers of complexity until the answer pops out.

Here is their 5-step detective story:

Step 1: The "Pauli Check" (The Easy Win)

First, they check if the secret rule is simple (just a basic flip or rotation, known as a "Pauli" operation). If it is, they solve it immediately. If not, they move to the hard part.

Step 2: The "Parity Scan" (Taking a Snapshot)

They perform a special measurement on pairs of qubits (the "squares").

The Analogy: Imagine you have N pairs of shoes. You check if the left and right shoe in each pair are "matching" (even parity) or "mismatched" (odd parity).
By doing this many times, they collect a set of "snapshots." Some of these snapshots are special; they form a "Bell-resolvable set." Think of this as finding a specific pattern of matching/mismatched shoes that reveals a hidden structure.

Step 3: The "Bell Resolution" (Decoding the Pattern)

Once they have these special snapshots, they perform a second measurement (Bell measurement).

The Magic: This step effectively turns the complex, non-abelian problem into a simple, abelian one.
The Analogy: It's like taking a tangled knot of headphones and, with a specific shake, making it fall into a neat, straight line. The "noise" of the complex system is filtered out, leaving behind a simple mathematical structure (a group of bits) that is easy to read.

Step 4: The "T-Gate Rotation" (The Final Twist)

Now that the problem is simplified, they know where the hidden rule is hiding, but not exactly what it is.

They use a mathematical trick involving T-gates (a specific type of quantum rotation).
The Analogy: Imagine you know the secret code is hidden in a specific drawer, but the drawer is locked with a weird, twisted lock. They apply a "T-wrench" that twists the lock just enough so it becomes a standard keyhole.
This converts the mysterious "T-conjugated" stabilizer into a standard, easy-to-solve "Pauli" stabilizer.

Step 5: The Final Reveal

With the lock now standard, they use a well-known, fast method (Fourier sampling) to read the final answer. They have successfully identified the hidden rule.

Why Does This Matter?

It's Fast and Cheap: The algorithm is "polynomial," meaning it scales reasonably well as the problem gets bigger. More importantly, it only requires constant depth circuits.
- Analogy: Previous methods were like building a massive, 100-story skyscraper to solve a puzzle. This new method solves it with a simple, single-story house. It uses very few quantum operations, making it possible to run on today's noisy, imperfect quantum computers.
Real-World Applications:
- Learning Quantum States: It helps us figure out how quantum error-correcting codes work, which is vital for building reliable quantum computers.
- Hamiltonian Spectroscopy: It helps scientists study the energy levels of complex molecules. If you know the symmetry (the hidden rule) of a molecule, you can predict how it behaves, which is huge for drug discovery and materials science.

The Bottom Line

The authors took a problem that was thought to be too hard for non-abelian groups and solved it by breaking it down. They didn't try to fight the complexity; they used clever measurements to "abelianize" the problem (turn the complex into the simple), applied a twist to fix the remaining details, and then solved the easy version.

It's a brilliant example of how, in quantum computing, sometimes the best way to solve a hard problem is to change the perspective until the answer becomes obvious.

1. Problem Definition

The paper addresses the State Hidden Subgroup Problem (StateHSP), a generalization of the classic Hidden Subgroup Problem (HSP).

Standard HSP: Given a function $f$ that hides a subgroup $H$ , find $H$ . This is well-understood for abelian groups but difficult for non-abelian groups (e.g., the Dihedral group).
StateHSP: Given copies of a quantum state $|\Psi\rangle$ that is invariant under a hidden subgroup $H$ (i.e., $\rho(h)|\Psi\rangle = |\Psi\rangle$ for $h \in H$ ) and distinguishable from other symmetries, identify $H$ .
Specific Focus: The authors focus on the Multiple-Squares StateHSP. The hidden group is a subgroup of the direct product of $N$ copies of the Dihedral group of order 8 ( $D_4$ ), denoted $D_4^N$ .
The Hidden Element: The subgroup is generated by a single involution $h = (r^{t_1}s^{k_1}, \dots, r^{t_N}s^{k_N})$ , where $r$ is a reflection and $s$ is a rotation. The state is stabilized by the "doubled representation" $U_2^N(h)$ acting on $2N$ qubits.
Motivation: This problem models learning non-Pauli stabilizers (specifically those conjugated by T-gates) and Hamiltonian spectroscopy (identifying symmetries of a Hamiltonian). Unlike standard Pauli stabilizer learning (which is abelian), T-conjugated stabilizers introduce non-Clifford elements, making the problem non-abelian.

2. Methodology and Algorithm

The authors present a polynomial-time algorithm that solves this non-abelian StateHSP using only constant-depth circuits and O(N²) samples. The core challenge is that standard Fourier sampling fails for non-abelian groups because most irreducible representations (irreps) of $D_4^N$ have exponentially large dimensions.

The algorithm proceeds in five main steps:

Step 1: Pauli Check

First, the algorithm checks if the hidden stabilizer is a standard Pauli operator (i.e., if the rotation component $w=0$ ). If so, it uses existing abelian StateHSP techniques (Learning Pauli Stabilizers) to solve it immediately. If not, it proceeds.

Step 2: Determining the Conjugacy Class ( $w_{max}$ )

The goal is to identify the vector $w$ (representing the rotation components $k$ ) of the hidden involution.

Parity Sampling: The algorithm performs transversal $Z \otimes Z$ measurements on pairs of qubits to obtain parity outcomes $\pi$ .
Bell-Resolvable Sets: It collects a set of parity outcomes $\{\pi_m\}$ such that their sum is zero ( $\sum \pi_m = 0$ ). This specific structure allows the construction of a "Bell-resolvable set."
Abelianization: Crucially, projecting the state onto these parity subspaces transforms the non-abelian representation into a representation of the abelian quotient group $Z_2^N \times Z_2^N$ .
Bell-Resolution: The algorithm performs Bell measurements and $X$ measurements on the post-measurement states to extract irrep labels $(p, q)$ . These labels satisfy a linear constraint $q \cdot t_h + p \cdot w_h = 0$ .
Null Space Construction: By collecting enough samples, the algorithm constructs a null space $K$ containing the hidden vector $(t_h, w_h)$ .
Maximal Rotation Subroutine: From the null space, the algorithm computes $w_{max}$ by taking the bitwise OR of the $w$ -vectors in the basis of $K$ . This $w_{max}$ correctly identifies the support of the hidden rotation vector $w_h$ wherever $t_h=1$ .

Step 3: T-Gate Correction (Abelianization)

Using the derived $w_{max}$ , the algorithm applies a correction circuit consisting of T-gates (specifically $T^\dagger$ ) on qubits where $w_{max}$ is 1.

Effect: This conjugation transforms the hidden non-abelian stabilizer $U_2^N(t_h, v_h, w_h)$ into a Pauli stabilizer $U_2^N(t_h, v_h, 0)$ .
Result: The problem is reduced from a non-abelian StateHSP to a standard Abelian StateHSP (specifically, learning a Pauli stabilizer).

Step 4 & 5: Final Learning

The algorithm runs the "Learning Pauli Stabilizers" subroutine on the corrected state to identify $t_h$ and $v_h$ .
Finally, it computes the full hidden vector $w_h = t_h \odot w_{max}$ (Hadamard product).

3. Key Contributions

First Direct Solution for Non-Abelian StateHSP: The paper provides the first efficient algorithm for a non-trivial non-abelian StateHSP ( $D_4^N$ ) that does not rely on the indirect method of simulating the regular representation (which is computationally expensive).
Constant Depth Circuits: Unlike previous HSP solutions that require deep coherent control or complex multi-qubit operations, this algorithm only requires constant-depth circuits and two-qubit operations/measurements. This makes it highly suitable for near-term quantum devices.
Abelianization via Parity/Bell Sampling: The authors introduce a novel technique to "abelianize" a non-abelian problem by using parity measurements and Bell-resolvable sets to project the state onto a subspace where the group action becomes abelian ( $Z_2 \times Z_2$ ).
Application to T-Doped Stabilizers: The work directly addresses the learning of stabilizers conjugated by T-gates, a critical step in characterizing states relevant for quantum error correction (e.g., non-abelian topological order) and Hamiltonian spectroscopy.
Sample Complexity: The algorithm achieves a sample complexity of $O(\epsilon^{-2}(N^2 + \log(N/\delta)))$ , which is polynomial in the system size $N$ .

4. Results

Theorem 1: The Multiple-Squares StateHSP algorithm solves the problem with probability $> 1-\delta$ using $O(\epsilon^{-2}(N^2 + \log(N/\delta)))$ samples.
Generalization: The authors extend the algorithm to arbitrary representations of $D_4^N$ (Section VII). This requires a "partial Fourier transform" to block-diagonalize the representation, but the core logic (parity sampling $\to$ abelianization $\to$ correction) remains the same.
HSP Corollary: As a special case, the algorithm solves the standard Hidden Subgroup Problem for the Multiple-Squares group on the regular representation with $O(N^2)$ samples, offering a mild improvement over previous $O(N^3)$ solutions.

5. Significance

Bridging Theory and Practice: By reducing the resource requirements to constant depth and two-qubit gates, this work moves non-abelian HSP solutions from theoretical constructs to practical implementations on current and near-future quantum hardware.
New Paradigm for Symmetry Learning: The paper demonstrates that for certain non-abelian groups, the "hardness" of the HSP can be circumvented if one has access to specific quantum states (StateHSP) rather than just classical functions. It highlights that the structure of the representation (specifically, the ability to abelianize it via measurement) is more critical than the group structure itself.
Hamiltonian Spectroscopy: The method provides a concrete protocol for identifying symmetries in quantum many-body systems, which is essential for efficient state preparation and energy estimation in quantum simulation.
Future Directions: The work suggests that other non-abelian groups might admit efficient StateHSP solutions if their representations can be similarly "abelianized" or if they possess specific structural properties (like short derived series) that allow for efficient quotienting.

In summary, this paper presents a breakthrough in quantum learning algorithms by solving a specific non-abelian symmetry problem efficiently, using a clever combination of parity measurements and T-gate corrections to reduce the problem to a known abelian case.