Learning Grover mixers for constrained optimization

Abstract

Grover-Mixer QAOA (GM-QAOA) is a promising quantum framework for constrained combinatorial optimization. However, its practical implementation requires the efficient preparation of a uniform superposition over feasible states. In this work, we propose a two-stage variational approach. First, a parameterized quantum circuit is trained to prepare this superposition, using an entropy-based cost function that favors a uniform distribution over feasible bitstrings. The trained circuit is then embedded in GM-QAOA, where it provides both the initial state and, together with its inverse, yields the Grover mixer. The resulting method is evaluated on two representative benchmark problems: the Maximum Weight Independent Set (MWIS) problem and the Multidimensional Knapsack Problem (MKP). While the results demonstrate consistent improvements over standard QAOA for MWIS, only marginal gains are observed for MKP, with the advantage diminishing as the problem size increases. The reduced performance on MKP reflects the growing difficulty of training the variational mixer, likely due to increasingly challenging optimization landscapes. Overall, these findings highlight both the potential of variational Grover mixers and the trade-off between their performance gains and the additional resources required for their training.

Grover-mixer QAOA requires a circuit preparing a uniform superposition over feasible solutions, which is generally unavailable for arbitrary constraints. This paper replaces exact preparation with a separately trained parameterized circuit $\overline U_F$. Training maximizes the computational-basis entropy restricted to feasible bitstrings. The resulting state initializes QAOA, and $\overline U_F$ together with its inverse implements a rank-one Grover mixer. Approximate preparation permits leakage into infeasible states. Statevector simulations benchmark constraint-based Hamiltonian variational and hardware-efficient ansätze on Maximum Weight Independent Set (MWIS) and single- and two-resource knapsack problems, using 16 random instances per configuration. Mixer training uses 500 fast-simulated-annealing iterations followed by 100 COBYQA iterations. The outer QAOA uses a two-parameter linear-ramp schedule. Comparisons with penalty-based QAOA approximately match decomposed circuit depth and use the same feasibility-aware objective. For MWIS, the learned Hamiltonian-variational mixer improves both the feasibility-weighted approximation ratio and optimal-solution probability across the tested sizes, although the latter still decreases exponentially with size. Knapsack gains diminish with increasing size. Initial feasibility correlates with final feasibility and approximation ratio, with Pearson coefficients around $0.7$; residual leakage generally increases during the outer circuit. Avoiding slack variables reduces knapsack qubit requirements, allowing simulations beyond the two-resource baseline’s limit of seven decision variables. The study provides small-instance numerical evidence, without scaling guarantees. Stated limitations include increasingly difficult state-preparation training, its additional computational cost, and the possibility that deeper standard QAOA closes the performance gap. Finite-shot sampling and hardware noise remain untested.