QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems

Abstract

In this paper, we propose a quantum computing oriented benchmark for combinatorial optimization. This benchmark, coined as QOPTLib, is composed of 40 instances equally distributed over four well-known problems: Traveling Salesman Problem, Vehicle Routing Problem, one-dimensional Bin Packing Problem and the Maximum Cut Problem. The sizes of the instances in QOPTLib not only correspond to computationally addressable sizes, but also to the maximum length approachable with non-zero likelihood of getting a good result. In this regard, it is important to highlight that hybrid approaches are also taken into consideration. Thus, this benchmark constitutes the first effort to provide users a general-purpose dataset. Also in this paper, we introduce a first full solving of QOPTLib using two solvers based on quantum annealing. Our main intention with this is to establish a preliminary baseline, hoping to inspire other researchers to beat these outcomes with newly proposed quantum-based algorithms.

arXiv comment15 pages, 3 figures, 1 table

References in corpus (19)

• Quantum Computing in the NISQ era and beyond
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum computing for finance: overview and prospects
• Quantum Computing for Finance: State of the Art and Future Prospects
• The Impact of Quantum Computing on Present Cryptography
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
• Quantum computing for energy systems optimization: Challenges and opportunities
• A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy
• A Hybrid Solution Method for the Capacitated Vehicle Routing Problem Using a Quantum Annealer
• Solving Vehicle Routing Problem Using Quantum Approximate Optimization Algorithm
• Quantum computers as universal quantum simulators: state-of-art and perspectives
• Dynamic Portfolio Optimization with Real Datasets Using Quantum Processors and Quantum-Inspired Tensor Networks
• The state of quantum computing applications in health and medicine
• A case study of variational quantum algorithms for a job shop scheduling problem
• Democratization of Quantum Technologies
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Analysis of The Vehicle Routing Problem Solved via Hybrid Quantum Algorithms in Presence of Noisy Channels
• Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem