Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.00678

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

Stuart Hadfield, Lucas T. Braydwood, Eleanor Rieffel

quant-phSubmitted Oct 31, 2026• Announced Nov 3, 2026• 1 citation
arXivHTMLPDF

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.

AI Summary

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.

Little sign of AI-generated textIncremental

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Improving the Quantum Approximate Optimization Algorithm with postselection

Sami Boulebnane

Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.

arXiv:2011.05425•Nov 10, 2020•3 citations

Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers

David Bucher, Maximilian Janetschek, Michael Poppel +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-$k$-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.

quant-pharXiv:2604.02083•New Journal of Physics•Apr 3, 2026•12 citations

Quantum Relaxation Based Branch-and-Bound Algorithm

Wei‐Hao Huang, Hiromichi Matsuyama, Kohji Nishimura +1 more

Mathematical optimization is a field where the potential of quantum algorithms is actively being explored. The Quantum Approximate Optimization Algorithm (QAOA) serves as a notable quantum-classical hybrid approach aimed at solving combinatorial optimization challenges on Noisy Intermediate-Scale Quantum (NISQ) devices. In QAOA, classical variables find representation in qubits via a one-to-one mapping. A newer entrant, Quantum Random Access Optimization (QRAO), encodes problems using fewer qubits than QAOA by leveraging the Quantum Random Access Code (QRAC) to structure a problem into its Hamiltonian form. Notably, the QRAO Hamiltonian, dubbed the Quantum Relaxation Hamiltonian, boasts of a ground state energy inferior to that of the QAOA Hamiltonian. Nonetheless, the QRAO's ground state exhibits entanglement, making it starkly different from QAOA's ground state. As a workaround, preceding studies formulated solutions to the original problem using a rounding algorithm. Our research introduces the Quantum Relaxation based Branch-and-Bound (QR-BnB) algorithm. This novel method marries Quantum Relaxation and the classical exact solution strategy, Branch-and-Bound. Within the QR-BnB framework, a classical device shoulders the responsibility of the branch-and-bound operation, while its quantum counterpart dedicates itself to determining each ground state energy for the subproblem's Quantum Relaxation Hamiltonian. This fusion eliminates the prerequisite of the rounding algorithm by crafting the optimal solution through branching operations. Preliminary simulations of the QR-BnB approach attest to its capability in accurately solving a MaxCut problem. As future work, exploring its applicability on diverse combinatorial optimization problems holds promise. Our algorithm signals a step forward in harnessing NISQ devices for tackling expansive optimization challenges.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 17, 2023•2 citations

Modified recursive QAOA for exact MAX-CUT solutions on bipartite graphs: closing the gap beyond QAOA limit

Eunok Bae, Hyukjoon Kwon, V Vijendran +1 more

Abstract Quantum approximate optimization algorithm (QAOA) is a quantum–classical hybrid algorithm proposed with the goal of approximately solving combinatorial optimization problems such as the MAX-CUT problem. It has been considered a potential candidate for achieving quantum advantage in the noisy intermediate-scale quantum era and has been extensively studied. However, the performance limitations of low-level QAOA have also been demonstrated across various instances. In this work, we first analytically prove the performance limitations of the standard level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. To this end, we derive an upper bound for the approximation ratio based on the average degree of bipartite graphs. Second, we demonstrate that recursive QAOA (RQAOA), which recursively reduces graph size using QAOA as a subroutine, outperforms the standard level-1 QAOA. However, the performance of RQAOA exhibits limitations as the graph size increases. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations. Surprisingly, this modified RQAOA always finds the exact maximum cut for any bipartite graphs and even for a more general graph with parity-signed weights.

arXiv:2408.13207•Journal of Physics A Mathematical and Theoretical•Nov 18, 2025•3 citations

Quantum-Informed Graph Decomposition

Matthew Brunet, Leah Prepchuk, Rebekah Herrman

