QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems

• URL: http://arxiv.org/abs/2404.15852v1
• Date: Wed, 24 Apr 2024 13:02:33 GMT
• Title: QOPTLib: a Quantum Computing Oriented Benchmark for Combinatorial Optimization Problems
• Authors: Eneko Osaba, Esther Villar-Rodriguez,
• Abstract summary: We propose a quantum computing oriented benchmark for optimization. This benchmark, coined as QOPTLib, is composed of 40 instances equally distributed over four well-known problems. In this paper, we introduce a first full solving of QOPTLib using two solvers based on quantum annealing.
• Score: 0.4972323953932129
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Black-Litterman Portfolio Optimization with Noisy Intermediate-Scale Quantum Computers [0.14732811715354452]
  We demonstrate a practical application of noisy intermediate-scale quantum (NISQ) algorithms to enhance subroutines in the Black-Litterman (BL) portfolio optimization model. As a proof of concept, we implement a 12-qubit example for selecting 6 assets out of a 12-asset pool.
  arXiv  Detail & Related papers  (2023-12-01T19:42:04Z)
• QUIK: Towards End-to-End 4-Bit Inference on Generative Large Language Models [57.04178959678024]
  We show that the majority of inference computations for large generative models can be performed with both weights and activations being cast to 4 bits. We achieve this via a hybrid quantization strategy called QUIK, which compresses most of the weights and activations to 4-bit. We provide GPU kernels matching the QUIK format with highly-efficient layer-wise runtimes, which lead to practical end-to-end throughput improvements of up to 3.4x.
  arXiv  Detail & Related papers  (2023-10-13T17:15:05Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem [0.8434687648198277]
  The Bin Packing Problem (BPP) stands out as a paradigmatic optimization problem in logistics. We have recently proposed a hybrid approach to the one dimensional BPP. We compare the performance of our procedure with other classical approaches.
  arXiv  Detail & Related papers  (2022-07-15T13:09:12Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Hybrid Quantum-Classical Heuristic for the Bin Packing Problem [0.8434687648198277]
  A hybrid classical-quantum approach is presented for dealing with the one-dimensional Bin Packing Problem (1dBPP) A classical computation subroutine builds complete solutions to the problem from the subsets given by the quantum subroutine. Being a hybrid solver, we have called our method H-BPP.
  arXiv  Detail & Related papers  (2022-04-12T09:05:27Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new results on the Asymmetric Salesman Problem [1.672938048065882]
  This paper extends the results and findings of the recently proposed hybrid Quantum Computing - Tabu Search Algorithm for partitioning problems. As an additional contribution, this work supposes the first solver of the Asymmetric Traveling Salesman Problem using a Quantum Computing based method.
  arXiv  Detail & Related papers  (2021-02-11T10:08:44Z)
• Larger Sparse Quadratic Assignment Problem Optimization Using Quantum Annealing and a Bit-Flip Heuristic Algorithm [0.4125187280299248]
  Linear constraints reduce the size of problems that can be represented in quantum annealers. We propose a method for solving a sparse QAP by applying a post-processing bit-flip algorithm to solutions obtained by the Ohzeki method. We successfully solved a QAP of size 19 with high accuracy for the first time using D-Wave Advantage.
  arXiv  Detail & Related papers  (2020-12-18T09:48:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.