Introduction to QAOA concepts
The standard method of finding the minimum of a binary quadratic model on a gate-based quantum computer is based on a method introduced by Edward Farhi, Jeffrey Goldstone, and Sam Gutmann in 2014. This method is called the Quantum Approximate Optimization Algorithm (QAOA). It is a hybrid algorithm since it requires its parameters to be classically tuned, as we will see later. We will proceed with the key steps in QAOA by discussing how to handle the linear terms, and then the quadratic terms of the BQM:
- First, let’s focus on how the linear coefficients can be mapped onto qubit rotations so that the variables with negative coefficients have a higher probability of getting a |1⟩ state. This makes use of rotating the qubit vector along the equator of the Bloch sphere using the RZ gate, and then rotating the qubit vector toward the measurement basis using the RX gate in such a way that the probability of the |1⟩ state increases...
