The Quantum Approximate Optimization Algorithm (QAOA) [1] is a metaheuristic gate-model quantum algorithm, mainly used for solving combinatorial optimization problems, such as Max-Cut, or the Travelling Salesman Problem. The main goal of the algorithm is to find an upper bound to the ground state energy, using the Cost Hamiltonian, which is based on the objective function of the optimization problem. Usually, the solutions of such an optimization problem are provided as a binary string, therefore any computational basis state can be considered as one solution to the optimization problem. In the algorithm, the application of Cost Hamiltonian achieves phase separation, in relation to the costs of each individual solution. The algorithm also includes another Hamiltonian called as the Mixer, and it is defined as a Hermitian matrix that does not commute with the Cost Hamiltonian. The Mixer Hamiltonian tries to mix the probabilities of all possible solutions. The aim for applying such a Mixer Hamiltonian, is to be able to explore the whole solution space, and avoid potential local minima.

In a recent work, Hadfield [2], showed that the role of Mixer Hamiltonians, can be expanded when there are constraints involved in the optimization problem. Preparing according to the hard constraints of a problem, the Mixer is ensured, not only to explore the whole solution space, but to also restrict it according to the corresponding constraints. However, preparing a Mixer can be cumbersome, since it requires distinct ansatz for different problems and constraints. We are proposing a different approach for solving such constrained optimization problems. Instead of using a problem specific Mixer Hamiltonian, we are using an encoding scheme, that shrinks the search space into the feasible subspace. After applying the Cost Hamiltonian and the encoder in a cascaded manner, we aim to find an approximate solution to the optimization problem, that satisfies the constraints, using the Travelling Salesman Problem as an example. Therefore, our overall goal is to provide an optimization scheme for a constrained optimization problem, along with comparing the convergence of the algorithm with the state-of-art approaches.

References

[1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028, 2014.

[2] Stuart Hadfield, Zhihui Wang, Eleanor G Rieffel, Bryan O’Gorman, Davide Venturelli, and Rupak Biswas. Quantum approximate optimization with hard and soft constraints. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pages 15–21, 2017.