Academy K

QAOA for Max-Cut

HardDerivationQAOAoptimizationcombinatorial

Related module: Variational and hybrid methods

Problem statement

The Quantum Approximate Optimization Algorithm (QAOA) encodes the Max-Cut problem for a graph G=(V,E)G=(V,E) with cost function:

C=∑(i,j)∈E1−ZiZj2C = \sum_{(i,j)\in E} \frac{1-Z_iZ_j}{2}

where ZiZj=+1Z_i Z_j = +1 if vertices i,ji,j are in the same partition, −1-1 if different.

  1. What is the QAOA circuit structure for depth pp?
  2. For a triangle graph, what is the maximum cut and what state achieves it?
  3. Why does QAOA performance improve with depth pp?

Hints

Practise this problem

Verify you understand it—not just that you read the answer.

Learn the foundations

The Quantum Computing track covers this topic and more in depth.