The Quantum Approximate Optimization Algorithm (QAOA) is a near-term quantum algorithm for solving combinatorial optimization problems, but its accuracy and resource requirements may scale poorly with problem size or structure, reducing its utility in practice. Approaches such as the Graph Decomposition for Optimization Algorithm (GDOA) seek to address this by iteratively reducing an input problem until it reaches a size where it can be solved using QAOA while maintaining the same optimal solution. This algorithm, however, requires solving integer programs that have exponentially many variables, and can result in suboptimal solutions, as the integer programs may contain slack terms. In this work, we propose a heuristic called the Quantum Enhanced Graph Decomposition (QEGD) algorithm. Its novelty lies in its use of QAOA as a subroutine for sparsifying a graph through local vertex-merging. The algorithm, when used to sparsify MaxCut problems that are then solved using QAOA, achieves higher approximation ratios across all tested graphs than GDOA for random 5-regular and 6-regular graphs. We then compare the time-to-solution and approximation ratio of QEGD to other QAOA variants a collection of Erdös-Rényi graphs. QEGD has higher approximation ratios on average than QAOA$^2$ and ParaQAOA on all tested graphs. It also results in higher average approximation ratios than DC-QAOA on sparse Erdös-Rényi graphs and comparable average approximation ratio on denser Erdös-Rényi graphs. However, its average wall-clock time is between 0.4\% and 5\% of the average DC-QAOA wall-clock time.

arXiv:2611.14180•Nov 10, 2026•0 citations

Symmetry-Preserving Hierarchical Quantum Approximate Optimization Algorithm with Subproblems Beyond the Qubit Limit

Zhaoyang Song, Wei Zhang, Ji Cao +2 more

The quantum approximate optimization algorithm (QAOA) is a paradigmatic variational quantum algorithm for combinatorial optimization problems, yet on current quantum devices the available qubit count and achievable circuit depth remain the main bottlenecks to its practical application. Divide-and-merge reduces the number of variables encoded in a single quantum circuit, while contraction based on coarse graining extends the effective range of shallow circuits, but existing work has not addressed both challenges simultaneously. We propose symmetry-preserving hierarchical QAOA (SP-HQAOA), in which parity sector contraction preserves the zero-field Ising structure of the effective objective at every contraction step, thereby addressing both within a single algorithm. We further prove that this reduction is the unique one with this property. Successive contractions further decouple the maximum leaf block size $B$ from the qubit limit $Q$ per quantum call, so every quantum circuit uses at most $Q$ qubits even when $B>Q$. We also establish a deterministic repair-risk bound on the possible loss in optimal value caused by each sector restriction, and the resulting bounds can be summed across contraction steps and levels of the recursive hierarchy. With depth $p=1$, SP-HQAOA attains $99.4\%$ to $99.7\%$ of the exact optimum on $N=40$ random regular MaxCut leaf blocks and, with at most $10$ qubits per circuit, $96\%$ of the classical reference for $N=500$. SP-HQAOA demonstrates the capacity to use shallow quantum circuits to address combinatorial optimization problems whose variable count far exceeds the qubit limit of a single quantum call, and may enable practical quantum optimization advantages in the near term.

