We now have the pieces needed to understand QAOA.
Your first hybrid quantum-classical algorithm.
Quantum Computing Series - Post #17
In the last few posts, we moved from optimization to binary optimization.
We saw that a solution can be represented as a bitstring.
For example: 10110
In the knapsack example, this means taking items 1, 3, and 4.
Now we can ask:
How does QAOA use this?
QAOA stands for:
Quantum Approximate Optimization Algorithm
It is called hybrid because it uses two parts:
- a quantum computer
- and a classical computer
Each one has a different role.
In general, the idea of QAOA goes like this:
Build a special “quantum machine” that produces candidate solutions.
Run it several times.
Score the solutions it gives us, using a classical computer.
Use those scores to find better parameters for the quantum machine.
Adjust the machine a little.
Then run it again.
Over time, the hope is that this machine becomes better at producing good solutions.
The process continues until we find a solution that is good enough.
The “quantum machine” is actually a quantum circuit with adjustable parameters.
These parameters control how the circuit behaves.
Inside the circuit, there are two important parts:
- The problem part
- The mixer part
The problem part is how the optimization problem is encoded into the quantum circuit.
The mixer part helps the circuit move between possible solutions.
Together, these two parts shape the quantum state before measurement.
We will go deeper into both of them in the next posts.
When we run the circuit once and measure, we get one bitstring.
For example: 10110
That is one candidate solution.
But because quantum measurement is probabilistic, we usually run the same circuit many times.
Each run gives one bitstring.
Together, these measurements give us a sample of candidate solutions.
Now the classical computer enters.
It scores the measured bitstrings using the cost function.
Then it updates the circuit parameters.
The quantum computer runs again with the new parameters.
This creates the QAOA loop:
• run the quantum circuit
• measure many times to get candidate solutions
• score the results classically
• update the parameters classically
• run again
The goal is that, after several rounds, better bitstrings appear more often when we measure.
The loop continues until we get a solution that is good enough for the problem, or until the improvement slows down.
That is why the word Approximate is in the name.
QAOA does not guarantee the perfect answer.
But for hard optimization problems, finding a very good solution can already be valuable.
Until next time: How do we create the quantum circuit for QAOA.
