When I told my family my master's thesis was about "Hybrid LLM-GNN models for ADAPT-QAOA quantum circuit optimization", I got the look. 😶
You know the one.
“So… you fix quantum computers with ChatGPT?”
Not exactly. But close enough to deserve a proper explanation. 😅
So I'm turning my thesis into a 5-part series that anyone can follow — no physics degree, no linear algebra trauma required. In this first post, we start with the problem: what are we even trying to solve, and why would anyone bring a quantum computer to the fight?
Key Takeaways
- What combinatorial optimization is, using a classroom example.
- What the Max-Cut problem is, and why it gets brutally hard as it grows.
- Where quantum computers (and the QAOA algorithm) fit into the picture.
Table of Contents
- A Classroom Problem
- So What Is Max-Cut?
- Why It Gets Hard So Fast
- Enter the Quantum Computer
- The Series Roadmap
- Conclusion
A Classroom Problem
Imagine you're a teacher with 10 students, and you need to split them into 2 teams.
But there's drama. Some pairs of students really don't get along.
Your goal: split the class so that as many "enemy pairs" as possible end up on different teams.
Sounds easy, right? Just try a few splits and pick the best one.
With 10 students, there are about 1,000 ways to split them. Annoying, but doable.
With 50 students? About 1,000,000,000,000,000 ways. Good luck with that. ☕
This is a classic example of combinatorial optimization: picking the best option out of a ridiculously large (but finite) number of combinations.
So What Is Max-Cut?
Let's turn the classroom into a graph:
- Each student = a node (a dot)
- Each "enemy pair" = an edge (a line between two dots)
- If some pairs hate each other more, we give that edge a weight (a number like 0.8 instead of 0.2)
Now split the nodes into two groups. Every edge that connects the two groups is "cut".
Max-Cut = find the split that makes the total weight of cut edges as large as possible.
That's it. That's the whole problem.
It looks like a toy, but Max-Cut shows up in real life more than you'd think:
| Real-world problem | How it looks like Max-Cut |
|---|---|
| Logistics | Splitting deliveries/routes to reduce conflicts |
| Network design | Partitioning networks to balance traffic |
| Chip design | Placing circuit parts to minimize crossing wires |
| Physics | Finding the lowest-energy state of magnetic spins |
Max-Cut is also the "Hello World" of quantum optimization — almost every quantum optimization paper tests on it. That's why my thesis uses it too.
Why It Gets Hard So Fast
Here's the scary part.
For a graph with n nodes, the number of possible splits is roughly 2ⁿ.
| Nodes | Possible splits |
|---|---|
| 10 | ~1,000 |
| 20 | ~1,000,000 |
| 50 | ~1,000,000,000,000,000 |
| 100 | more than atoms you'd want to count |
Every extra node doubles the work. That's what we call exponential growth, and classical computers hate it.
Of course, smart people have built clever classical algorithms that find good enough answers. But as problems get bigger and messier, even those start sweating.
Think of it like finding the best seat arrangement for a wedding. 10 guests? Fine. 300 guests with family drama? You'll be crying in the venue bathroom.
Enter the Quantum Computer
A classical bit is either 0 or 1.
A quantum bit (qubit) can be in a mix of 0 and 1 at the same time — a superposition. With n qubits, a quantum computer can represent all 2ⁿ splits at once in one quantum state.
For Max-Cut, the mapping is beautiful:
- 1 node = 1 qubit
- qubit =
0→ node goes to Team A - qubit =
1→ node goes to Team B
Note: a quantum computer does NOT magically "try every answer and pick the best". When you measure it, you only get one answer. The trick is to shape the quantum state so that good answers come out with high probability.
That's exactly what QAOA (Quantum Approximate Optimization Algorithm) does. It's a hybrid algorithm:
- The quantum computer prepares a state using a circuit with some knobs (parameters).
- We measure it and check how good the cut is.
- A classical computer tweaks the knobs to do better.
- Repeat until it's good enough.
Quantum computer: “I think this split is good?”
Classical computer: “Meh. Turn knob #3 a bit left and try again.”
How good is "good enough"? We measure it with the Approximation Ratio (AR):
AR = (cut value we found) / (best possible cut value) -
AR = 1.0→ perfect answer -
AR = 0.9→ 90% as good as the best answer
Remember this number. It's going to be the star of the whole series.
The Series Roadmap
Here's where we're going:
- Max-Cut 101 (you are here)
- QAOA vs ADAPT-QAOA — building quantum circuits like LEGO, and the 2 big pains
- Turning a graph into a fingerprint — NetLSD, FEATHER & GNN
- A quantum circuit is just a sentence — training NanoGPT & LLaMA to write circuits
- The results — what worked, what didn't, and why the smaller model won
Conclusion
- Max-Cut = split a graph into 2 groups to cut as much edge weight as possible.
- It gets exponentially harder as the graph grows (2ⁿ possibilities).
- Quantum computers can represent all those possibilities at once, and QAOA is a hybrid way to steer them toward good answers.
- We judge answers with the Approximation Ratio — closer to 1 is better.
Future me: next time someone asks about my thesis, I'll just say "I help computers split a class into two teams."
🚀 Coming up next: In Part 2, we open the box and look at how a quantum circuit is built — and why the "smart" version, ADAPT-QAOA, is both brilliant and painfully slow.
Reference
All the code is live here on my GitHub:
mrzaizai2k/Adapt-LLM
Feel free to clone it, star it ⭐, or ask me anything.
👉 Hit follow + drop a comment if you want the next chapter.
And tell me: did the classroom example make sense, or did I lose you at "qubit"? 😄
Project Demo
Want the quick version of the whole project? Here's my demo video: