Solving approximate hidden subgroup problems: quantum heuristics to detect weak entanglement

1. Problem Statement

The Hidden Subgroup Problem (HSP) is a foundational problem in quantum computing, famously solved efficiently by Shor's algorithm for integer factorization. However, finding practical applications beyond cryptography has been difficult because HSP algorithms typically require a "perfect" oracle that hides a subgroup with exact symmetry.

The paper addresses a specific variation called the Hidden Cut Problem (introduced by Bouland et al., 2024), which seeks to partition an $n$-qubit quantum state $|\psi\rangle$ into mutually unentangled subsystems (a "cut").

• The Limitation: Real-world quantum states (e.g., in quantum machine learning or simulation) rarely exhibit perfect separability. Instead, they possess hierarchical structures with weak entanglement.
• The Failure of Standard Methods: The standard Hidden Cut algorithm, designed to find perfect cuts (where subsystems are exactly unentangled), fails in these realistic scenarios. If no perfect cut exists, the algorithm returns a trivial result (no cuts), providing no insight into the weak entanglement structure that actually exists.

Goal: Develop quantum heuristics to detect approximate symmetries and identify weakly entangled qubit registers (approximate cuts) rather than just perfect ones.

2. Methodology and Theoretical Framework

The authors derive a rigorous mathematical link between the output of the Hidden Cut circuit and the entanglement structure of the input state.

A. The Hidden Cut Circuit (StateHSP)

The algorithm treats the problem as a State Hidden Subgroup Problem (StateHSP) over the group $G = \mathbb{Z}_2^n$.

• Input: $t$ pairs of copies of the state $|\psi\rangle$.
• Circuit: Uses a group register and a state register. It applies controlled SWAP operations ($SWAP_s$) conditioned on the group register, followed by a Fourier transform (Hadamard transform for $\mathbb{Z}_2^n$) and measurement.
• Standard Operation: With many copies ($t \to \infty$), the algorithm suppresses all information except for "perfect cuts" (subsystems with purity $P(s)=1$).

B. Core Theoretical Insight: The Reward Function

The paper's primary theoretical contribution is proving that the output probability distribution $p_t(x)$ of the circuit is the inverse Fourier transform of the $t$-th power of the subsystem purity function $P(s)$.

• Subsystem Purity: $P(s) = \text{Tr}(\rho_s^2)$, where $\rho_s$ is the reduced density matrix of subsystem $s$. $P(s)=1$ implies the subsystem is unentangled from the rest.
• The Relationship:
  $$p_t(x) = \frac{1}{2^n} \sum_{s} P(s)^t (-1)^{x \cdot s}$$
  Here, $P(s)^t$ acts as a reward function.
• The Role of $t$ (Number of Copies):
  • Raising $P(s)$ to the power $t$ acts as a non-linear filter.
  • Values of $P(s) < 1$ (entangled subsystems) decay exponentially as $t$ increases.
  • Values of $P(s) = 1$ (perfect cuts) remain at 1.
  • Crucial Insight: By using a small, finite number of copies ($t$), the algorithm suppresses highly entangled subsystems but preserves secondary maxima corresponding to weakly entangled (approximate) cuts.

3. Key Contributions: Two Heuristics

The authors propose two heuristics to extract approximate cuts from the measurement samples, moving away from the standard "find the nullspace" post-processing used in perfect HSP.

Heuristic 1: Early Stopping Nullspace Construction

• Mechanism: In the standard algorithm, samples are used to eliminate candidate cuts until only the trivial solution remains. This heuristic stops the elimination process early.
• Logic: Since samples with higher probability $p_t(x)$ correspond to eliminating "worse" (more entangled) candidates, the remaining candidates after a few steps are likely to be the "best" (least entangled) cuts available.
• Procedure:
  1. Run the circuit to collect samples.
  2. Iteratively eliminate candidates $s$ that do not satisfy $x \cdot s = 0$ for the most frequent samples.
  3. Stop before the solution space collapses to the trivial $\{0, 1\}$ (all-zeros/all-ones).
  4. Aggregate results over multiple runs to find the most probable approximate cuts.

Heuristic 2: Classical Estimator of Cut Quality

• Mechanism: Instead of just finding a cut, this method constructs a classical estimator $\hat{P}_t(s)$ for the purity of any arbitrary cut $s$ using the quantum samples.
• Derivation: Using the property that $E[x \cdot s] = \frac{1}{2}(1 - P(s)^t)$, the authors define an estimator based on the Hamming weight of the dot products between measurement samples $x$ and a candidate cut $s$.
  $$\hat{P}_t(s) = 1 - 2 \frac{|M s|}{m}$$
  Where $M$ is the matrix of $m$ measurement samples and $|Ms|$ is the Hamming weight.
• Significance: This allows the entanglement structure to be mapped to a classical optimization problem. One can use classical optimizers to maximize $\hat{P}_t(s)$ without needing to run new quantum circuits for every candidate $s$.
• Connection to Coding Theory: The authors note this is equivalent to the Minimum Syndrome Weight Problem in coding theory, linking quantum entanglement detection to NP-hard problems in the general case, but efficiently solvable when a strong structure exists.

4. Results and Simulations

• Simulation Setup: The authors tested the heuristics on 4-qubit and 6-qubit states, including Haar-random states and states with "planted" approximate cuts (created by entangling two separable blocks with a tunable rotation angle $\phi$).
• Performance:
  • The heuristics successfully identified the planted approximate cuts even when the entanglement was weak (small $\phi$).
  • As the number of copies $t$ increased, the algorithm correctly suppressed the signal of the weak cut, eventually failing to find it (converging to the "no cut" result), confirming the theoretical role of $t$ as a filter.
  • Scalability: The method works well for small scales (up to 8 qubits in simulations). The success depends on the "prolificness" of the cut structure (i.e., the gap between the best approximate cut and the rest of the spectrum).
• Resource Efficiency: The circuit requires only $2n$ Hadamard gates and $n$ controlled-SWAP gates. The number of input copies $t$ serves as a tunable hyperparameter to amplify the signal of specific entanglement structures.

5. Significance and Applications

• Bridging Theory and Practice: This work moves HSP algorithms from the realm of "perfect" cryptographic oracles to "approximate" physical realities. It provides a theoretical justification for why and how quantum algorithms can be useful for noisy, real-world quantum states.
• Quantum Machine Learning (QML): The method can be used to analyze the correlation structure of generative quantum models. If a model is separable across a cut, the algorithm can detect it, potentially guiding training to enforce statistical independence or identifying feature groupings.
• Quantum Simulation: It offers a tool to characterize the entanglement hierarchy in simulated physical systems (e.g., condensed matter), where understanding weak entanglement is crucial for classifying phases of matter.
• Hybrid Quantum-Classical Workflow: The second heuristic demonstrates a powerful hybrid approach where a quantum computer provides a "feature map" (samples) that is processed classically to optimize a reward function, avoiding the need for repeated quantum circuit executions for every optimization step.

Conclusion

The paper establishes that the Hidden Cut algorithm is not limited to finding perfect separations. By analyzing the relationship between the output distribution and the purity function, the authors show that using a small number of state copies allows the algorithm to act as a filter for weak entanglement. The proposed heuristics (early stopping and classical estimation) provide a practical pathway to applying HSP-based quantum algorithms to complex, non-ideal quantum systems in physics and machine learning.