Quantum Approximate Optimization Algorithm - RPIQuantumComputing/QuantumCircuits GitHub Wiki

Quantum Approximate Optimization Algorithm (QAOA) is an algorithm which allows one to solve combinatorial optimization problem. The goal of an optimization problem can be expressed as trying to find an $x$ obeying certain constraints such that $x$ achieves a maximum or minimum value for a given function.

Now, which starting state to use? Well, we assuming we are just starting our search-we really should not bias ourselves to one choice over another.

$$\ket{\psi_{0}} = \frac{1}{\sqrt{2^{N}}}\sum_{x \in {0, 1}^{N}} \ket{x}$$

We can think of our search in the following: we find ourselves independently exploring every possibility. From each state, when we start, it really only makes sense to try one thing: apply our objective function. Now, like in Grover's, we can assume our objective function can be expressed as a Hamiltonian. From this, we need to create a unitary for our quantum computer. Before we did so by defining a new function, carrying the original input, and applying the function's action through introduce a phase flip caused by the result on an ancillary qubit. But, once could take the mathematicians approach to making a unitary from a Hamiltonian (which is really just a Hermitian matrix we call the Hamiltonian due to it being a physical operation representing the amount of action within the system, see the VQE wiki page to understand what action is):

$$U_{P}(\gamma) = e^{-i\gamma H_{P}}$$

Now, the challenge becomes trying to understand what the heck this thing is. Noting that the $H_{p}$ is a matrix and taking the Taylor definition of a matrix exponentiation, we find the following:

$$e^{-i\gamma H_{P}} = I\cos{\gamma} - iH_{p}\sin{\gamma}$$

Applying to the basis, we find that $H_{p}$, by its definition, gives us our objective values for our $\ket{x}$, so we can apply the operation to our superposition.

$$e^{-i\gamma H_{P}} = \sum_{x \in {0, 1}^{N}} (I\cos{\gamma} - iH_{p}\sin{\gamma})\ket{x} = \sum_{x \in {0, 1}^{N}} \cos{\gamma} \ket{x} - i\sum_{x \in {0, 1}^{N}} e^{i p(\ket{x})} \sin{\gamma} \ket{x}$$

Now, you might be wondering: How the hell did you know the eigenvalue of $H_{p}$ are specifically $e^{i p(\ket{x})}$? And, well, I have to admit something: we know it must be unitary, it must be consistent to $p(\ket{x})$'s mapping, and it has to be a linear operator. All this does is ensures we have normalization. But, this process actually gave us valuable insight: We can modify the "degree" in which we seperate our inital input state from the resulting one through $\gamma$. Allowing multiple applications of $\gamma$ seperated by time also give sthe impression that we are evolving our state into one encodes more and more how "desirable" states are.

Now, if we kept applying this operation, we would find ourselves seperating the maximizing and minimizing state drammatically from the other states, but, for sake of argument, say we are always minimizing-no loss to generality. Then, the states which evolve the slowest under gamma are our optimization solutions.

If we apply Pauli $X$ rotation gate, we see that it effectively acts to perturb our system by slowing flipping bits. One thing to note is that its eigenbasis is the Hadamard basis meaning that it should act on phase without bias to any of the $Z$ basis vectors-giving hope that it might help us. In fact, this implies that our energy evaluation for each state will change as the operator's are non-communiting.

$$e^{-i \beta X} = I\cos{\beta} - iX\sin{\beta}$$

A careful analysis of the action of these two operators reveals that the choice of $\gamma$ directly impacts the degree of mixing and the average degree of mixing of solutions is controlled by $\beta$. As we know that resulting phase from $\gamma$ implies, in the case of the minimizing solution, the least perturbation from the starting state, it is easy to see that our solution state would be the steady eigenstate state of our problem. The question becomes though: how long do we have to iterate this process? Theoretically, we can quite easily find a choice of $\beta$ and $\gamma$ which has this property and implies the following: $$\bra{\ket{\psi_{i+1}}}H_{C}\ket{\ket{\psi_{i+1}}} < \bra{\ket{\psi_{i}}}H_{C}\ket{\ket{\psi_{i}}}$$

However, this could take an unpredictable amount of time. But, it is shown you can get a sufficient approximation in polytime if one allows optimization over the betas and gammas. The question is why does this work. The core insight is to continue thinking about us "trialing to a different extent" each solution and then "changing the degree at which we transition out of bad solutions towards better ones". Maybe in the beginning, we can be pretty agressive going to good solutions as the main ones we are going from are drastically larger than our desired solution, but, as we get closer, we have to be a bit more cautious from going away from solutions so easily. It is this insight which motivates QAOA.