Quantum Speedups for Group Relaxations of Integer Linear Programs

1. Problem Statement

Integer Linear Programs (ILPs) are fundamental to discrete optimization but are NP-Hard. While classical solvers (e.g., branch-and-cut) are effective, they often rely on global, exhaustive search strategies that struggle to exploit local structure.

• The Challenge: Achieving super-quadratic quantum speedups for ILPs is difficult. Most quantum algorithms (like Grover's search) offer at best a quadratic speedup over unstructured search. Algorithms promising super-quadratic gains (e.g., Short Path, QAOA, Quantum Adiabatic) typically require local exploration of the feasible set and mixers that preserve feasibility.
• The Obstacle: General ILPs have complex constraints that make defining a local, feasibility-preserving search space difficult. Classical local search methods often fail because the feasible set is not easily enumerable or connected.

The authors ask: Is there a class of algorithms for general ILPs that relies on local exploration of a feasible space and is a viable candidate for super-quadratic quantum speedups?

2. Methodology

The paper proposes a framework centered on Gomory's Group Relaxation, a specific relaxation of the ILP that transforms the problem into a search over a finite abelian group.

A. The Group Relaxation

Given an ILP $\min \{c^T x : Ax=b, x \in \mathbb{Z}^n_{\ge 0}\}$, the authors select an optimal basis $B$ from the Linear Programming (LP) relaxation.

1. Relaxation: They drop the non-negativity constraints on the basic variables ($x_B$) while retaining integrality.
2. Transformation: The problem is reformulated in terms of the non-basic variables ($x_N$) using the null space of the constraint matrix.
3. Finite Abelian Group: The feasible set of this relaxation is shown to be a coset within a finite abelian group $K$ (the kernel of a linear map over a finite ring).
   • The problem becomes: $\min \{f(x) : x \in \hat{x} + K\}$, where $K$ is a finite group and $f$ is the objective function.
   • Crucially, if the group relaxation is nondegenerate (a condition stronger than LP non-degeneracy), solving this relaxation yields the exact optimal solution to the original ILP. Otherwise, it provides a tighter lower bound than the LP relaxation.

B. Classical Local Search (Markov Chain Search)

To solve the group relaxation, the authors design a feasibility-preserving local search:

1. Null Space Generation: They use the Smith Normal Form (SNF) to efficiently compute a generating set $S$ for the kernel $K$ in classical polynomial time.
2. Random Walk: They construct a Cayley walk on the group $K$ using the generators $S$.
   • Product-of-Cycles Walk: The walk moves by adding/subtracting generators. The stationary distribution is uniform over $K$.
   • Expander Walk: By randomly sampling additional elements from $K$, they construct a Cayley graph that is a spectral expander (constant spectral gap) with high probability.
3. Algorithm: A classical Markov Chain Search (MCS) samples from this walk to find the global minimum.

C. Quantum Algorithm (Generalized Short Path)

The authors apply the Generalized Short Path (SP) framework [CHO+24] to the group relaxation:

1. Hamiltonian Construction: They define a cost Hamiltonian $H$ encoding the objective function and a mixer Hamiltonian based on the Markov chain (the discriminant matrix $D(P)$).
2. State Preparation: They provide efficient quantum circuits to prepare the uniform superposition state $|\sqrt{\pi}\rangle$ over the feasible set $K$ using the generators found classically.
3. Block Encodings: They construct block-encodings for both the cost function and the mixer, satisfying the input requirements for the SP algorithm.
4. Speedup Mechanism: The algorithm performs "short jumps" and "long jumps" between ground states of interpolated Hamiltonians. Under specific spectral conditions (Log-Sobolev inequalities or constant spectral gaps), this yields a runtime of $O((|K|/|K^*|)^{1/2 - \alpha})$, where $\alpha > 0$.

3. Key Contributions

1. Feasibility-Preserving Local Search: The first competitive classical algorithm for Gomory's group relaxation based on local search over a finite abelian group, utilizing the null space formulation.
2. Super-Quadratic Quantum Speedup: A quantum algorithm that achieves a runtime of $O((|K|/|K^*|)^{1/2 - \alpha})$ for the group relaxation. This is a genuine super-quadratic improvement over classical sampling and direct Grover search ($O(\sqrt{|K|})$).
3. Constraint-Preserving Mixers: The construction of two specific mixers with favorable spectral properties:
   • Product-of-Cycles Walk: With explicit Log-Sobolev bounds.
   • Expander Walk: With a constant spectral gap, derived via the Alon-Roichman theorem.
   • These mixers allow the quantum algorithm to stay within the feasible set without penalty terms, preserving spectral efficiency.
4. Conditions for Optimality: Identification of "nondegeneracy" conditions under which the group relaxation solves the original ILP exactly, and conditions (sparsity of generators, problem hardness) under which the quantum speedup is guaranteed.

4. Results

• Theoretical Guarantees:
  • Theorem 9 & 11: Prove that under mild technical conditions (specifically regarding the sparsity of the null space generators and the magnitude of the objective function), the quantum algorithm achieves a super-quadratic speedup ($\alpha = \Theta(1)$).
  • Exactness: If the group relaxation is nondegenerate, the algorithm finds the exact ILP solution.
• Numerical Experiments:
  • Cutting Stock Problems: Tested on synthetic 1D cutting-stock instances. The group relaxation ($OPT_B$) significantly tightened the lower bound compared to the LP relaxation ($OPT_{LP}$), often closing a large percentage of the integrality gap.
  • MIPLIB 2017 Benchmarks: Applied to real-world pure ILP instances.
    • In several cases (e.g., qap10, gen02), the group relaxation provided a much tighter bound than the LP relaxation.
    • For some instances (e.g., ex10), the group relaxation was exact ($OPT_B = OPT_{ILP}$).
    • The results demonstrate that the group relaxation is a powerful tool for reducing the search space in branch-and-bound solvers.

5. Significance

• Bridging the Gap: This work addresses the "mismatch" between classical global search and quantum local search. It identifies a specific relaxation (Gomory's group relaxation) that is both applicable to general ILPs and amenable to local quantum exploration.
• Practical Quantum Advantage: By showing that the group relaxation can be solved with super-quadratic speedups and that it yields tighter bounds (or exact solutions) for real problems, the paper provides a concrete pathway for quantum advantage in operations research.
• New Primitives: The construction of feasibility-preserving mixers for finite abelian groups is of independent interest, potentially applicable to other quantum algorithms like QAOA and Quantum Annealing where maintaining feasibility is a major hurdle.
• Hybrid Potential: Even when the quantum algorithm does not solve the ILP directly, the improved bounds can accelerate classical branch-and-cut solvers, suggesting a viable hybrid quantum-classical workflow.

In summary, the paper successfully demonstrates that by reformulating ILPs into group relaxations, one can construct local search algorithms that are both classically competitive and amenable to super-quadratic quantum speedups, offering a promising direction for solving discrete optimization problems on future quantum hardware.