A quantum algorithm for solving 0-1 Knapsack problems
arXiv:2310.06623 · doi:10.1038/s41534-025-01097-8
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 massive memory savings and enables competitive runtimes compared to the classical state-of-the-art knapsack solvers (such as COMBO, Gurobi, CP-SAT, Greedy) already for instances involving as few as 100 variables. (2) By introducing a new runtime calculation technique that exploits logging data from the classical solver 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 600 variables. Combining both of these innovations, we demonstrate the QTG's potential practical quantum advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems.
6+13 pages, 11 figures
References in corpus (21)
- Quantum Computing in the NISQ era and beyond
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Quantum Annealing in the Transverse Ising Model
- A Quantum Approximate Optimization Algorithm
- Superconducting Qubits: Current State of Play
- Quantum computing with trapped ions
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Photonic quantum information processing: a concise review
- Quantum Computation by Adiabatic Evolution
- Quantum Decoherence
- Demonstration of Universal Parametric Entangling Gates on a Multi-Qubit Lattice
- Addition on a Quantum Computer
- Quantum Computing based Hybrid Solution Strategies for Large-scale Discrete-Continuous Optimization Problems
- Nested quantum search and NP-complete problems
- Quantum-Computing Architecture based on Large-Scale Multi-Dimensional Continuous-Variable Cluster States in a Scalable Photonic Platform
- Quantum speedup of branch-and-bound algorithms
- Fast Simulation of High-Depth QAOA Circuits
- Elementary Proof of QAOA Convergence
- Universal Quantum Speedup for Branch-and-Bound, Branch-and-Cut, and Tree-Search Algorithms
- Quantifying Grover speed-ups beyond asymptotic analysis
- Realistic Runtime Analysis for Quantum Simplex Computation