Optimal QAOA design for the Traveling Salesman Problem

The talk will be given by:

Adam Glos

Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Gliwice, PL

Abstract

Combinatorial Optimization is a potential candidate for achieving quantum advantage in the Noisy Intermediate-Scale Quantum era. Quantum Approximate Optimization Algorithm (QAOA) is a promising algorithm that may provide solutions to these problems faster than its classical counterparts. Unfortunately, QAOA requires that the problem Hamiltonian is implemented in the circuit, thus directly affecting the resources required. For example, for the Travelling Salesman Problem (TSP) all the known implementations require either O(n^2) number of qubits or O(n^2) depth. We show that this limitation can be broken through the use of simulated QAOA, where instead of applying each Pauli term independently, a quantum version of classical pseudocode is implemented, using only O(n log(n)) number of qubits and O(n polylog(n)) depth, even on the LNN architecture. In fact, other significant cost measures such as the number of gates, trainable gates or energy span are also optimized. Our results are the first which show significant improvement over state-of-the-art problem Hamiltonian implementation for TSP.

Bio: Adam Glos is a PhD researcher working in the Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, and the Finnish start-up Algorithmiq. His research area covers the NISQ-era oriented optimization, with a particular focus on the efficient representations for the currently most prominent quantum algorithms.