A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems
Monit Sharma 1, Hoong Chuin Lau 1,2 · 2025
Read A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems by Monit Sharma 1, Hoong Chuin Lau 1,2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-12121.txt.
Introduction
Quantum methods promise fresh ways to solve hard sorting and packing puzzles, but fair tests of those claims are scarce. Monit Sharma and Hoong Chuin Lau build a shared test frame in 2025 that weighs quantum tools by answer quality, speed, and growth with problem size. The test set uses four classic hard problem types.
The set covers a multi-limit knapsack task, a largest free set task, an assignment task, and a market share task. The team tests gate-based methods, among them two forms of a quantum solver and a quantum approximation method with its variants. To cope with tight hardware limits, they add tricks that shrink the number of quantum bits a task needs. The frame gives a shared yardstick for the field.
Catalog record
| CREATOR | Monit Sharma 1, Hoong Chuin Lau 1,2 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 101 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-12121
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Comparative Study of Quantum Optimization Techniques for Solving Combinatorial Optimization Benchmark Problems Monit Sharma 1, Hoong Chuin Lau 1,2 Abstract Quantum optimization holds promise for addressing classically intractable combinatorial problems, yet a standardized framework for benchmarking its performance—particularly in terms of solution quality, computational speed, and scalability—is still lacking. In this work, we introduce a comprehensive benchmarking framework designed to systematically evaluate a range of quantum optimization techniques against well-established NP-hard combinatorial problems. Our framework focuses on key problem classes, including the Multi-Dimensional Knapsack Problem (MDKP), Maximum Independent Set (MIS), Quadratic Assignment Problem (QAP), and Market Share Problem (MSP) Our study evaluates gate-based quantum approaches, including the Variational Quantum Eigensolver (VQE) and its CVaR-enhanced variant, alongside advanced quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) and its extensions. To address resource constraints, we incorporate qubit compression techniques like Pauli Correlation Encoding (PCE) and Quantum Random Access Optimization (QRAO). Experimental results, obtained from simulated quantum environments and classical solvers, provide key insights into feasibility, optimality gaps, and scalability. Our findings highlight both the promise and current limitations of quantum optimization, offering a structured pathway for future research and practical applications in quantum-enhanced decision-making. Preprint: APS/123-QED I Introduction Combinatorial optimization plays a fundamental role in a wide range of scientific and industrial applications, including logistics [ 1 ] , finance [ 2 ] , telecommunications [ 3 ] , and drug discovery [ 4 ] . Many critical problems in these fields fall within the class of NP-hard problems [ 5 ] , rendering them computationally intractable for large instances. Despite substantial advancements in classical optimization techniques, solving these problems remains challenging, as exact methods often become impractical due to their exponential scaling. Quantum computing has emerged as a promising frontier in combinatorial optimization research, offering the potential to tackle these problems [ 6 ] . The performance of quantum optimization algorithms is inherently tied to rigorous benchmarking. Unlike classical optimization, where well-established benchmarks exist [ 7 ] for evaluating solvers, quantum optimization still lacks standardized methodologies and datasets that can reliably assess the effectiveness and scalability of quantum approaches. This gap hinders the ability to systematically compare algorithms, evaluate hardware capabilities, and understand the practical advantages quantum optimization might offer over classical techniques. Benchmarking in quantum optimization serves multiple critical purposes. Firstly, it provides a structured way to measure progress in algorithmic and hardware development. The nascent field of quantum optimization is rapidly evolving, with new quantum algorithms being proposed, while the well known ones such as the Quantum Approximate Optimization Algorithm (QAOA) [ 8 ] and Variational Quantum Eigensolver (VQE) [ 9 ] , are being refined [ 10 , 11 , 12 ] . Benchmarking enables researchers to evaluate these methods consistently across diverse problem instances and sizes, offering insights into their practical performance and limitations. Secondly, benchmarking facilitates reproducibility and transparency in quantum computing research. With the inherent complexity of quantum hardware and its susceptibility to noise, it is crucial to establish robust benchmarks that can differentiate between genuine algorithmic improvements and artifacts caused by hardware-specific effects. Such benchmarks help create a level playing field for researchers and practitioners, fostering a collaborative environment for innovation. Thirdly, benchmarks play a pivotal role in bridging the gap between theoretical promise and practical application. Many quantum algorithms exhibit theoretical advantages under specific assumptions, but their performance on real-world problems often deviates due to hardware constraints, such as limited qubit counts, decoherence, and gate fidelities. Benchmarking against practical datasets, such as those derived from real-world industrial problems, provides a reality check, highlighting the strengths and weaknesses of quantum optimization in practical settings. The absence of a well-defined benchmarking framework also poses challenges for industry adoption. Decision-makers in industries such as logistics, finance, and supply chain management require clear evidence of the advantages of quantum optimization before committing resources to its implementation. A comprehensive benchmarking framework can provide this evidence, demonstrating the specific scenarios where quantum optimization outperforms classical methods or offers complementary benefits. Moreover, benchmarking is essential for guiding the co-evolution of quantum hardware and algorithms. By identifying the problem instances and parameter regimes where quantum optimization excels, benchmarks inform hardware designers about the critical requirements for next-generation quantum devices. Similarly, they help algorithm developers tailor their methods to leverage the unique capabilities of quantum hardware. To establish quantum optimization as a practical tool for solving real-world problems, the development of benchmarking frameworks must consider diverse factors. These include the selection of problem instances, the definition of performance metrics, and the handling of noise and errors in quantum computations. Additionally, benchmarking should address the trade-offs between solution quality, runtime, and resource utilization, providing a holistic view of quantum optimization’s performance. In this paper, we aim to bridge the existing gap by presenting a comprehensive benchmarking framework for quantum optimization. By tackling classically proven hard problems [ 13 , 14 , 15 ] , such as the Multi-Dimensional Knapsack Problem (MDKP) [ 16 ] , Maximum Independent Set (MIS) [ 17 ] , Market Share Problem (MSP) [ 18 ] and Quadratic Assignment Problem (QAP) [ 19 ] , and using metrics tailored to quantum algorithms, we provide a robust foundation for evaluating quantum optimization methods. Our framework is designed to facilitate fair comparisons between classical and quantum solvers, highlight the unique strengths of quantum approaches, and identify areas where further research and development are needed. These problems were selected (among many other candidates) because they not only represent classically proven hard problems that remain challenging for state-of-the-art classical solvers, but also give rise to real-world business problems (in logistics, supply chains and finance). Notably, QAP is among the “hardest of the hard” combinatorial optimization problems, as finding even an \epsilon -approximate solution has been proven to be NP-complete [ 15 ] . Moreover, other well-known NP-hard problems, such as the Traveling Salesman Problem (TSP), are special cases of QAP [ 20 ] . Other challenging combinatorial optimization problems that were not considered in this study include the Low Autocorrelation Binary Sequences (LABS) problem [ 21 ] , the Sports Timetabling problem [ 22 ] , among others. II Our Contributions In this paper, we make the following key contributions: 1. A Comprehensive Benchmarking Framework for Quantum Optimization: We present a rigorous benchmarking framework tailored for quantum optimization. This framework systematically evaluates a select set of combinatorial optimization problems that remain computationally challenging even at small scales. By focusing on problem instances that are within an intermediate size range where current and/or near-term quantum technologies can be effectively deployed, our approach enables a critical assessment of quantum techniques against current classical techniques. 2. Detailed Analysis of Hard Optimization Problems: We conduct a detailed examination of each benchmark problem, highlighting their inherent computational challenges and identifying key parameter settings that amplify their difficulty. This analysis not only explains why these problems remain intractable even at moderate scales but also serves as a valuable guide for selecting and tuning problem instances in future quantum optimization research. 3. Enhancement of the Market Share Problem: Among the four chosen problems, the Market Share Problem is the least well-studied in the classical optimization community. Hence, a side contribution of this work is to provide a