Quantum tree generator improves QAOA state-of-the-art for the knapsack problem

Abstract

This paper introduces a novel approach to the Quantum Approximate Optimization Algorithm (QAOA), specifically tailored to the knapsack problem. We combine the recently proposed quantum tree generator as an efficient state preparation circuit for all feasible solutions to the knapsack problem with the framework of Grover-mixer QAOA to form the first representative of Amplitude Amplification-mixer QAOA (AAM-QAOA). On hard benchmark sets with up to 20 knapsack items, we demonstrate our method's improved performance over the current state-of-the-art Copula-QAOA. However, for larger instance sizes, both approaches fail to deliver better outcomes than greedily packing items in descending value-to-weight ratio, at least for the considered circuit depths. For sufficiently high circuit depths, however, we can prove that AAM-QAOA will eventually be able to sample the optimal solution.

Accepted at QCE25; added IEEE copyright statement, detailed resource estimation

References in corpus (14)

• Quantum Computing in the NISQ era and beyond
• Variational Quantum Algorithms
• Quantum Simulation
• Ising formulations of many NP problems
• Quantum Amplitude Amplification and Estimation
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Warm-starting quantum optimization
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation
• Nested quantum search and NP-complete problems
• Quantum speedup of branch-and-bound algorithms
• Iterative Layerwise Training for Quantum Approximate Optimization Algorithm
• Elementary Proof of QAOA Convergence
• JuliQAOA: Fast, Flexible QAOA Simulation
• Deep-Circuit QAOA