A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem

Abstract

Amplitude Amplification offers a provable speedup for search problems, which is leveraged in combinatorial optimization by Grover Adaptive Search (GAS). The protocol demands deep circuits that are challenging with regards to NISQ capabilities. We propose a nested Amplitude Amplification protocol for the binary knapsack problem that splits the decision tree at a tunable depth, performing a partial amplification on the first variables before executing a global GAS on the full search space. The partial amplification is implemented by an Inner Iteration Finder that selects the rotation count maximizing marked-subspace amplitude. The resulting biased superposition serves as the initial state for the outer Amplitude Amplification. Using the Quantum Tree Generator for feasible-state preparation and an efficient classical amplitude-tracking scheme, we simulate the protocol on knapsack instances of sizes intractable by statevector simulation. Our results show that the nested approach reduces the cost of improving an incumbent solution compared to baseline GAS, particularly for a specific subset of knapsack instances. As combinatorial problems in domains such as semiconductor supply-chain planning grow in scale, methods that reduce circuit cost are an important step toward eventual quantum advantage for such applications.