Quantum approximate optimization algorithm
Background
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid iterative method for solving combinatorial optimization problems. In this tutorial, we demonstrate how to implement the QAOA algorithm using Qiskit Runtime for solving a simple max-cut problem.
In a max-cut problem, we want to partition nodes of a graph in a way that maximizes the number of edges between nodes in differing groups. The desired max-cut partition for the following graph is clear: the 0th-node on the left should be separated from the rest of the nodes on the right by a cut. We will find this answer by applying QAOA by using Qiskit Runtime primitives and sessions.
Setup
Output:
Output:
Step 1: Map classical inputs to a quantum problem
To demonstrate max-cut, we'll create a graph using the rustworkx library, and create Pauli Hamiltonian that encodes the cost in a manner such that the minimum expectation value of the operator corresponds to the maximum number of edges between the nodes in two different groups.
Output:
For this simple example, the operator is a linear combination of terms with
Output:
The previous image illustrates the ansatz in basic gates for clarity. However, it can be expressed in multiple levels of decomposition by changing the
Output:
Step 2: Optimize problem for quantum execution.
We can schedule a series of qiskit.transpiler passes to optimize our circuit for a selected backend. This includes a few components:
optimization_level : The lowest optimization level does the bare minimum needed to get the circuit running on the device; it maps the circuit qubits to the device qubits and adds swap gates to allow all 2-qubit operations. The highest optimization level is much smarter and uses lots of tricks to reduce the overall gate count. Since multi-qubit gates have high error rates and qubits decohere over time, the shorter circuits should give better results.- Dynamical Decoupling: We can apply a sequence of gates to idling qubits. This cancels out some unwanted interactions with the environment.
Output:
Output: