In this paper, we present a novel two-phase quantum algorithm designed to analyze a variant of the Maximum Constraint Satisfaction Problem (Max-CSP), denominated Partial Binary Max-CSP. The goal of Partial Binary Max-CSP is to maximize the number of feasibly assigned variables while ensuring conflict-free constraints. The proposed method uses the Quantum Approximate Optimization Algorithm (QAOA) in two distinct steps. In the ifrst step, QAOA is utilized to obtain an initial solution focused on satisfying as many constraints as possible. In cases where the problem is oversubscribed and conflicts remain, we use a second step: the unresolved conflicts are mapped into a Minimum Vertex Cover (MVC) problem, which is subsequently solved using a second QAOA. This two-phase approach ensures a conflict-free solution while minimizing the number of deactivated variables. We demonstrate the eficacy of our algorithm with an illustrative example involving the safe storage of dangerous materials, showing its potential application in real-world scenarios. This paper sets the foundation for further exploration of quantum algorithms in solving complex constraint satisfaction problems.
The Max-CSP (Maximum Constraint Satisfaction Problem) is a fundamental optimization problem in theoretical computer science and artificial intelligence, where the goal is to maximize the number of satisfied constraints in a given set of logical or algebraic constraints. Max-CSP is NP-hard, and therefore ifnding exact solutions in polynomial time is believed to be infeasible. In recent years, there has been growing interest in exploring quantum computing as a means to address such intractable problems, with the Quantum Approximate Optimization Algorithm (QAOA) emerging as a prominent method for combinatorial optimization on near-term quantum devices.
QAOA, introduced by [
QAOA is part of the broader family of hybrid quantum-classical algorithms, which aim to harness the computational power of quantum processors without requiring full-scale fault-tolerant quantum computing. The algorithm works by alternating between two unitary operations that correspond to the problem’s cost function and a mixing Hamiltonian, respectively. These operations are parameterized by classical variables, which are optimized to achieve the best possible approximation for a given problem.
QAOA’s success in solving combinatorial optimization problems lies in its flexible design, which can be adapted to various constraints and objective functions. While QAOA was originally proposed to tackle the Max-Cut problem on graphs, it has since been extended and generalized to a variety of combinatorial optimization problems, many of which can be formulated as special cases of Max-CSP. In the context of Max-CSP, each constraint can be viewed as a term in the objective function, and the algorithm seeks to find an assignment that maximizes the number of constraints satisfied. A number of works have studied the performance and application of QAOA to both Max-Cut and broader Max-CSP instances, revealing interesting insights into the algorithm’s capabilities and limitations.
In [5] the authors present an application of the Quantum Approximate Optimization Algorithm (QAOA) to a bounded occurrence constraint satisfaction problem, specifically Max E3LIN2. The authors demonstrate that QAOA achieves a performance that exceeds the classical counterparts. They highlight the algorithm’s eficiency in comparison to classical approaches like random sampling and describe its potential for more complex problem classes.
In [6] the performance of QAOA on CSPs with bounded-degree variables is explored, showing that QAOA can satisfy more constraints than random assignments in problems like Max-kXOR and MaxkSAT. The authors leave open the issue of whether classical algorithms may reach QAOA’s performance, under the same assumptions.
More recently, in [7] the authors apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. Their results show that QAOA achieves more eficient scaling than the highest-performance classical solver tested, suggesting that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts.
In this paper we describe a purely theoretical approach for the resolution of a variant of the binary Max-CSP problem, which we call Partial Binary Max-CSP, that difers from the Max-CSP in that we are interested in solutions where the number of feasibly assigned variables is maximized instead of solutions where the number of satisfied constraints is maximized. The proposed approach consists of basically 2 steps. In the first step, the QAOA algorithm is employed to find an initial graph coloring, with the goal of satisfying as many CSP constraints as possible. However, as the problem may be oversubscribed, the returned solution may still contain unresolved constraints.
In this case, we proceed with a second QAOA-based step to the solving process, where we basically build up a Minimum Vertex Cover instance from the solution returned by the previous Max-CSP step, and resolve the residual conflicts by identifying the nodes involved in the unsatisfied constraints and “deactivating” them. In this way, we obtain a conflict-free solution, efectively solving the Partial Binary Max-CSP.
The paper is organized as follows. Section 2 is dedicated to the description of the Partial Binary Maximal Constraint Satisfaction Problem that will be tackled in this work, while Section 3 describes the two-step algorithm devised for its resolution. Some illustrative examples are provided in Section 4 and ifnally, Section 5 presents the concluding remarks and some possible ideas for future work.
A Constraint Satisfaction Problem with Binary Constraints (Binary CSP) is a tuple = (, ), where = {1, . . . , } is a set of discrete variables with finite domains 1, . . . , , respectively, and = {1, . . . , } is a finite set of binary constraints. Each domain contains the possible values 1, . . . , for the variable . We denote by ¯ the set of all possible values ∪=1.
Each constraint involves the values of only two variables , and and is defined in terms of a set of simultaneous “forbidden” combinations of values for and . Namely, for all (ℎ, ) ∈ , the assignment = ℎ and = is unfeasible. Without any loss of generality, we can restrict to the case in which there exists only one constraint for each pair of variables and .
Let be the set of all the index pairs {, }, such that there exists a constraint between the variables and . Note that the graph = (, ) forms an undirected graph known as conflict graph . A feasible solution of is a complete assignment : → ¯ such that () ∈ , for all = 1, . . . , , and all the constraints are satisfied, i.e., ( (), ( )) ̸∈ for all {, } ∈ . A problem is satisfiable if it admits at least one feasible solution.
When is not satisfiable (i.e., oversubscribed), we are interested in finding a particular kind of partial solution, described as follows. Let us define as partial assignment a mapping ˜ : → ¯, where ⊂ , such that () ∈ for all ∈ . In other words, ˜ assigns a value only to the (proper) subset of all the available variables. A feasible solution of the Partial Binary CSP is a solution that corresponds to a partial assignment ˜, i.e., an assignment that only involves the variables ∈ , and that satisfies the constraints in . In other words, no constraint that involves the variables ∈ ∖ is considered to be violated.
An optimal solution * of the Partial Binary CSP is a feasible solution where the size of is maximized.
In this section we propose an algorithm to solve the Partial Binary Max-CSP described above. The algorithm is divided in two steps, both revolving around the Quantum Approximate Optimization Algorithm (QAOA). Hence, a brief presentation of the QAOA will be provided in the next section. 3.1. The Quantum Approximate Optimization Algorithm The Quantum Approximate Optimization Algorithm is a variational quantum algorithm designed to tackle combinatorial optimization problems. From the mathematical viewpoint, the algorithm alternates between two types of quantum operators: (i) the Problem Hamiltonian ( ) and the Mixer Hamiltonian ( ) both characterized by parameters that are optimized by means of a classical optimizer. Since the QAOA operates by alternating quantum and classical techniques during the optimization process, it is classified as a hybrid algorithm.
The QAOA’s quantum segment typically starts with an equal superposition of all possible solutions for an n-qubit system: | 0⟩ = ⊗ |0⟩⊗ |⟩ = () |⟩
= ∑︁ =1 (1) (2) (3) (4) (5)
The goal is to find the values of the parameters ⃗ and ⃗ that optimize this expectation value using classical optimization algorithms (e.g., COBYLA).
The Problem Hamiltonian ( ) encodes the objective function () to be optimized. The Problem Hamiltonian is diagonal in the computational basis, with eigenvalues corresponding to the function’s values:
Lastly, the Mixer Hamiltonian ( ) encourages the exploration of the solution space by mixing the states. The most simple example is the transverse-field Hamiltonian, which applies Pauli-X operators to lfip qubit states:
The QAOA algorithm alternates between applying the Problem Hamiltonian and the mixer Hamiltonian to the initial state | 0⟩, according to the following formula: ⃒ ⃒⃒ ⃗(, ⃗ )⟩ = ( ) ( ) · · · ( 1) ( 1) | 0⟩ where is the number of alternating applications (phases) of both Hamiltonians, and⃗ = ( 1, 2, . . . , ) and ⃗ = ( 1, 2, . . . , ) are the parameters to be optimized.
The expectation value of the Problem Hamiltonian is computed on the final state:
⟨ ⟩ = ⟨ ⃗(, ⃗ )⃒⃒⃒ ⃒⃒⃒ ⃗(, ⃗ )⟩ 3.2. First step: solving the Max-CSP In the first step, the algorithm solves the Max-CSP applied to to obtain a complete assignment which maximizes the number of satisfied constraints. A possible algorithmic solution for this problem entails its formulation as a Quadratic Binary Optimization (QUBO) problem, which allows to solve it by means of a QAOA approach.
The formulation of the Max-CSP [8] uses the set ℬ = { : = 1, . . . , , = 1, . . . , } of = ∑︀
=1 binary variables. The values of these variables correspond to a complete assignment by a employing a one-hot encoding, i.e., by setting, for all = 1, . . . , , = 1, . . . , , = 1 if () = , otherwise = 0.
Since each variable has a unique value in each complete assignment, the constraint is imposed on the set ℬ.
The objective function ∑︁ = 1 for each = 1, . . . , =1 = ∑︁
∑︁ counts the number of violated constraints, therefore by minimizing under the constraint (6) it is possible to solve the Max-CSP problem.
With this formulation it is possible to use the Quantum Alternating Operator Ansatz algorithm to solve Max-CSP. This algorithm is more general than the more frequently used Quantum Approximate Optimization Algorithm because the former can solve constrained problems which are defined in terms of non-binary variables, as it is in the case. If the problem is not oversubscribed, this step alone is suficient to find an optimal solution, as all constrains can be satisfied within in the current step.
The implementation of QAOA to the Max-CSP problem uses qubits, divided in Q-registers 1, . . . , of 1, . . . , qubits, respectively. We denote by the -th qubit of the register : the qubits correspond to the binary variables and the Q-register corresponds to the value of the variable . In order to work only with legal complete assignments, the state of each Q-register must be a superposition of bitstrings with Hamming weight equal to one.
The quantum segment of QAOA employs a parametrized circuit, which is composed by three diferent kind of blocks, as shown in Figure 1 (Quantum computing module).
The first block creates the initial state. Each Q-register is initialized in the state 1 √ (|100 . . . 0⟩ + |010 . . . 0⟩ + |001 . . . 0⟩ + · · · + |000 . . . 1⟩) composed by all bitstrings with Hamming weight equal to one and length . This can be obtained using the gate , described in [9], applied to each Q-register .
After the initial block, the circuit is composed by layers. In each layer, two blocks are present, the Phase Shifting block and the Mixing block.
The Phase Shifting block is related to the Hamiltonian function of the Max-CSP problem. It is possible to obtain by replacing in the objective function (7) each binary variable with the operator 12 (1 − ), where is the gate applied to . With some algebra we obtain that = + where is the number of occurrence of the value in the constraints, and is a numerical constant, which is irrelevant for our purpose.
Then, the Phase Shifting block is just (8) (9) (10) = exp(− ) where is a real parameter, which is fixed for all the gates of the layer .
The computation produces = ∏︁
∏︁ ℎ ( ) ( ).
( ) = ∏︁ , ( )
=1 where the unitary transformation
, ( ) = ,last( ),even( ),odd( ) is applied to each Q-register .
Here, we adopt the strategy “Parity single-qudit ring mixer” as described in [10], to overcome the problem of non commutativity.
The transformation ,even( ) is defined as ,even( ) =
∏︁ even
exp(− (,,+1 + ,,+1)) The transformation ,odd( ) is analogous, while
,last( ) = exp(︀ − (,,1 + ,,1)︀) , when is odd, while it is the identity transformation when is even. 3.3. Second step: solving Minimum Vertex Cover Once the QAOA algorithm is finished, the solution x with the lowest cost function defined in formula (7) hopefully corresponds to the CSP assignment which satisfies the maximum number of constraints.
In particular, if the value of (x) is 0, then all the constraints are satisfied and the solution ⋆ corresponds to a feasible solution of the CSP .
On the other hand, when (x) > 0, it is impossible to satisfy all the constraints, therefore the second stage of the algorithm starts with the purpose of finding ⋆, the partial assignment which satisfies all the constraints and minimizes the number of unassigned variables.
This problem can be formulated in terms of the well-known Minimum Vertex Cover (MVC) problem. In fact, given the best solution x found in the first stage, it is possible to extract a subgraph ′ = (, ′) from the conflict graph = (, ). The edge set ′ corresponds to all the constraints which are not satisfied by the solution ⋆, while the vertex set are the vertices which are connected by the edges in ′. In other words, is composed by all the variables involved in the constraints not satisfied by x.
The purpose of MVC problem is to find the set ⊂ with the minimal cardinality which covers ′, in the sense that for each edge {, } ∈ ′, either ∈ or ∈ .
It is easy to see that by taking the assignment , corresponding to the solution x, and removing the value assigned by to the variables ∈ , it is possible to obtain the partial assignment ⋆. In fact, in each constraint associated to the edges in ′, at least one variable has no value and hence the constraint is (vacuously) satisfied.
The MVC problem can be solved either with a conventional computer, if the number of variables in is small, or with a quantum computer. In the latter case, we propose to employ again the QAOA approach.
The MVC problem is formulated in terms of binary variables 1, . . . , , where = 1 means that the corresponding node will be selected (and hence the corresponding variable of the CSP problem is undefined), = 0 otherwise.
The objective function, to be minimized, is
( ) = ∏︁ ( )
=1 Hence, it is composed by a rotation gate (with rotation angle ) applied to all the qubits.
∑︁ + =1
∑︁ {,ℎ}∈′ (1 − )(1 − ℎ) which is the sum of a first term, which accounts the number of selected vertices of ′, and a second term, which is a penalization term which forces to choose a covering of ′. is a penalty coeficient which regulates the relative importance of the penalization term with respect to the cardinality term.
The structure of the circuit is simpler than the one for Max-CSP problem, because the solutions have a binary representation, where all the bitstrings correspond to feasible solutions.
The initial block is composed by a Hadamard gate applied to each qubit. In this way the initial state is a superposition of all 2 possible bitstrings.
The Hamiltonian of MVC problem is
=1 = ∑︁( 4 − 21 ) + 4
∑︁ {,ℎ}∈′ ℎ where is the degree of the -th vertex in the graph ′.
Hence the Phase Shift block is composed by the gates applied to , ℎ with angle 4 , for each edge {, ℎ} of ′, and by the gates applied to each vertex with angle ( 4 − 2 1 ) .
Finally, the Mixing block consists in the unitary transformation (11) (12) (13)
An illustrative example of the previously described problem is the safe storage of dangerous materials [11].
Consider a facility where various types of dangerous substances need to be stored. Each substance has specific storage requirements and incompatibilities with other substances. Additionally, some materials can exhibit dangerous self-incompatibilities if not stored under precise conditions. These materials are placed in storage units at various distances from each other, and it is critical to ensure that incompatible substances are not stored in adjacent units to prevent dangerous interactions that could lead to accidents such as fires or explosions.
Let us consider a scenario with storage units, 1, 2, 3, . . . , . The goal is to place a substance in each storage unit such that (self-)incompatible substances are not stored in nearby units, ensuring both safety and compliance with regulations on dangerous materials.
Each substance belongs to one of the following four storage categories:
Storage Categories
• Flammable materials are incompatible with: Flammable materials, Oxidizers, Strong Bases • Oxidizers are incompatible with: Oxidizers, Flammable materials, Strong Acids • Strong Acids are incompatible with: Strong Acids, Oxidizers, Strong Bases • Strong Bases are incompatible with: Strong Bases, Strong Acids, Flammable materials These incompatibility rules define which types of substances cannot be stored in adjacent units. Let us now suppose we have = 16 storage units, organized in an undirected graph. The nodes of the graph, labeled from 1 to 16, represent the storage units. Edges between nodes represents vicinity constraints, and indicate that the corresponding storage units are suficiently close that safety measures must be considered to prevent dangerous interactions, and their satisfaction ensures that incompatible substances are not stored in neighboring units.
Let each specific type of dangerous substance be represented by a diferent color: Flammable as Red, Oxidizer as Blue, Strong Acid as Green, and Strong Base as Yellow.
The goal can be reformulated as a particular kind of graph coloring problem, i.e., to assign colors to all the nodes such that no connected nodes are colored with incompatible colors.
The conflict rules for the materials can be rewritten as incompatibility relations among the colors, as follows: • The red color is in conflict with red, blue, and yellow. • The blue color is in conflict with blue, red, and green. • The green color is in conflict with green, blue, and yellow.
• The yellow color is in conflict with yellow, green, and red. 4.1. Graph Representation
As described in Section 3.2, we apply the first step of our resolution process for the dangerous materials storage problem by using the QAOA, aiming to find an optimal or near-optimal solution to the Max-CSP problem. However, as it can be seen from Figure 3, the algorithm cannot return a feasible solution where all the constraints are satisfied. In fact, it is important to notice that a feasible solution does not exist, as the problem instance is oversubscribed. In the example solution depicted in the figure, the red edges highlight conflicts between materials stored in neighboring units where incompatible substances are assigned, violating safety constraints. The generated solution considers the blue nodes as Oxidizers and the yellow nodes as Strong Bases.
To find a solution that meets the safety constraints, all conflicts must be resolved by identifying and “deactivating” a subset of nodes associated to storage units that contain incompatible substances. Our interest is to minimize the size of this subset.
This result is obtained by selecting a specific group of units that will not be used for storage, thus avoiding conflicts between the related neighboring locations, and ensuring complete compliance with all safety regulations.
This problem can be formulated as a Minimum Vertex Cover (MVC), in which the goal is to find the sub-graph with the smallest set of nodes that includes at least one endpoint of every edge of the graph. It is clear that if the nodes in this set are eliminated, all conflicts are resolved.
Figure 4 illustrates the solution obtained with the MVC approach, where the white nodes represent the storage units that have been eliminated, i.e., they no longer contain dangerous substances, thus resolving the previously existing conflicts.
Figure 5 illustrates a final solution to the problem of safe storage of dangerous materials.
In this context, each colored node represents a storage unit with an assigned substance, while white nodes indicate units which were involved in conflicts, which now are empty.
The reader should note that the solution thus found entails the presence of 12 “surviving” variables on the initial 16, that is 75% of the original variables. Reasonably, it should be noted that this result has been obtained by eliminating the variables (6, 7, 10 and 11) that participate to the highest number of constraints.
In this paper, we propose a novel approach to solving a Max-CSP (Maximum Constraint Satisfaction Problem) in a partial way.
Our approach is composed of two diferent steps, both leveraging the hybrid algorithm known as the Quantum Approximate Optimization Algorithm (QAOA) to find an optimal solution.
In the first step, the QAOA is applied to generate a preliminary solution to the problem represented as a Max-CSP, i.e., an assignment of the CSP variables that minimizes the number of unsatisfied constraints. If the problem is not oversubscribed, the application of the QAOA may return an optimal solution where all constraints are satisfied. However, in oversubscribed scenarios, the returned solution will likely contain unresolved conflicts (see Figure 3).
To address these conflicts, we introduce a second step, where the solution from the previous step is used to formulate a Minimum Vertex Cover (MVC) problem. The resulting MVC problem is then solved through a second application of the QAOA. In this step, the algorithm identifies specific nodes (i.e., the variables) in the conflict graph that contribute to the unresolved conflicts. By “deactivating” these nodes and considering only the surviving variables, we can achieve a conflict-free and optimal solution that minimizes the number of deactivated variables.
This paper provides a theoretical analysis of the approach, but further research is necessary to explore its full potential. A critical next step is to conduct a comprehensive set of experiments to rigorously test the performance of our approach across various scenarios and problem sizes. These experiments would help to (i) validate our hypotheses, (ii) quantify the efectiveness of the hybrid QAOA-based approach, and (iii) provide insights into its scalability and real-world applicability.
Another possible direction for future research is to explore whether it is possible to merge the two steps into a single application of the QAOA. Analyzing the feasibility of such an approach, along with its potential trade-ofs in terms of computational complexity and accuracy, could ofer valuable insights for the further development of quantum algorithms in solving Max-CSP problems. In conclusion, the two-step approach presented in this paper may ofer an interesting idea for solving complex constraint satisfaction problems. [5] E. Farhi, J. Goldstone, S. Gutmann, A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, arXiv: Quantum Physics (2014). URL: https://api. semanticscholar.org/CorpusID:119071769. [6] C. Y. Lin, Y. Zhu, Performance of QAOA on typical instances of constraint satisfaction problems with bounded degree, CoRR abs/1601.01744 (2016). URL: http://arxiv.org/abs/1601.01744. arXiv:1601.01744. [7] S. Boulebnane, A. Montanaro, Solving boolean satisfiability problems with the quantum approximate optimization algorithm, PRX Quantum 5 (2024) 030348. URL: https://link.aps.org/doi/10. 1103/PRXQuantum.5.030348. doi:10.1103/PRXQuantum.5.030348. [8] R. Dechter, Constraint Processing, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003. [9] F. G. Fuchs, H. Ø. Kolden, N. H. Aase, G. Sartor, Eficient encoding of the weighted max -cut on a quantum computer using qaoa, SN Computer Science 2 (2021) 89. URL: https://doi.org/10.1007/ s42979-020-00437-z. doi:10.1007/s42979-020-00437-z. [10] S. Hadfield, Z. Wang, B. O’Gorman, E. Riefel, D. Venturelli, R. Biswas, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Algorithms 12 (2019) 34. URL: http://dx.doi.org/10.3390/a12020034. doi:10.3390/a12020034. [11] F. Rahmawati, Design of an integrated temporary storage for hazardous and toxic material wastes 4.0 case study in the department of industrial chemical engineering, IPTEK The Journal of Engineering (2024). URL: https://api.semanticscholar.org/CorpusID:269510805.