A quantum search method for quadratic and multidimensional knapsack problems

• URL: http://arxiv.org/abs/2503.22325v1
• Date: Fri, 28 Mar 2025 10:58:26 GMT
• Title: A quantum search method for quadratic and multidimensional knapsack problems
• Authors: Sören Wilkening, Andreea-Iulia Lefterovici, Lennart Binkowski, Marlene Funck, Michael Perk, Robert Karimov, Sándor Fekete, Tobias J. Osborne,
• Abstract summary: We extend the "Quantum Tree Generator" (QTG) to the 0-1 Knapsack Problem, the 0-1 Quadratic Knapsack Problem (QKP) and the Multidimensional Knapsack Problem (MDKP)<n>The QTG constructs a superposition of all feasible solutions for a given instance and can therefore be utilized as a promising state preparation routine.<n>We evaluate the algorithm's performance on QKP and MDKP against the classical solver Gurobi.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Solving combinatorial optimization problems is a promising application area for quantum algorithms in real-world scenarios. In this work, we extend the "Quantum Tree Generator" (QTG), previously proposed for the 0-1 Knapsack Problem, to the 0-1 Quadratic Knapsack Problem (QKP) and the Multidimensional Knapsack Problem (MDKP). The QTG constructs a superposition of all feasible solutions for a given instance and can therefore be utilized as a promising state preparation routine within amplitude amplification to produce high-quality solutions. Previously, QTG-based search was tested on the 0-1 Knapsack Problem, where it demonstrated the potential for practical quantum advantage, once quantum computers with a few hundred logical and fully connected qubits are available. Here, we evaluate the algorithm's performance on QKP and MDKP against the classical solver Gurobi. To facilitate large-scale evaluations, we employ an advanced benchmarking technique that enables runtime predictions for instances with up to 2000 variables for QKP and up to 1500 variables and 100 constraints for MDKP. Our results indicate that QTG-based search can produce high-quality solutions with competitive runtimes for QKP. However, its performance declines for MDKP, highlighting the challenges quantum algorithms face when tackling highly constrained optimization problems.

Related papers

• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods. We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• 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)
• Depth scaling of unstructured search via quantum approximate optimization [0.0]
  Variational quantum algorithms have become the de facto model for current quantum computations. One such problem is unstructured search which consists on finding a particular bit of string. We trotterize a CTQW to recover a QAOA sequence, and employ recent advances on the theory of Trotter formulas to bound the query complexity.
  arXiv  Detail & Related papers  (2024-03-22T18:00:03Z)
• A quantum algorithm for solving 0-1 Knapsack problems [0.0]
  We introduce the "Quantum Tree Generator", an approach to generate in superposition all feasible solutions of a given instance. By introducing a new runtime calculation technique, we can predict the runtime of our method way beyond the range of existing platforms and simulators.
  arXiv  Detail & Related papers  (2023-10-10T13:40:30Z)
• 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)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• 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-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• 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)
• 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.