# Quantum Approximate Optimization Algorithm#

This modules facilitates the execution of The Quantum Approximate Optimization Algorithm (QAOA) and related techniques called the Quantum Alternating Operator Ansatz.

The end goal in QAOA is to optimize the variational parameters $$\gamma_p$$ and $$\beta_p$$ in order to minimize the expectation value of the cost function with respect to the final state $$\ket{\psi_p}$$. You can read more about the theoretical fundamentals behind QAOA in the tutorial Theoretical Overview. You can also find efficient implementations of this algorithm for MaxCut and Max-$\kappa$-Colorable Subgraph QAOA Implementation in an easy to read, insightful tutorials in which we describe the recipe to implement QAOA for other problem instances in a modular way, and independent of the encoding used.

The central data structure of the QAOA module is the QAOAProblem class.

## QAOAProblem#

The QAOAProblem class is like a blueprint for a implementing QAOA for a specific problem instance we’re trying to solve. When we create an instance of this class, we need to provide three things:

• Cost operator aka phase separator: a function that represents the problem we’re trying to solve, defining what makes a good or bad solution.

• Mixer operator: a function that drives transitions between different states. In the Quantum Alternating Operator Ansatz, mixers can be chosen from a broader set of unitaries, also specified below.

• Classical cost function: a function that takes a potential solution and calculates its cost.

Apart from the basic three ingredients mentioned above, some problems require the specification of the initial state. This can be achieved using the .set_init_function method.

The .run method prepares the initial state, applies $$p$$ layers of phase separators and mixers, and compiles a quantum circuit with intended measurements. Subsequently, the optimization algorithm is executed and the measurement results of the optimized circuit are returned.

For benchmarking, we provide the .benchmark method, which allows you to collect performance data about your implementation.

## QAOABenchmark#

As an approximation algorithm, benchmarking various aspects such as solution quality and execution cost is a central question for QAOA. The results of the benchmarks of QAOAProblem are represented in a class called QAOABenchmark. This enables convenient evaluation of several important metrics as well as visualization of the results.

## Collection of mixers and implemented problem instances#

Qrisp comes with a variety of predefined mixers to tackle various types of problem instances:

 RX_mixer(qv, beta) Applies an RX gate to each qubit in qv. RZ_mixer(qv, beta) This function applies an RZ gate with a negative phase shift to a given quantum variable. XY_mixer(qv, beta) Applies multiple XX+YY gates to qv such that each qubit has interacted with it's neighbour at least once. grover_mixer(qv, beta) Performs the parametrized Grover diffuser. constrained_mixer_gen(constraint_oracle, ...) Generates a customized mixer function that leaves arbitrary constraints intact.

The following problem instances have already been successfully implemented using the Qrisp framework:

PROBLEM INSTANCE

MIXER TYPE

IMPLEMENTED IN QRISP

MaxCut

X mixer

Max-$\ell$-SAT

X mixer

MaxIndependentSet

Controlled X mixer

MaxClique

Controlled X mixer

MaxSetPacking

Controlled X mixer

MinSetCover

Controlled X mixer

Max-$\kappa$-Colorable Subgraph

XY mixer