Hi all,
I’ve been learning a lot about quantum and I really love it. Especially everything we can do with it! I think it can help with the vehicle routing problem. And so many other real applications. Optimization is my favourite topic. And I read that QAOA can help but I don’t really understand it. Like how is it realized?
(post deleted by author)
(post deleted by author)
Hi @I_love_quantum ! 
Your question is excellent as you’re starting out in quantum computing and its applications in optimization! The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid classical-quantum algorithm and can indeed be used for the vehicle routing problem. Below, I will explain in a general and simplified way how it works:
QAOA is based on Farhi’s 2014 paper (here’s the link if you’d like to read it: https://arxiv.org/pdf/1411.4028). Its goal is to approximate the solution to combinatorial optimization problems, where the aim is to find the best configuration from a large set of possible solutions. This work was originally applied to the MaxCut problem, but it can be adapted to other problems by following this process:
You start with a combinatorial optimization problem, which is a function that can be expressed in terms of 0s and 1s. For example, in the vehicle routing problem, you need an objective function where each variable is binary, either represented as a graph or as a mathematical expression, such as:
x_0 \times x_1 \times x_2 + x_2 \times x_3 +x_0 \times x_1 \times x_3
ZZZI+IIZZ+ZZIZ
Next, variational or parametric quantum circuits are used to generate the cost Hamiltonian, which represents the optimization problem you are trying to solve, such as minimizing the total distance in a vehicle routing problem. The mixing Hamiltonian is also used, allowing the system to explore different configurations.
The algorithm alternates between applying these two Hamiltonians in a controlled way. Essentially, the circuit moves the system through potential solutions by adjusting parameters and phases in the quantum gates. The goal is to find the configuration with the lowest energy, which corresponds to the optimal or near-optimal solution.
PennyLane offers several tutorials on the Quantum Approximate Optimization Algorithm (QAOA), including an introduction, the physics and mathematics behind the algorithm, its application to the MaxCut problem, and a tutorial that can help you generate a solution for the vehicle routing problem.
I hope this brief explanation and these resources help you better understand how the QAOA algorithm works. If, after reading them, you still have questions, feel free to ask me!
Thanks for the answer @maldoalberto !
So how would you actually make the QAOA in a circuit? How would it look like?
This is an example of a QAOA quantum circuit, following a structure similar to the example I mentioned to you earlier. To help you understand it better, I will explain it step by step:
The section outlined in the green rectangle contains a series of Hadamard gates, which perform the basis change from Z to X, generating the states $|+\rangle$ and $|-\rangle$, which operate in the Z axis.
The section outlined in the blue rectangle represents the cost Hamiltonian, which models the objective function of the problem to be solved.
The section outlined in the red rectangle corresponds to the mixer function, which adjusts the circuit’s angles and searches for the minima.
The section outlined in the orange rectangle is the ZZ function, representing the interaction between two qubits or the connection as if it were a graph.
The section outlined in the pink rectangle is a QAOA layer; these layers repeat and are divided into fractions of $2\pi$.
Finally, the section outlined in the black rectangle contains the measurements, which are processed classically to obtain the states of highest probability of interest.
I hope this explanation is helpful. If you need further information, feel free to ask!
Thanks so much @maldoalberto !
Seeing the circuit with the rectangles really helps a lot. Thanks for the detailed explanation!