Quantum approximation optimization algorithm for traveling salesman problem on 5-qubit IQM spark quantum computer

Abstract

In this paper, we consider a method for solving difficult combinatorial optimization problems on real quantum computers. We focus on the traveling salesman problem as a representative problem for a group of problems where the solution is represented by a permutation. Typically, existing algorithmic solutions use binary matrices to store this permutation – the QUBO (quadratic unconstrained binary optimization) model. We propose a new way of encoding permutations on quantum computers, using a significantly smaller number of qubits than binary matrix encodings. Our method allows for significant performance improvements for any problem whose input or solution is a permutation. We demonstrate an example implementation of the traveling salesman problem on the IQM quantum computers: IQM Spark 5-qubit ‘ODRA-5’ computer and IQM Radiance ‘Garnet’ 20-qubit computer