Iterative Quantum Optimization: From Greedy Reductions to Branch-and-Bound

Abstract

Iterative quantum optimization (IQO) uses quantum-generated information to select a sequence of classical problem reductions. We introduce Bound-Aware Tree-IQO which combines this iterative structure with bounds and reversible search. Feasible measured samples update a shared incumbent, while valid classical bounds prune branches that cannot improve it. Incorporating backtracking yields an anytime method that returns the best feasible solution found when interrupted, or can be run as a complete search to return and certify the optimum. For suitable single-variable or pairwise reductions, an initial IQO path can determine the branching schedule without further quantum calls, though certifying the optimum may take superpolynomial classical time. To motivate our framework, we prove two limitations of irreversible IQO reductions based on the quantum approximate optimization algorithm (QAOA). We show an infinite family of unweighted MaxCut instances on which globally optimized level-1 QAOA makes standard Recursive QAOA strictly prefer a first reduction that excludes every optimal solution, and limits that branch to an approximation ratio of at most $2/3+o(1)$. In contrast, a single backtrack recovers an optimal solution using the same quantum information. Causal cone arguments give a complementary obstruction at every fixed depth of standard QAOA: a weighted MaxCut instance is shown to contain two edges with identical two-qubit reduced states, even though every optimum requires opposite edge parities. MaxCut experiments show that QAOA-guided ordering is nonrandom in exact-certification tests through $n=28$, while demonstrating that quantum samples can strengthen the incumbent and enable further pruning. Our results suggest that quantum data could provide useful guidance toward solving hard combinatorial optimization problems more effectively than either quantum or classical algorithms alone.

Iterative quantum optimization (IQO) uses quantum-derived scores to choose classical problem reductions, typically committing irreversibly to one path. This paper asks how to retain that guidance while allowing recovery from incorrect reductions and exact certification. Bound-Aware Tree-IQO combines complementary reduction branches, a shared incumbent from feasible lifted samples, and valid classical upper bounds for branch-and-bound pruning. Correctness follows from objective-preserving lifting, exhaustive branch coverage, and safe pruning. For pairwise reductions forming a spanning tree, the initial IQO path supplies a complete branching schedule: subsequent certification needs no additional quantum calls, but may require exponential classical search. The main analytical example is an infinite unweighted MaxCut family, $K_{3,m}$ with two added internal edges. For sufficiently large $m$, every globally optimized level-1 QAOA solution makes standard RQAOA strictly prefer an incorrect first relation. That branch achieves at most $(2m+2)/(3m)=2/3+o(1)$ of optimum; one root backtrack permits exact recovery in $O(m)$ time. A separate causal-cone construction gives, at every fixed QAOA depth, two edges with identical two-qubit reduced states for all global layer angles but opposite required optimal parities. This latter obstruction restricts the candidate edges rather than proving a strict all-edge trap. MaxCut simulations separate branching guidance from sample reuse. Ordering tests through $n=28$ show fewer visited nodes than random ordering, while classical comparisons depend on ensemble and configuration. Sample reuse improves incumbents and pruning. All tests use classically tractable level-1 QAOA; node counts exclude full quantum and preprocessing costs, and no end-to-end runtime advantage is established.