Project 7: QAOA for Max-Cut (Solving Hard Graphs)

Build a QAOA workflow that approximates Max-Cut solutions.

Project Overview

Attribute Value
Difficulty Level 3: Advanced
Time Estimate 2-3 weeks
Main Language Python
Alternative Languages Julia, Q#
Knowledge Area Combinatorial optimization
Tools Qiskit or Cirq
Main Book “Quantum Computation and Quantum Information” by Nielsen & Chuang

What you’ll build: A QAOA implementation that solves small Max-Cut graphs and compares results to classical solutions.

Why it teaches quantum: QAOA connects quantum circuits with classical optimization loops.

Core challenges you’ll face:

  • Encoding the cost Hamiltonian for Max-Cut
  • Building alternating mixer and cost layers
  • Optimizing parameters for best cut value

Real World Outcome

You will input a small graph and output a cut value and bitstring solution.

Example Output:

$ python qaoa.py --graph triangle
Best cut value: 2
Best bitstring: 010

Verification steps:

  • Compare to brute-force Max-Cut on small graphs
  • Track improvement over random guesses

The Core Question You’re Answering

“How can a quantum circuit guide a classical optimizer toward good solutions?”

QAOA is the hybrid approach to combinatorial problems.

Concepts You Must Understand First

Stop and research these before coding:

  1. Max-Cut formulation
    • How do you express Max-Cut as a Hamiltonian?
    • Book Reference: “Quantum Computation and Quantum Information” by Nielsen & Chuang, Ch. 6
  2. QAOA layers
    • What do cost and mixer layers do?
    • Book Reference: “Quantum Computing: An Applied Approach” by Jack Hidary, Ch. 9
  3. Parameter optimization
    • Why does QAOA require classical optimization?
    • Book Reference: “Algorithms for Optimization” by Mykel J. Kochenderfer, Ch. 5

Questions to Guide Your Design

  1. Graph encoding
    • How will you represent graphs in code?
    • How will you map edges to Pauli terms?
  2. Optimization loop
    • Which optimizer will you use?
    • How will you manage noisy objective values?

Thinking Exercise

Triangle Graph

For a triangle graph (3 nodes fully connected), what is the maximum cut value?

Questions while working:

  • How many cut partitions exist?
  • Why is the maximum cut 2?

The Interview Questions They’ll Ask

Prepare to answer these:

  1. “What is QAOA?”
  2. “How is Max-Cut encoded in a Hamiltonian?”
  3. “Why does QAOA use alternating layers?”
  4. “What limits QAOA performance on real hardware?”
  5. “How do you evaluate QAOA results?”

Hints in Layers

Hint 1: Starting Point Start with a 2-3 node graph.

Hint 2: Next Level Implement one layer (p=1) first.

Hint 3: Technical Details Use expectation value of the cost Hamiltonian as the objective.

Hint 4: Tools/Debugging Compare results to brute-force enumeration.

Books That Will Help

Topic Book Chapter
Max-Cut Nielsen & Chuang Ch. 6
QAOA “Quantum Computing: An Applied Approach” by Jack Hidary Ch. 9
Optimization “Algorithms for Optimization” by Mykel J. Kochenderfer Ch. 5

Implementation Hints

  • Keep graphs small for validation.
  • Separate circuit construction from optimization loop.
  • Track cut value distribution for insight.

Learning Milestones

  1. First milestone: You can encode Max-Cut as a Hamiltonian.
  2. Second milestone: You can run a p=1 QAOA circuit.
  3. Final milestone: You can compare QAOA output to brute-force results.