Rigetti and Purdue University Demonstrate Quantum Preconditioning Framework for Constrained Optimization

Quantum computing developer Rigetti Computing and researchers from Purdue University have published joint research extending Rigetti's quantum preconditioning framework to hard-constrained combinatorial optimization problems. By using two-point variable correlations extracted from shallow Quantum Approximate Optimization Algorithm (QAOA) circuits to modify the objective function of commercial Mixed-Integer Programming (MIP) solvers, the team demonstrated that quantum preconditioning can guide classical branch-and-bound searches to near-optimal solution thresholds up to 100 times faster than unpreconditioned runs.

Augmenting Branch-and-Bound via Quantum Correlation Matrices

Combinatorial optimization under hard constraints—such as graph partitioning for parallel scientific computing and logistics routing—remains NP-hard, forcing exact classical solvers like Gurobi to navigate massive search trees. The quantum preconditioning framework uses a gate-based QPU as a structure-learning pre-processor rather than a standalone solver:

• Correlation Matrix Generation: The algorithm runs a shallow QAOA circuit on the problem graph, enforcing balance constraints as a soft penalty parameter (ρ) within the cost Hamiltonian. Measuring the resulting quantum state yields a two-point correlation matrix (Z_ij) that captures pairwise decision-variable alignments.

• Hard-Constrained MIP Execution: The correlation matrix replaces the original edge-weight matrix (W_ij) in the objective function. Gurobi then solves this preconditioned problem while enforcing the original balance constraint as an explicit, uncompromised hard constraint.

• Accelerated Incumbent Discovery: Callback trajectory data shows that the preconditioned objective allows the classical solver's branch-and-bound algorithm to make better branching decisions and discover high-quality feasible solutions significantly earlier in the search process.

Benchmark Results and Parameter Transferability

Evaluated across 50 dense, all-to-all connected graph instances (n = 40), the framework enabled Gurobi to reach solutions within 1% of the baseline global optimum in under a second—compared to hours for unpreconditioned runs. Notably, the majority of the preconditioning advantage was captured at p = 1, minimizing circuit depth and exposure to quantum gate noise. To avoid high variational optimization costs as problem sizes scale, the team successfully transferred rescaled QAOA parameters (γ_ℓ ∝ 1/√n) optimized at n = 20 to larger graph instances without performance degradation.

Review the full research paper on arXiv (arXiv:2608.28842) here.

September 2, 2026