A quantum algorithm for the solution of the 0-1 Knapsack problem

• URL: http://arxiv.org/abs/2310.06623v1
• Date: Tue, 10 Oct 2023 13:40:30 GMT
• Title: A quantum algorithm for the solution of the 0-1 Knapsack problem
• Authors: S\"oren Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski, Michael Perk, S\'andor Fekete, and Tobias J. Osborne
• Abstract summary: We introduce the ''Quantum Tree Generator'', an approach to generate in superposition all feasible solutions of a given instance. We also introduce a high-level simulation strategy that exploits logging data from COMBO.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the ''Quantum Tree Generator'', an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for $0$-$1$-Knapsack problems. The QTG offers exponential memory savings and enables competitive runtimes compared to the state-of-the-art Knapsack solver COMBO for instances involving as few as 600 variables. (2) By introducing a high-level simulation strategy that exploits logging data from COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 1600 variables. Combining both of these innovations, we demonstrate the QTG's potential advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems.

Related papers

• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
  arXiv  Detail & Related papers  (2024-08-14T20:06:32Z)
• 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)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• 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)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• 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)
• Adiabatic Quantum Optimization Fails to Solve the Knapsack Problem [0.0]
  We use the D-Wave 2000Q adiabatic quantum computer to solve the integer-weight knapsack problem. We find that adiabatic quantum optimization fails to produce solutions corresponding to optimal filling of the knapsack.
  arXiv  Detail & Related papers  (2020-08-17T16:29:34Z)
• 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.