Review of quantum optimisation techniques for the quadratic assignment problem

Abstract

The Quadratic Assignment Problem (QAP) is one of the fundamental Combinatorial Optimisation Problems (COP), solving many real-life scenarios. However, the exponential increase in CPU time taken to deterministically solve the 𝒩𝒫-Hard QAP, as the problem size scales, has resulted in a search for non-deterministic optimisation solution techniques to obtain solutions to the QAP efficiently. The work presented extends and contributes to research into the QAP and using classical and quantum methods to solve it. While previous work has focused on improving classical heuristics, a study has not compared the Variational Quantum Eigensolver (VQE) algorithm and Quantum Approximate Optimisation Algorithm (QAOA) results from the QAP. This paper presents a warm start technique for the VQE and QAOA, allowing a comparison between both methods and the classical benchmark deterministic and heuristic methods. The comparison of the methods uses metrics to measure solution quality, introduced from previous work on this topic. The results show that classical methods are more accurate and time-efficient than the VQE and the QAOA on IBM Quantum systems and simulators. The results illustrate the evolution of the processors and their effects on the VQE. For the QAOA, there is an investigation into the impact of the 𝑝-value (a determination of circuit depth). Of the two quantum hybrid heuristics, the VQE is more time-efficient, and the smaller circuit size means solving more significant instances with this warm start method. The QAOA performs better in solution quality over increased problem size than the VQE. This work investigates the comparison of the impact of a new set of basis gates on the quantum optimisation techniques for the VQE; the results did not reflect any consistent relationship. The results show that the VQE has fewer operations than QAOA and that increasing 𝑝-values have more complex circuits. Results of a quantum warm-start method imply the QAOA may not maintain higher solution quality for instances larger than size 4, but more results are required. These conclusions contribute to those working to solve COP, particularly those using quantum computers.