An Exclusive-Sum-of-Products Pipeline for QAOA

Matthew Brunet, Shilpi Shah, Mostafa Atallah, Anthony Wilkie, Rebekah Herrman · 2025

Read An Exclusive-Sum-of-Products Pipeline for QAOA by Matthew Brunet, Shilpi Shah, Mostafa Atallah, Anthony Wilkie, Rebekah Herrman (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-21686.txt.

Introduction

Matthew Brunet and co-authors improve a quantum algorithm for hard choice problems by rewriting its constraints, in work from 2025. The algorithm, QAOA, tackles problems such as picking the largest set of unlinked nodes in a graph. Rules that forbid some choices are usually added as penalties in the goal function, which can blur the search.

The team instead writes each constraint as a Boolean formula in a special form before adding penalties. They tested the method on graphs with three to twenty nodes. The rewritten form gave better approximation scores than the standard penalty route, with gains up to about thirty percent. It won after a single algorithm layer on about two thirds of the graphs. The work offers a practical step for near-term quantum hardware.

Catalog record

CREATORMatthew Brunet, Shilpi Shah, Mostafa Atallah, Anthony Wilkie, Rebekah Herrman
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE26 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-21686

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Exclusive-Sum-of-Products Pipeline for QAOA Matthew Brunet, Shilpi Shah, Mostafa Atallah, Anthony Wilkie, Rebekah Herrman Abstract The quantum approximate optimization algorithm is commonly used to solve combinatorial optimization problems. While unconstrained problems map naturally into the algorithm, incorporating constraints typically requires penalizing constraint violations in the objective function. In this work, we propose an alternative approach that encodes constraints as Boolean expressions in exclusive-sum-of-products (ESOP) form before penalization. We test this method on the maximum independent set problem using graphs with 3 to 20 vertices and find that ESOP constraint formulations achieve higher approximation ratios than standard constraint penalization methods, with percent increases of up to 30.3%. Furthermore, ESOP constraint formulations result in higher approximation ratios than standard QAOA penalization approaches after one layer of the algorithm on approximately 64% of the tested graphs. 1 Introduction The quantum approximate optimization algorithm (QAOA) [ 12 ] is a variational quantum algorithm that has the potential to provide a speed-up over classical algorithms for solving combinatorial optimization problems [ 26 , 39 , 42 ] . Recent QAOA research has resulted in numerous variations of the algorithm that seek to either decrease the circuit depth or problem size [ 32 , 48 ] , allow for more expressible circuits [ 17 , 44 , 46 , 43 ] , or reduce the space of feasible solutions [ 13 , 45 , 41 ] . While unconstrained combinatorial optimization problems such as MaxCut can easily be mapped into QAOA [ 28 ] , solving constrained combinatorial optimization problems, such as the Maximum Independent Set (MIS) problem, with the QAOA is more challenging. One of the main methods for handling constraints is to penalize them in the objective function, turning the problem into an unconstrained one that can be naturally mapped to QAOA [ 18 , 21 ] . These approaches can require ancillary qubits and can involve squaring sums of constraints, leading to products of several variables. This penalization can lead to complex cost Hamiltonians whose optimization landscape is difficult to navigate due to barren plateaus and local minima [ 19 , 20 , 3 ] . Another method of handling constraints is to encode the constraints directly into the initial state of the QAOA circuit, reducing the search space to only the feasible states [ 6 , 44 , 13 , 45 , 41 , 14 ] . The drawback to this method is the difficulty in creating an efficient (in circuit depth or number of two-qubit gates) state preparation circuit to encode the feasible states. For single constraints, such as linear equality constraints [ 7 , 44 ] , the state preparation can be efficient, however it is not clear if this is easy for general sets of constraints, specifically constraints that share large amounts of variables. Other approaches for constrained optimization for QAOA try to avoid penalization altogether [ 4 , 10 ] . The foundational work by Hadfield et al. [ 16 ] first established systematic methods for encoding Boolean constraints into phase oracles and Hamiltonians for quantum algorithms. Building on this foundation, recent approaches such as Boolean-Hamiltonian-Transformation QAOA (BHT-QAOA) [ 2 ] have extended these techniques to generate QAOA cost Hamiltonians by marking bit-strings that do not satisfy Boolean constraint expressions. In contrast to other penalization methods, BHT-QAOA formulates each constraint as an exclusive-sum-of-product (ESOP) Boolean expression. Interestingly, ESOP expressions have been used in quantum circuit compilation algorithms to reduce T gate count [ 25 , 38 ] and in quantum walk assisted QAOA (QW-QAOA) to solve constrained combinatorial optimization problems [ 23 ] , though the QW-QAOA approach updates the mixing Hamiltonian to search only over feasible solutions. In this work, we first introduce background on QAOA, MIS, and ESOPs in Sec. 2 . Then, we describe how to use ESOP expressions to encode constraints into QAOA, using MIS as a test problem, in Sec. 3 . In Sec. 4 , we compare the ESOP constraint approach to standard QAOA penalty approaches to solve MIS on over 3000 graphs with between 3 and 20 vertices and find that encoding constraints using the ESOP formulation results in up to a 30.3\% percent increase in approximation ratio over the standard QAOA constraint encoding approach. Finally, we conclude with a discussion in Sec. 5 . 2 Background In this section, we provide background information for QAOA, the MIS problem, SOPs, and ESOPs. 2.1 QAOA QAOA is a variational quantum algorithm in which two unitaries, a cost unitary U(C,\gamma)=e^{-iC\gamma} and a mixing unitary U(B,\beta)=e^{-iB\beta} , are applied to an initial state {\left|s\right\rangle} . The cost Hamiltonian, C , is a diagonal matrix that encodes the combinatorial optimization problem f(x) being solved. The construction of C for the MIS problem will be described in more detail later. The mixer Hamiltonian B allows for probability amplitude to be transferred between the computational basis states. In order for QAOA to converge to the optimal solution to the combinatorial optimization problem, the initial state {\left|s\right\rangle} should be an eigenstate of B . B is often chosen to be the transverse field mixer, B=\sum_{i}\sigma_{i}^{x} , and {\left|s\right\rangle}={\left|+\right\rangle}^{\otimes n} . The final state after p iterations of the algorithm is {\left|\gamma,\beta\right\rangle}=U(B,\beta_{p})U(C,\gamma_{p})\cdots U(B,\beta_{1})U(C,\gamma_{1}){\left|s\right\rangle}. The real-valued parameters \beta and \gamma , often called angles, are selected to minimize the expected value of the cost Hamiltonian C , \gamma^{*},\beta^{*}=\argmin_{\gamma,\beta}\langle C\rangle=\argmin_{\gamma,\beta}{\left\langle\gamma,\beta\right|}C{\left|\gamma,\beta\right\rangle}. Classical optimization routines such as BFGS [ 34 ] and COBYLA [ 33 ] are commonly used to find the angles. A common measure of success for QAOA is the approximation ratio (AR), which for constrained optimization, is defined as \frac{\langle C\rangle-C_{\mathrm{max}}}{C_{\mathrm{min}}-C_{\mathrm{max}}} where C_{\mathrm{max}} ( C_{\mathrm{min}} ) is the largest (smallest) eigenvalue of C . The AR is a real number between 0 and 1, with values closer to 1 indicating better solutions to the combinatorial optimization problem. 2.2 MIS The goal of the MIS problem on a simple graph G=(V,E) is to find the largest subset of vertices I\subset V such that for all i,j\in I , ij\notin E . For an example, see Fig. 1 . We can formulate the MIS problem as an integer program \displaystyle\max_{x\in\{0,1\}^{|V|}} \displaystyle\sum_{i\in V}x_{i} s.t. \displaystyle\;x_{i}+x_{j}\leq 1,\quad\forall(i,j)\in E. The MIS problem is commonly written as a quadratic unconstrained binary optimization (QUBO) problem of the form [ 47 , 31 , 11 , 8 ] \min\;\;\;-\sum_{i\in V}x_{i}+J\sum_{ij\in E}x_{i}x_{j}, which is mapped to H_{C} using the substitution x_{i}\rightarrow\frac{I-Z_{i}}{2} [ 15 ] . Note that this formulation recasts MIS as a minimization problem by negating the objective function. Throughout this work, we shall refer to this encoding as the “standard QAOA constraint encoding" method. x_{2} x_{4} x_{1} x_{3} Figure 1: Path on four vertices, P_{4} . This has three unique maximum independent sets: \{x_{1},x_{2}\} , \{x_{2},x_{3}\} , and \{x_{3},x_{4}\} . 2.3 SOPs and ESOPs Boolean expressions are commonly written in a SOP formulation [ 1 , 5 , 22 ] , in which products of Boolean variables (ANDs) are added together (ORs). Any Boolean expression can be converted to an equivalent ESOP, which is a Boolean expression consisting solely of exclusive sums of products of literals that can be negated. One can convert a Boolean expression to an ESOP expression using the identity \displaystyle a\vee b

Read the complete text