Building QAOA Circuits for MaxCut

Hello! Welcome back to our deep dive into quantum computing.

In our last lesson, we explored Hamiltonian simulation, focusing on how to approximate the time evolution operator $e^{-iHt}$ using Trotter-Suzuki decomposition. We saw that this method breaks down a complex evolution into a sequence of simpler, implementable gate operations.

Today, we will see how this concept of simulating evolution is ingeniously repurposed for a completely different task: solving combinatorial optimization problems. This lesson addresses the learning outcome: Construct the QAOA ansatz circuit for a given problem Hamiltonian, such as for MaxCut.

We will learn how to:

1. Map a classical optimization problem, MaxCut, onto a quantum mechanical Hamiltonian.
2. Define the two key components of the QAOA ansatz: the problem Hamiltonian and the mixer Hamiltonian.
3. Construct the full, parameterized QAOA quantum circuit by alternating the evolution under these two Hamiltonians.

This lesson serves as a crucial bridge, connecting the simulation techniques we just learned with the broader family of variational algorithms we began exploring with VQE.

1. From Classical Optimization to a Quantum Hamiltonian

The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm designed to find approximate solutions to combinatorial optimization problems. To use it, we must first rephrase our classical problem in the language of quantum mechanics. We'll use the MaxCut problem as our primary example.

MaxCut is a famous NP-hard problem defined on a graph. The goal is to partition the graph's vertices into two sets, say $S_0$ and $S_1$, such that the number of edges connecting vertices in different sets is maximized.

To solve this with a quantum algorithm, we need to encode the problem into a Hamiltonian whose ground state corresponds to the optimal solution (the maximum cut). This mapping involves a few steps:

1. Assign variables: We assign a binary variable to each vertex $i$, say $x_i\in \{0,1\}$, representing which of the two sets the vertex belongs to.
2. Formulate a cost function: We create a function that counts the number of "cut" edges. For an edge $(i,j)$, the term $x_i+x_j-2x_i{x}_j$ is 1 if $x_i\ne x_j$ and 0 otherwise. Summing this over all edges gives the total cut value.
3. Convert to a minimization problem: Quantum algorithms naturally find minimum energy states (ground states). So, we flip the sign of our cost function to turn the maximization problem into a minimization one.
4. Map to an Ising Hamiltonian: The final step is to map the binary variables $x_i\in \{0,1\}$ to spin variables $z_i\in \{+1,-1\}$ using the transformation $x_i\to (1-z_i)/2$. This converts the cost function into an Ising Hamiltonian, an operator whose terms are composed of Pauli $Z$ operators and identity operators.

The ground state of this resulting Hamiltonian, which we call the problem Hamiltonian $H_C$, is the quantum state that encodes the bitstring corresponding to the maximum cut.

For a graph $G=(V,E)$ with unweighted edges, the resulting problem Hamiltonian is remarkably simple:

Finding the ground state of this $H_C$ is equivalent to solving the MaxCut problem.

2. The Structure of the QAOA Ansatz

The QAOA ansatz is a parameterized quantum circuit inspired by adiabatic quantum computing. Instead of a slow, continuous evolution, QAOA uses a discrete, layered approach.

The state is prepared by applying a sequence of operators to an initial state. The general form of the QAOA state for $p$ layers is:

Let's break this down:

• Initial State $|+{⟩}^{\otimes n}$: The circuit starts by applying a Hadamard gate to each qubit, preparing an equal superposition of all possible computational basis states. This ensures we start with an unbiased exploration of the entire search space.
• Problem Hamiltonian $H_C$: This is the Hamiltonian we just derived from the MaxCut problem. The unitary $e^{-i{\gamma }_l{H}_C}$ is an evolution under this Hamiltonian for a "time" ${\gamma }_l$. This operator's role is to impart a phase to each basis state according to its corresponding cut value, effectively "rewarding" states that represent good solutions.
• Mixer Hamiltonian $H_M$: This is a second Hamiltonian, standard for most QAOA applications, defined as the sum of Pauli-X operators: $H_M={\sum }_{i=1}^n{X}_i$. The unitary $e^{-i{\beta }_l{H}_M}$ evolves the system under this mixer. Its role is to induce transitions between different computational basis states, allowing the algorithm to "mix" and explore different potential solutions. The initial state $|+{⟩}^{\otimes n}$ is the ground state of this mixer.
• Parameters $\vec{\gamma },\vec{\beta }$: The angles $({\gamma }_1,...,{\gamma }_p)$ and $({\beta }_1,...,{\beta }_p)$ are the variational parameters that are optimized by a classical computer to find the best possible approximation to the ground state of $H_C$.

The structure is a repeated, alternating application of the problem and mixer evolution operators.

3. Constructing the Circuit from the Hamiltonians

Now we arrive at the core task: translating the abstract operators $e^{-i\gamma H_C}$ and $e^{-i\beta H_M}$ into a sequence of quantum gates. This is where our knowledge from the previous lesson on Hamiltonian simulation becomes directly applicable.

