The prevalence of NP-Hard Combinatorial Optimisation Problems (COP) requires a continuous search for powerful heuristic techniques to efficiently solve problems of this nature, due to the exponentially growing CPU times faced by deterministic methods. This paper focuses on two COP, namely the Travelling Salesmen Problem (TSP) and the Quadratic Assignment Problem (QAP). In particular, the computational performance of classical optimisation techniques, Branch and Bound (BNB) and Simulated Annealing (SA), are compared to the Variational Quantum Eigensolver (VQE) algorithm. These algorithms are executed respectively on classical and Noisy Intermediate-Scale Quantum (NISQ) computers, in this case, a host of IBM quantum devices. The experimental results resemble and extend on previously reported results found in the literature. Furthermore, this research critically analyses, compares and comments on the performance of quantum computing techniques to that of classical techniques. The results highlight the current shortcomings of NISQ devices, as classical optimisation techniques significantly outperform the VQE algorithm when run on state of the art IBM Quantum devices.
The prevalence of NP-Hard Combinatorial Optimisation Problems (COP) requires a continuous search for powerful heuristic techniques to efficiently solve problems of this nature, due to the exponentially growing CPU times faced by deterministic methods. This paper focuses on two COP, namely the Travelling Salesmen Problem (TSP) and the Quadratic Assignment Problem (QAP). In particular, the computational performance of classical optimisation techniques, Branch and Bound (BNB) and Simulated Annealing (SA), are compared to the Variational Quantum Eigensolver (VQE) algorithm. These algorithms are executed respectively on classical and Noisy Intermediate-Scale Quantum (NISQ) computers, in this case, a host of IBM quantum devices. The experimental results resemble and extend on previously reported results found in the literature. Furthermore, this research critically analyses, compares and comments on the performance of quantum computing techniques to that of classical techniques. The results highlight the current shortcomings of NISQ devices, as classical optimisation techniques significantly outperform the VQE algorithm when run on state of the art IBM Quantum devices.
The performance of the Quantum Approximate Optimisation Algorithm (QAOA) in solving the Quadratic Assignment Problem (QAP) is evaluated, with the Variational Quantum Eigensolver (VQE) as a benchmark. The QAP is directly revelant to numerous industry scenarios. The QAP, a Combinatorial Optimisation Problem (COP), is classified asNP-Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.
Optimization algorithms for combinatorial problems play a critical role in a wide range of applications, from logistics and scheduling to cryptography and artificial intelligence. Traditional classical methods, such as simulated annealing, genetic algorithms, and branch-and-bound techniques, have been widely employed to solve these problems, but they often face limitations in terms of computational efficiency and scalability as problem complexity grows. In recent years, quantum computing has emerged as a promising alternative, with quantum annealing offering a novel approach to solving combinatorial optimization problems. This study provides a comparative analysis of quantum annealing and classical optimization methods, highlighting their respective strengths and limitations. We explore how quantum annealing, through leveraging quantum tunnelling and superposition, has the potential to outperform classical algorithms in specific problem domains and Noisy Mean Field Annealing (NMFA) is used to comparisons of all algorithms. Benchmarking various combinatorial problems, such as the Traveling Salesman Problem (TSP), Max-Cut, Knapsack, and Quadratic Assignment Problem (QAP), this paper discusses performance metrics, computational time, and scalability. The findings suggest that while classical methods remain robust and practical for many real-world problems, quantum annealing holds significant promise, especially as quantum hardware continues to mature. However, there remain challenges in terms of noise, coherence, and problem mapping, which currently limit the full realization of quantum annealing's potential. This study offers insights into the future directions of optimization techniques and the evolving role of quantum computing in solving complex combinatorial problems.
This paper investigates the performance of the emerging non-variational Quantum Walk-based Optimisation Algorithm (NV-QWOA) for solving small instances of the Quadratic Assignment Problem (QAP). NV-QWOA is benchmarked against classical heuristics, the MaxMin Ant System (MMAS) and Greedy Local Search (GLS), as well as the Grover quantum search algorithm, which serves as a quantum baseline. Performance is evaluated using two metrics: the number of objective function evaluations and the number of algorithm iterations required to consistently reach optimal or near optimal solutions across QAP instances with 5 to 10 facilities. The motivation for this study stems from limitations of both classical exact methods and current quantum algorithms. Variational Quantum Algorithms (VQAs), such as QAOA and VQE, while widely studied, suffer from costly parameter tuning and barren plateaus that hinder convergence. By adopting a non-variational approach, this work explores a potentially more efficient and scalable quantum strategy for combinatorial optimisation. The results provide a direct comparative analysis between classical and quantum frameworks, characterising the average case performance of NV-QWOA. Our findings highlight the practical utility of quantum walks for complex combinatorial problems and establish a foundation for future quantum optimisation algorithms.
Claims of quantum advantage for combinatorial optimisation require rigorous comparison against state-of-the-art classical algorithms under controlled experimental conditions -- yet the quantum computing literature frequently benchmarks quantum methods against weak classical baselines such as greedy heuristics or random search, inflating apparent quantum advantage. This paper presents the Quantum-Classical Combinatorial Benchmark (QCCB), a rigorous comparative study of quantum optimisation algorithms (QAOA, VQE-QUBO, hybrid QA) against nine state-of-the-art classical algorithms (Goemans-Williamson SDP, simulated annealing, tabu search, CPLEX branch-and-bound, OR-Tools CP-SAT, Gurobi MIP, Benders decomposition, extremal optimisation, and population-based iterated local search) across six canonical combinatorial problem classes (MaxCut, Vertex Cover, Graph Colouring, Knapsack, Set Cover, and Weighted Max-SAT) at problem sizes n = 12 to n = 256. QCCB finds that no quantum algorithm consistently outperforms all classical baselines across all problem classes at current NISQ scale. QAOA with QOAS adaptive depth (Bianchi, 2024) outperforms all nine classical algorithms on MaxCut at n = 48 (approximation ratio 0.924 vs. GW 0.878). However, classical Gurobi MIP and CPLEX solve MaxCut exactly for n up to n = 84 within the same time budget, eliminating the QAOA advantage at moderate scale. QCCB provides nuanced guidance on problem classes, instance sizes, and time budgets where quantum algorithms offer genuine near-term advantage.
Permutation problems, such as the Travelling Salesman Problem (TSP) and the Quadratic Assignment Problem (QAP), form a well-established class of combinatorial optimisation problems with broad applications in routing, assignment, and scheduling. Metaheuristics, particularly Evolutionary Algorithms (EAs), have been widely demonstrated to yield high-quality solutions for these problems. In parallel, classical commercial solvers based on Mixed-Integer Programming (MIP), including CPLEX and Gurobi, have also been extensively applied. In recent years, there has been growing interest in quantum, quantum-inspired, and quantum-hybrid approaches for solving combinatorial optimisation problems. This paper presents a comparative analysis of six optimisation solvers: Genetic Algorithm (GA), Estimation of Distribution Algorithm (EDA), CPLEX, Gurobi, Digital Annealer (DA), and a quantum-hybrid Nonlinear solver (NL), applied to permutation problems. We evaluate solver performance in terms of runtime, solution quality relative to optimality, and scalability across instances of TSP and QAP. Our results highlight the promising performance of the quantum-hybrid Nonlinear solver across all evaluation metrics.
NP-hard problems are one of the most computationally intensive challenges in computer science, appearing in many domains such as logistics, cybersecurity, drug design, and financial modelling. Classical algorithms become impractical as problem size increases due to combinatorial explosion. This paper presents a structured framework for analysing quantum algorithms targeting NP-hard optimization problems, like the Traveling Salesman Problem (TSP), Max-Cut, and Boolean Satisfiability (SAT). We have developed a taxonomy which categorizes quantum approaches—quantum annealing, variational algorithms (QAOA/VQE), and Grover-based search—based on problem encoding strategies, resource requirements, and theoretical guarantees. From the comparative analysis of existing literature, we: 1) Map algorithm classes to problem domains (e.g., QAOA for Max-Cut, annealing for TSP) 2) Identify performance trade-offs between solution quality, qubit counts, and circuit depth 3) Analyse hardware compatibility constraints across NISQ platforms 4) Reveal fundamental scalability barriers including noise susceptibility and embedding overhead The framework establishes implementation guidelines for near- term quantum hardware and proposes hybrid quantum-classical pathways to bridge theoretical potential and practical deployment. This systematic analysis prioritizes research directions for achieving quantum advantage in combinatorial optimization.