This is an example of a Quantum Approximate Optimization Algorithm (QAOA) implemented in a Q# program. QAOA was first introduced by Farhi et al. in A Quantum Approximate Optimization Algorithm.This sample is based on the "Traveling Santa" problem described by Stephen Jordan in his Quantum Algorithm Zoo post, Traveling Santa Problem.
Here we will use a combinatorial optimization problem to demonstrate the usage of an implementation of QAOA. We consider a "Traveling Santa" problem. Santa needs to visit a a few different houses and end up back on the North Pole. We can express this as a graph with 4 nodes, where each node represents a house and each node is connected to all other nodes. The edges in the graph each have a cost associated with them. The goal is to find the optimal route such that Santa visits all houses only once and ends up back on the North Pole.
The idea behind QAOA is to express a problem as an Ising Hamiltonian and replace each variable z_j with a Pauli-Z operation acting on the jth qubit, such that:
If we then find the ground state of said Hamiltonian, we can find the solution by measuring the value of each qubit in the Pauli-Z basis. To find said ground state we intersperse time evolutions of the instance Hamiltonian by time evolutions induced by a "driver" Hamiltonian that evolves the qubits by a Pauli-X rotation of the form:
In this sample, the time evolutions are pre-determined, however, these could also be found variationally as part of a hybrid classical-quantum algorithm, by using e.g. gradient descent.
In this sample, we use QAOA to solve the Traveling Santa problem. The constraints are expressed as penalties in the instance Hamiltonian weights and coupling terms. For a more detailed explanation of this sample, please visit Stephen Jordan's Quantum Algorithm Zoo post, Traveling Santa Problem.