Quantum Preconditioning For Constrained Optimization Problems
Abstract
We study the effect of quantum preconditioning on constrained combinatorial optimization problems, focusing on balanced graph bi-partitioning. The proposed approach uses two-point correlations between decision variables derived from the Quantum Approximate Optimization Algorithm (QAOA) to construct a modified objective function that is subsequently provided to mixed-integer programming (MIP) solvers. The preconditioned MIP formulation retains the original hard constraint, and all incumbent solutions are evaluated under the original objective. Computational experiments on dense, weighted complete-graph instances show that the preconditioned problem instances reach near-optimal solutions faster, with most of the benefit already realized at the shallowest QAOA depth tested. Solver callback trajectories show this arises from earlier discovery of high-quality incumbents during the solution search. These results support a hybrid optimization framework in which quantum algorithms provide problem-specific information to guide classical exact MIP solvers.
Related
- Solving Graph Coloring Problems Using Feedback-Based Algorithm for Quantum Optimization
- Leaving Quantum Bias on the Table: Pushforwards as a Path to Quantum Advantage in Constrained Optimization
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- PACE-QAOA: Physics-Constrained Quantum Optimization for Qubit-Efficient Power System Islanding
- Circuit Design Problems in Binary Polynomial Quantum Optimization
BibTeX
@misc{ramesh2026quantum,
title = {{Quantum Preconditioning For Constrained Optimization Problems}},
author = {Anurag Ramesh and Bhuvanesh Sundar and Maxime Dupont and David E. Bernal Neira},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.28842},
eprint = {2608.28842},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.28842},
}
RIS
TY - UNPB
TI - Quantum Preconditioning For Constrained Optimization Problems
AU - Anurag Ramesh
AU - Bhuvanesh Sundar
AU - Maxime Dupont
AU - David E. Bernal Neira
PY - 2026
DA - 2026/08/28
PB - arXiv
DO - 10.48550/arxiv.2608.28842
UR - https://arxiv.org/abs/2608.28842
AB - We study the effect of quantum preconditioning on constrained combinatorial optimization problems, focusing on balanced graph bi-partitioning. The proposed approach uses two-point correlations between decision variables derived from the Quantum Approximate Optimization Algorithm (QAOA) to construct a modified objective function that is subsequently provided to mixed-integer programming (MIP) solvers. The preconditioned MIP formulation retains the original hard constraint, and all incumbent solutions are evaluated under the original objective. Computational experiments on dense, weighted complete-graph instances show that the preconditioned problem instances reach near-optimal solutions faster, with most of the benefit already realized at the shallowest QAOA depth tested. Solver callback trajectories show this arises from earlier discovery of high-quality incumbents during the solution search. These results support a hybrid optimization framework in which quantum algorithms provide problem-specific information to guide classical exact MIP solvers.
ER -