quant-pharXiv:2610.38344•Oct 29, 2026•0 citations
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)2/3+o(1)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=28n=28n=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, K3,mK_{3,m}K3,m​ with two added internal edges. For sufficiently large mmm, 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)(2m+2)/(3m)=2/3+o(1)(2m+2)/(3m)=2/3+o(1) of optimum; one root backtrack permits exact recovery in O(m)O(m)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=28n=28n=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.
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-kkk-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
Mathematical optimization is a field where the potential of quantum algorithms is actively being explored. The Quantum Approximate Optimization Algorithm (QAOA) serves as a notable quantum-classical hybrid approach aimed at solving combinatorial optimization challenges on Noisy Intermediate-Scale Quantum (NISQ) devices. In QAOA, classical variables find representation in qubits via a one-to-one mapping. A newer entrant, Quantum Random Access Optimization (QRAO), encodes problems using fewer qubits than QAOA by leveraging the Quantum Random Access Code (QRAC) to structure a problem into its Hamiltonian form. Notably, the QRAO Hamiltonian, dubbed the Quantum Relaxation Hamiltonian, boasts of a ground state energy inferior to that of the QAOA Hamiltonian. Nonetheless, the QRAO's ground state exhibits entanglement, making it starkly different from QAOA's ground state. As a workaround, preceding studies formulated solutions to the original problem using a rounding algorithm. Our research introduces the Quantum Relaxation based Branch-and-Bound (QR-BnB) algorithm. This novel method marries Quantum Relaxation and the classical exact solution strategy, Branch-and-Bound. Within the QR-BnB framework, a classical device shoulders the responsibility of the branch-and-bound operation, while its quantum counterpart dedicates itself to determining each ground state energy for the subproblem's Quantum Relaxation Hamiltonian. This fusion eliminates the prerequisite of the rounding algorithm by crafting the optimal solution through branching operations. Preliminary simulations of the QR-BnB approach attest to its capability in accurately solving a MaxCut problem. As future work, exploring its applicability on diverse combinatorial optimization problems holds promise. Our algorithm signals a step forward in harnessing NISQ devices for tackling expansive optimization challenges.
Abstract Quantum approximate optimization algorithm (QAOA) is a quantum–classical hybrid algorithm proposed with the goal of approximately solving combinatorial optimization problems such as the MAX-CUT problem. It has been considered a potential candidate for achieving quantum advantage in the noisy intermediate-scale quantum era and has been extensively studied. However, the performance limitations of low-level QAOA have also been demonstrated across various instances. In this work, we first analytically prove the performance limitations of the standard level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. To this end, we derive an upper bound for the approximation ratio based on the average degree of bipartite graphs. Second, we demonstrate that recursive QAOA (RQAOA), which recursively reduces graph size using QAOA as a subroutine, outperforms the standard level-1 QAOA. However, the performance of RQAOA exhibits limitations as the graph size increases. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations. Surprisingly, this modified RQAOA always finds the exact maximum cut for any bipartite graphs and even for a more general graph with parity-signed weights.
The Quantum Approximate Optimization Algorithm (QAOA) is a near-term quantum algorithm for solving combinatorial optimization problems, but its accuracy and resource requirements may scale poorly with problem size or structure, reducing its utility in practice. Approaches such as the Graph Decomposition for Optimization Algorithm (GDOA) seek to address this by iteratively reducing an input problem until it reaches a size where it can be solved using QAOA while maintaining the same optimal solution. This algorithm, however, requires solving integer programs that have exponentially many variables, and can result in suboptimal solutions, as the integer programs may contain slack terms. In this work, we propose a heuristic called the Quantum Enhanced Graph Decomposition (QEGD) algorithm. Its novelty lies in its use of QAOA as a subroutine for sparsifying a graph through local vertex-merging. The algorithm, when used to sparsify MaxCut problems that are then solved using QAOA, achieves higher approximation ratios across all tested graphs than GDOA for random 5-regular and 6-regular graphs. We then compare the time-to-solution and approximation ratio of QEGD to other QAOA variants a collection of Erdös-Rényi graphs. QEGD has higher approximation ratios on average than QAOA2^22 and ParaQAOA on all tested graphs. It also results in higher average approximation ratios than DC-QAOA on sparse Erdös-Rényi graphs and comparable average approximation ratio on denser Erdös-Rényi graphs. However, its average wall-clock time is between 0.4\% and 5\% of the average DC-QAOA wall-clock time.
The quantum approximate optimization algorithm (QAOA) is a paradigmatic variational quantum algorithm for combinatorial optimization problems, yet on current quantum devices the available qubit count and achievable circuit depth remain the main bottlenecks to its practical application. Divide-and-merge reduces the number of variables encoded in a single quantum circuit, while contraction based on coarse graining extends the effective range of shallow circuits, but existing work has not addressed both challenges simultaneously. We propose symmetry-preserving hierarchical QAOA (SP-HQAOA), in which parity sector contraction preserves the zero-field Ising structure of the effective objective at every contraction step, thereby addressing both within a single algorithm. We further prove that this reduction is the unique one with this property. Successive contractions further decouple the maximum leaf block size BBB from the qubit limit QQQ per quantum call, so every quantum circuit uses at most QQQ qubits even when B>QB>QB>Q. We also establish a deterministic repair-risk bound on the possible loss in optimal value caused by each sector restriction, and the resulting bounds can be summed across contraction steps and levels of the recursive hierarchy. With depth p=1p=1p=1, SP-HQAOA attains 99.4%99.4\%99.4% to 99.7%99.7\%99.7% of the exact optimum on N=40N=40N=40 random regular MaxCut leaf blocks and, with at most 101010 qubits per circuit, 96%96\%96% of the classical reference for N=500N=500N=500. SP-HQAOA demonstrates the capacity to use shallow quantum circuits to address combinatorial optimization problems whose variable count far exceeds the qubit limit of a single quantum call, and may enable practical quantum optimization advantages in the near term.