A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

Technical Summary: General Hamiltonian Reduction for Higher-Order Ising-Like Models

Problem Statement
The Ising model is a standard framework for encoding combinatorial optimization problems, where finding the ground state corresponds to finding the optimal solution. While heuristic solvers (e.g., quantum annealing, simulated bifurcation) have advanced, they often struggle with the combinatorial explosion inherent in large-scale instances. A common preprocessing strategy is Hamiltonian reduction, which aims to decrease the number of logical variables by identifying subsets of spins that maintain fixed relative configurations across all ground states.

Existing reduction techniques, such as FastHare and roof duality, are primarily designed for second-order (quadratic) Ising models. However, many practical optimization problems, including satisfiability and higher-order network models, naturally formulate as higher-order Ising-like Hamiltonians containing multi-body interactions. Current methods cannot directly handle these higher-order terms, and while order-reduction techniques exist to convert higher-order problems to quadratic ones, they often introduce auxiliary variables, increasing problem size. There is a lack of specialized Hamiltonian reduction schemes for general-order interactions.

Methodology
The authors propose GeneralHare (GH), a framework that generalizes the theory of non-separable groups (NGs) to arbitrary-order Ising-like models. The core methodology involves three main components:

1. Generalized Non-Separable Groups (gNGs):
   The paper extends the definition of NGs (where all spins in a group share the same sign in all ground states) to gNGs. A gNG is a subset of spins that maintains a specific relative configuration (e.g., $\sigma_a = -\sigma_b = \sigma_c$) in all ground states, or its global inverse. This allows for the merging of spins with complex internal correlations, not just identical ones.

2. Computable Criteria for Identification:
   Calculating the exact non-separability index (the energy gap between separating and non-separating configurations) is NP-hard. To make the algorithm tractable, the authors derive easily computable lower bounds ($\hat{\nu}_H(X)$) for the non-separability index.

   • The method decomposes the Hamiltonian by interaction order ($m$).
   • It utilizes a lower bound estimation that avoids minimizing over all possible spin configurations, instead considering specific bisections of the candidate group $X$.
   • If the lower bound $\hat{\nu}_H(X) > 0$, the group is identified as a non-separable group. If $\hat{\nu}_H(X) = 0$, it is treated as a "weakly" non-separable group.

3. The GeneralHare Algorithm:
   The scheme operates iteratively in rounds until no further reductions are possible:

   • Node Fixation: Before identifying groups, nodes with linear terms (biases) that dominate their local interactions are fixed to specific values ($\pm 1$), effectively removing them and reducing the order of incident hyperedges.
   • Identification: The algorithm scans hyperedges (up to a size limit $\xi$) to detect gNGs and weakly gNGs using the derived lower-bound criteria.
   • Enlargement: Using the "closure under union" property, overlapping gNGs are merged to form larger groups.
   • Compression: Identified groups are merged into single nodes. This involves flipping spins to align relative configurations, merging nodes, and aggregating weights of parallel hyperedges. Additive constants resulting from this process are tracked to preserve the ground-state correspondence.
   • Optimization: To improve speed, the algorithm restricts candidate searches to updated neighborhoods and employs simultaneous merging of independent weakly gNGs.

Key Results
The authors benchmarked GeneralHare on synthetic hypergraphs (Erdős-Rényi and Scale-Free) and public higher-order network datasets (e.g., contact networks, email networks).

• Reduction Performance:
  • On synthetic data, GeneralHare achieves significant reduction ratios (up to ~50% on sparse scale-free hypergraphs).
  • Reduction efficiency decreases as graph density (average degree) increases and as the interaction order rises (fourth-order graphs showed roughly half the reduction ratio of third-order graphs).
  • On real-world datasets, reduction ratios ranged from 2.1% to 67.4%, with 5 out of 7 instances exceeding 20%.
• Comparison with FastHare (Second-Order Case):
  • When applied to second-order Ising models, GeneralHare outperforms the standard FastHare algorithm in terms of reduction ratio, identifying more non-separable groups due to its generalized criteria.
  • GeneralHare incurs a higher computational runtime on very small graphs but scales efficiently, showing a crossover point (becoming faster or comparable) at approximately 5,000 nodes.
• Integration with Order Reduction:
  • The paper evaluates a pipeline combining GeneralHare with order-reduction (quadratization) and downstream solvers.
  • Results indicate that applying GeneralHare before quadratization (specifically using a conservative demonstrator GH_minimal) results in a lower final variable overhead compared to applying FastHare after quadratization.
  • The most effective strategy identified is a combined pipeline: GeneralHare $\to$ Quadratization $\to$ FastHare.

Significance and Claims
The paper claims that GeneralHare establishes a foundation for Hamiltonian reduction in higher-order Ising-like optimization problems. Its primary contributions are:

1. Theoretical Extension: It successfully generalizes non-separability theory from second-order to arbitrary-order models, addressing the lack of such techniques for higher-order interactions.
2. Practical Efficiency: It provides a preprocessing tool that reduces the logical size of problems, potentially improving the performance of downstream heuristic solvers (both classical and quantum-inspired) by reducing the search space.
3. Preservation of Ground States: The method guarantees that the ground states of the reduced Hamiltonian correspond to the ground states of the original problem via an explicit reconstruction map.

The authors note that while the method is generally applicable, its effectiveness may vary depending on the problem structure (e.g., homogeneous degree distributions in 3-SAT problems may yield lower reduction ratios). They suggest future work could involve combining this approach with specialized solvers like SAT solvers for specific problem classes.