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.

Additionally, a circuit can be pretrained with the method .train_function . This allows preparing a new QuantumVariable with already optimized parameters, such that no new optimization is conducted. The results will therefore be the same.

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.
controlled_RX_mixer_gen(predicate)	Generate a controlled RX mixer for a given predicate function.

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	✅
E3Lin2	X mixer	✅
QUBO	X mixer	✅
MaxIndependentSet	Controlled X mixer	✅
MaxClique	Controlled X mixer	✅
MaxSetPacking	Controlled X mixer	✅
MinSetCover	Controlled X mixer	✅
Max-$\kappa$-Colorable Subgraph	XY mixer	✅