Solving MAX 3-SAT With QAOA

Introduction

Quantum Approximation Optimization Algorithm (QAOA) is a promising new approach to solving complex optimization problems, leveraging the power of quantum computing to optimize and potentially even solve problems that are not feasibly solved by classical computing.

In our project, we applied QAOA to tackle the problem of MAX 3-SAT — an optimization problem that seeks to maximize the number of three-literal clauses in a Boolean formula that can be satisfied simultaneously.

A Rough Overview

QAOA is a variational algorithm that uses a unitary computed as the function of two parameters to prepare a quantum state, which encodes the optimal solution to the given problem in a binary string. To do so, a mix of both quantum and classical computing is used, with a classical algorithm being used to optimize parameters passed into the quantum simulation, which then, in turn, generates expectation values via the provided cost function.

A sketch of this process is as follows:

1. Initialize our parameters.
2. Given parameters, use the unitary to prepare the quantum state.
3. Measure the state in the standard basis.
4. Compute the expectation of the state.
5. Now, pass the expectation value to a classical optimization algorithm to find a new set of parameters, and repeat steps 2–4 until a suitable criterion is met.

This process is visualized in the diagram below, from Qiskit; and we will further break down each of the steps in the following sections.

Part I: Preparing the Quantum State

The first part of our algorithm is preparing the quantum state. To do so, we apply n Hadamard gates — one to each qubit — to represent an equal distribution between all possible states. Thus, we obtain the following state:

Then, we apply a unitary operator p times (for our implementation, we chose p = 10). This unitary operator is the product of two different unitary operators: the mixing unitary and the problem unitary. Thus, our final quantum state, given two vector parameters, beta and gamma, is computed as follows:

The mixing unitary, which takes beta as a parameter, is computed as follows:

Here, the matrix H is called the mixing Hamiltonian, and for the purpose of our implementation, we chose a mixing Hamiltonian such that the mixing unitary corresponds to an X rotation by beta.

Now, to construct the problem unitary, we first need a cost function to optimize: to that end, we seek to minimize the number of unsatisfied clauses (which would in turn, give the maximum number of satisfied clauses). A clause is unsatisfied if all literals evaluate to false. Thus, to encode a MAX 3-SAT problem into a cost function, we simply turn clauses into products, and the number of unsatisfied clauses is the sum of products. For example, we have the following conversion of a clause to a product:

The overall cost function is the sum of the individual products, and to generate the problem Hamiltonian, we take

Then, the problem unitary is simply

Note the similarity to the time evolution operator derived from the Schrodinger equation. We can think of gamma as a parameter that governs how much the system evolves using the Hamiltonian. Since lower energy states are preferable, the system will result in a high probability of states with a lower cost function, thus approximating solutions to the problem.

To physically implement this exponential, however, we need to express our Hamilotnian in terms of Pauli operators, which can be done via the following substitution:

For example, an individual clause would become:

For arbitrary indices i, j, k, this conveniently expands to

We can eliminate the 1, as it is a global phase shift, and the signs of each term are determined by whether each variable is negated or not. Since these Z operations all commute, it suffices to construct 3 RZ gates, 3 RZZ gates, and 1 RZZZ gate. Qiskit has built-in functions for RZ and RZZ gates; however, to construct an RZZZ gate, we use 4 CNOTs and an RZ gate, as follows:

Thus, an example circuit for the clause

would be

Part II: Computing the Expectation and Optimizing

To compute the expectation, we simply take a measurement in the Z basis, calculating the following:

In our implementation, since the circuit used to construct the quantum state is not too deep, it is possible to classically evaluate it. However, for deeper circuits, one must turn to methods such as sampling to approximate the expectation. Then, passing this expectation through an applicable classical optimization algorithm (in our case, we used Constrained Optimization By Linear Approximation (COBYLA)), we compute the next set of parameters gamma and beta to rotate our problem and admixer unitaries by suffices.

Results

Here, we document the results of our problem running on a MAX 3-SAT problem with 6 variables, and 30 clauses:

References

1. https://qiskit.org/textbook/ch-applications/qaoa.html
2. https://quantumcomputing.stackexchange.com/questions/28259/implementing-qaoa-hamiltonian-for-max-3-sat-in-qiskit
3. A Novel Approach for Solving Constrained Optimization Problems with QAOA using Encoders, Burak Mete