QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing
- URL: http://arxiv.org/abs/2309.12678v2
- Date: Mon, 15 Jan 2024 20:10:40 GMT
- Title: QAL-BP: An Augmented Lagrangian Quantum Approach for Bin Packing
- Authors: Lorenzo Cellini, Antonio Macaluso, Michele Lombardi
- Abstract summary: The bin packing is a well-known NP-Hard problem in the domain of artificial intelligence.
Recent advancements in quantum technologies have shown promising potential for achieving substantial computational speedup.
We introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO) formulation designed specifically for bin packing.
- Score: 4.589533935256401
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The bin packing is a well-known NP-Hard problem in the domain of artificial
intelligence, posing significant challenges in finding efficient solutions.
Conversely, recent advancements in quantum technologies have shown promising
potential for achieving substantial computational speedup, particularly in
certain problem classes, such as combinatorial optimization. In this study, we
introduce QAL-BP, a novel Quadratic Unconstrained Binary Optimization (QUBO)
formulation designed specifically for bin packing and suitable for quantum
computation. QAL-BP utilizes the Augmented Lagrangian method to incorporate the
bin packing constraints into the objective function while also facilitating an
analytical estimation of heuristic, but empirically robust, penalty
multipliers. This approach leads to a more versatile and generalizable model
that eliminates the need for empirically calculating instance-dependent
Lagrangian coefficients, a requirement commonly encountered in alternative QUBO
formulations for similar problems. To assess the effectiveness of our proposed
approach, we conduct experiments on a set of bin packing instances using a real
Quantum Annealing device. Additionally, we compare the results with those
obtained from two different classical solvers, namely simulated annealing and
Gurobi. The experimental findings not only confirm the correctness of the
proposed formulation but also demonstrate the potential of quantum computation
in effectively solving the bin packing problem, particularly as more reliable
quantum technology becomes available.
Related papers
- Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems [0.4915744683251151]
We show that inequality constraints can be relaxed into a similar objective function through statistical mechanics.
We evaluate the performance of this method in a typical inequality-constrained optimization problem, the quadratic knapsack problem.
arXiv Detail & Related papers (2024-11-11T11:59:50Z) - Beyond QUBO and HOBO formulations, solving the Travelling Salesman Problem on a quantum boson sampler [0.0]
We present a novel formulation which needs fewer binary variables, and where, by design, there are no penalty terms because all outputs from the quantum device are mapped to valid routes.
Although we worked with a boson sampler, we believe that this novel formulation is relevant to other quantum devices.
arXiv Detail & Related papers (2024-06-20T12:25:00Z) - Solving Combinatorial Optimization Problems with a Block Encoding Quantum Optimizer [0.0]
Block ENcoding Quantum (BEQO) is a hybrid quantum solver that uses block encoding to represent the cost function.
Our findings confirm that BENQO performs significantly better than QAOA and competes with VQE across a variety of performance metrics.
arXiv Detail & Related papers (2024-04-22T10:10:29Z) - Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems.
In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems.
We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
arXiv Detail & Related papers (2024-04-17T11:00:12Z) - Variational quantum eigensolver with linear depth problem-inspired
ansatz for solving portfolio optimization in finance [7.501820750179541]
This paper introduces the variational quantum eigensolver (VQE) to solve portfolio optimization problems in finance.
We implement the HDC experiments on the superconducting quantum computer Wu Kong with up to 55 qubits.
The HDC scheme shows great potential for achieving quantum advantage in the NISQ era.
arXiv Detail & Related papers (2024-03-07T07:45:47Z) - Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
Quantum computing sets the foundation for new ways of designing algorithms.
New challenges arise concerning which field quantum speedup can be achieved.
Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
arXiv Detail & Related papers (2024-02-26T09:32:07Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - A Quantum Approach for Stochastic Constrained Binary Optimization [2.6803492658436032]
Quantum-based algorithms have been shown to generate high-quality solutions to hard problems.
This work puts forth quantum vectors to cope with binary quadratically constrained programs.
The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks.
arXiv Detail & Related papers (2023-01-04T04:24:26Z) - Quantum-inspired optimization for wavelength assignment [51.55491037321065]
We propose and develop a quantum-inspired algorithm for solving the wavelength assignment problem.
Our results pave the way to the use of quantum-inspired algorithms for practical problems in telecommunications.
arXiv Detail & Related papers (2022-11-01T07:52:47Z) - Evaluating the Convergence of Tabu Enhanced Hybrid Quantum Optimization [58.720142291102135]
We introduce the Tabu Enhanced Hybrid Quantum Optimization metaheuristic approach useful for optimization problem solving on a quantum hardware.
We address the theoretical convergence of the proposed scheme from the viewpoint of the collisions in the object which stores the tabu states, based on the Ising model.
arXiv Detail & Related papers (2022-09-05T07:23:03Z) - Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems.
By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
arXiv Detail & Related papers (2021-08-03T17:49:09Z)
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.