Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem

• URL: http://arxiv.org/abs/2207.07460v1
• Date: Fri, 15 Jul 2022 13:09:12 GMT
• Title: Comparative Benchmark of a Quantum Algorithm for the Bin Packing Problem
• Authors: Mikel Garcia-de-Andoin, Izaskun Oregi, Esther Villar-Rodriguez, Eneko Osaba, Mikel Sanz
• Abstract summary: 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.
• Score: 0.8434687648198277
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Bin Packing Problem (BPP) stands out as a paradigmatic combinatorial optimization problem in logistics. Quantum and hybrid quantum-classical algorithms are expected to show an advantage over their classical counterparts in obtaining approximate solutions for optimization problems. We have recently proposed a hybrid approach to the one dimensional BPP in which a quantum annealing subroutine is employed to sample feasible solutions for single containers. From this reduced search space, a classical optimization subroutine can find the solution to the problem. With the aim of going a step further in the evaluation of our subroutine, in this paper we compare the performance of our procedure with other classical approaches. Concretely we test a random sampling and a random-walk-based heuristic. Employing a benchmark comprising 18 instances, we show that the quantum approach lacks the stagnation behaviour that slows down the classical algorithms. Based on this, we conclude that the quantum strategy can be employed jointly with the random walk to obtain a full sample of feasible solutions in fewer iterations. This work improves our intuition about the benefits of employing the scarce quantum resources to improve the results of a diminishingly efficient classical strategy.

Related papers

• Quantum optimisation applied to the Quadratic Assignment Problem [4.483208369550461]
  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)<n>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.<n>Our findings highlight the practical utility of quantum walks for complex quantum problems and establish a foundation for future quantum optimisation algorithms.
  arXiv  Detail & Related papers  (2026-01-03T07:50:03Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Quantum-Enhanced Optimization by Warm Starts [1.1666234644810893]
  We present an approach, which we term quantum-enhanced optimization, to accelerate classical optimization algorithms by leveraging quantum samples.<n>Our method uses quantum-generated samples as warm starts to classical samplings for solving novel problems like Max-Cut and Maximum Independent Set (MIS)
  arXiv  Detail & Related papers  (2025-08-22T11:36:19Z)
• Provably Faster Algorithms for Bilevel Optimization via Without-Replacement Sampling [96.47086913559289]
  gradient-based algorithms are widely used in bilevel optimization. We introduce a without-replacement sampling based algorithm which achieves a faster convergence rate. We validate our algorithms over both synthetic and real-world applications.
  arXiv  Detail & Related papers  (2024-11-07T17:05:31Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Guess What Quantum Computing Can Do for Test Case Optimization [43.89456212504871]
  In the near term, quantum approximate optimization algorithms (QAOAs) hold great potential to solve optimization problems. We present the first effort to formulate a software test case optimization problem as a QAOA problem and solve it on quantum computer simulators. To solve bigger test optimization problems that require many qubits, which are unavailable these days, we integrate a problem decomposition strategy with the QAOA.
  arXiv  Detail & Related papers  (2023-12-24T21:25:31Z)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• Efficient DCQO Algorithm within the Impulse Regime for Portfolio Optimization [41.94295877935867]
  We propose a faster digital quantum algorithm for portfolio optimization using the digitized-counterdiabatic quantum optimization (DCQO) paradigm. Our approach notably reduces the circuit depth requirement of the algorithm and enhances the solution accuracy, making it suitable for current quantum processors. We experimentally demonstrate the advantages of our protocol using up to 20 qubits on an IonQ trapped-ion quantum computer.
  arXiv  Detail & Related papers  (2023-08-29T17:53:08Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• A quantum advantage over classical for local max cut [48.02822142773719]
  Quantum optimization approximation algorithm (QAOA) has a computational advantage over comparable local classical techniques on degree-3 graphs. Results hint that even small-scale quantum computation, which is relevant to the current state-of the art quantum hardware, could have significant advantages over comparably simple classical.
  arXiv  Detail & Related papers  (2023-04-17T16:42:05Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Adapting Quantum Approximation Optimization Algorithm (QAOA) for Unit Commitment [2.8060379263058794]
  We formulate and apply a hybrid quantum-classical algorithm to a power system optimization problem called Unit Commitment. Our algorithm extends the Quantum Approximation Optimization Algorithm (QAOA) with a classical minimizer in order to support mixed binary optimization. Our results indicate that classical solvers are effective for our simulated Unit Commitment instances with fewer than 400 power generation units.
  arXiv  Detail & Related papers  (2021-10-25T03:37:34Z)
• Quantum Optimization Heuristics with an Application to Knapsack Problems [5.866941279460248]
  This paper introduces two techniques that make the standard Quantum Approximate Optimization Algorithm (QAOA) more suitable for constrained optimization problems. The first technique describes how to use the outcome of a prior greedy classical algorithm to define an initial quantum state and mixing operation to adjust the quantum optimization algorithm to explore the possible answers around this initial greedy solution. The second technique is used to nudge the quantum exploration to avoid the local minima around the greedy solutions.
  arXiv  Detail & Related papers  (2021-08-19T17:22:44Z)
• An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime [0.0]
  We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm. We analyze some of its use cases based on time complexity in the low qubit number regime. We demonstrate the efficacy of our algorithm for a benchmark problem.
  arXiv  Detail & Related papers  (2020-12-04T00:01:15Z)
• Tabu-driven Quantum Neighborhood Samplers [2.9934511331003555]
  Combinatorial optimization is an important application numerically targeted by quantum computing. One option to achieve advantages with near-term devices is to use them in combination with classicals. We show that QAOA provides a flexible tool for exploration Algorithm-exploitation in such hybrid settings.
  arXiv  Detail & Related papers  (2020-11-18T19:30:27Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.