Quantum Optimisation Achieves Near-Optimal Solutions for 10-Facility Quadratic Assignment Problems

The Quadratic Assignment Problem, a notoriously difficult challenge in combinatorial optimisation, continues to drive research into more efficient solution methods. Andrew Freeland and Jingbo Wang, both from The University of Western Australia, have now explored the potential of a novel, non-variational Quantum Walk-based Optimisation Algorithm (NV-QWOA) to tackle this problem. Their work benchmarks NV-QWOA against established classical heuristics like MaxMin Ant System and Greedy Local Search, alongside the Grover quantum search algorithm, offering a direct comparison of performance. This research is significant because it sidesteps the limitations of current quantum algorithms, specifically the parameter tuning and convergence issues plaguing Variational Quantum Algorithms. By demonstrating the practical utility of quantum walks, Freeland and Wang et al. lay the groundwork for future advances in quantum optimisation strategies for complex problems.

The research aims to establish a comparative understanding of NV-QWOA’s efficacy relative to established classical and quantum approaches for this NP-hard combinatorial optimisation problem. The approach involves implementing NV-QWOA and the selected classical algorithms on QAP benchmark instances of sizes n = 4, 6, 8, and 10 from the QAPLIB.

Performance is evaluated based on the quality of solutions obtained within a fixed computational budget, measured by the number of function evaluations. A detailed comparison of solution qualities and computational effort is undertaken to highlight the strengths and weaknesses of each method. Specific contributions of this work include a rigorous empirical evaluation of NV-QWOA on QAP instances, providing insights into its scalability and performance characteristics. The results demonstrate the ability of NV-QWOA to achieve competitive solutions for small problem sizes, and identify the conditions under which it outperforms classical heuristics. By adopting a non-variational approach, this work explores a potentially more efficient and scalable quantum strategy for combinatorial optimisation. Each instance was solved multiple times, recording the number of objective function evaluations and algorithm iterations to determine average performance. Results provide a direct comparative analysis between classical and quantum frameworks, characterising the average-case performance of NV-QWOA. Findings highlight the practical capabilities of the proposed algorithm, demonstrating its potential to outperform classical counterparts in specific problem sizes and configurations. Further investigation focused on the scalability of NV-QWOA by increasing the number of facilities (n) in the QAP instances, assessing its ability to maintain performance as problem complexity grows. Results indicate polynomial scaling of circuit depth with problem size and competitive performance relative to the tested classical methods. The authors acknowledge limitations related to hardware constraints and computational overhead when scaling to larger problem instances, beyond n=30 where exact algorithms become impractical. Future research should investigate whether the observed trends persist for larger QAP sizes and explore the potential of parameter transfer schemes to extend solutions derived from smaller instances to the classically intractable regime.