{
    "intro": "For a more formal treatment, which aligns with your background, the Qiskit lecture 'Introduction to the Quantum Approximate Optimization Algorithm and Applications' explains precisely how these Hamiltonian evolutions are compiled into gates.",
    "resource_title": "Lecture 5.2 - Introduction to the Quantum Approximate Optimization Algorithm and Applications",
    "resource_id": "6b43e",
    "relevant_parts": [
        2,
        3
    ],
    "instructions": "Please watch from 18:37 to 24:14. This segment first gives a high-level overview of the QAOA variational form, then dives into the details of matrix exponentiation, explaining how the cost Hamiltonian (a sum of Z and ZZ terms) becomes a layer of RZ and controlled-RZ gates, and how the mixer Hamiltonian (a sum of X terms) becomes a layer of RX gates.",
    "estimated_time": "6 minutes"
}

Let's summarize the construction for a single QAOA layer ($p=1$):

A. The Problem (Cost) Layer: $e^{-i\gamma H_C}$

The MaxCut problem Hamiltonian is $H_C=\frac{1}{2}{\sum }_{(i,j)\in E}(I-Z_i{Z}_j)$.
The evolution operator is $e^{-i\gamma H_C}=e^{-i\gamma \frac{1}{2}\sum (I-Z_i{Z}_j)}$.

• The identity terms $I$ contribute only a global phase, which doesn't affect measurement outcomes, so we can focus on the $Z_i{Z}_j$ terms.
• Crucially, all $Z_i{Z}_j$ terms for different edges commute with each other. For example, $[Z_1{Z}_2,Z_3{Z}_4]=0$. This means we don't need a Trotter approximation here; the exponential of the sum is exactly the product of the exponentials: $$e^{i\frac{\gamma }{2}{\sum }_{(i,j)\in E}{Z}_i{Z}_j}=\prod _{(i,j)\in E}{e}^{i\frac{\gamma }{2}{Z}_i{Z}_j}$$
• Each term $e^{i\theta Z_i{Z}_j}$ (with $\theta =\gamma /2$) is a two-qubit gate that we learned how to build in the last lesson. It can be decomposed as: $$e^{i\theta Z_i{Z}_j}={\text{CNOT}}_{i,j}(I\otimes R_Z(-2\theta )){\text{CNOT}}_{i,j}$$

So, the problem layer consists of applying this CNOT-RZ-CNOT sequence for every edge in the graph.

B. The Mixer Layer: $e^{-i\beta H_M}$

The mixer Hamiltonian is $H_M={\sum }_i{X}_i$.

• Similar to the problem layer, all individual $X_i$ terms commute with each other ($[X_i,X_j]=0$). Therefore, the evolution operator decomposes exactly: $$e^{-i\beta H_M}=e^{-i\beta {\sum }_i{X}_i}=\prod _i{e}^{-i\beta X_i}$$
• Each term $e^{-i\beta X_i}$ is simply a rotation around the X-axis, which is implemented by the $R_X(2\beta )$ gate.

So, the mixer layer consists of applying an $R_X(2\beta )$ gate to every qubit in the circuit.

C. The Full p=1 Ansatz Circuit

Combining these pieces, the QAOA ansatz circuit for one layer ($p=1$) for a given graph is constructed as follows:

1. Initialization: Apply a Hadamard gate to every qubit.
2. Problem Layer: For each edge $(i,j)$ in the graph, apply the sequence ${\text{CNOT}}_{i,j}\to R_Z(-\gamma )\to {\text{CNOT}}_{i,j}$.
3. Mixer Layer: Apply an $R_X(2\beta )$ gate to every qubit.

For a deeper ansatz with $p>1$, you simply repeat steps 2 and 3 $p$ times, using new parameters ${\gamma }_l$ and ${\beta }_l$ for each layer.

Conclusion

In this lesson, we have detailed the construction of the QAOA ansatz, a cornerstone of modern variational quantum algorithms. We have seen how a classical optimization problem like MaxCut can be systematically translated into a quantum circuit.

Key Takeaways:

• Combinatorial optimization problems can be mapped to Ising Hamiltonians ($H_C$), where the ground state of the Hamiltonian encodes the optimal solution. For MaxCut, $H_C$ is a sum of $Z_i{Z}_j$ terms for each edge.
• The QAOA ansatz creates a trial state by starting in a uniform superposition and then repeatedly applying two alternating evolution operators:
  • Problem Evolution ($e^{-i\gamma H_C}$): Phases the states based on the problem's cost function.
  • Mixer Evolution ($e^{-i\beta H_M}$): Mixes the states to explore the solution space.
• The construction of these evolution operators into gates is a direct application of the principles of Hamiltonian simulation. Since the terms within $H_C$ and $H_M$ commute among themselves, no Trotter approximation is needed for each layer.
• The problem layer for MaxCut is built from CNOT and RZ gates, while the mixer layer is built from RX gates.

Preview of the Next Lesson

We have now successfully constructed the parameterized quantum circuit, or ansatz. However, the parameters $\vec{\gamma }$ and $\vec{\beta }$ are still undefined. In our next lesson, Implement the full QAOA workflow, including the classical optimization loop, to solve a small instance of the MaxCut problem, we will address this. We will see how the quantum circuit is embedded within a classical optimization loop that iteratively adjusts these parameters to minimize the expectation value $⟨H_C⟩$, thereby guiding the algorithm toward the optimal solution.