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.
Comments
This work has been submitted to the IEEE for possible publication
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.
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 (AAMQAOA). 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.
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.
The K-SAT problem is a fundamental challenge in computational theory, widely used in artificial intelligence, cryptography, and optimization. Classical algorithms struggle with exponential time complexity, making them inefficient for large-scale instances. In this research, we propose an efficient quantum computing approach based on Grover’s algorithm to enhance the search process for satisfiable solutions in K-SAT problems. Our implementation leverages quantum superposition and amplitude amplification to explore multiple possible solutions simultaneously, reducing the search complexity from O (2ⁿ) in classical methods to O(√2ⁿ) in quantum computing. We design a quantum oracle that encodes the K-SAT clauses and integrates it into Grover’s iterative search framework. The performance is evaluated through Qiskit simulations, demonstrating a significant improvement in search efficiency compared to classical brute-force techniques. The results highlight the potential of quantum algorithms in solving complex combinatorial problems with enhanced speed and accuracy. This study contributes to the development of quantum-accelerated optimization methods, paving the way for real-world applications in machine learning, cryptanalysis, and large-scale data processing.
Quantum Amplitude Amplification (QAA), the generalization of Grover's algorithm, is well-positioned for combinatorial optimization and is particularly promising for Quadratic Unconstrained Binary Optimization (QUBO) problems. QAA is appealing due to its ability to drive the quantum system to a target state, yielding the globally optimal solution with probability over 90+%. However, realizing QAA for application-scale optimization currently exceeds quantum hardware capacity, which is further compounded by unresolved algorithmic challenges regarding the choice of free parameters. In this study, we address these issues by utilizing a realistic traffic flow QUBO problem to investigate the implementation of QAA as a heuristic solver. Specifically, allowing the diffusion operator parameter to take non-π values expands the capabilities of QAA. This unlocks a new multiple-shot, low-iteration strategy that aims for a high cumulative probability rather than maximizing the probability of a single basis state. Using 25-qubit simulations, our results demonstrate that heuristic QAA addresses two of the main challenges cited in previous studies. Firstly, heuristic QAA works even at a single iteration, reducing circuit depth by orders of magnitude compared to standard QAA. And secondly, we show that the problem-dependent parameters necessary for reaching optimal algorithmic performance can be reliably approximated with minimal upfront classical computing overhead.
Abstract We present two novel contributions for achieving and assessing quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the “Quantum Tree Generator” to generate in superposition all feasible solutions of a given 0-1 knapsack instance; combined with amplitude amplification, this identifies optimal solutions. Assuming fully connected logical qubits and comparable quantum clock speed, QTG offers perspectives for runtimes competitive to classical state-of-the-art knapsack solvers for instances with only 100 variables. (2) By introducing a new technique that exploits logging data from a classical solver, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for benchmark instances with up to 600 variables. Under the given assumptions, we demonstrate the QTG’s potential practical quantum advantage for such instances, indicating the promise of an effective approach for hard combinatorial optimisation problems.
In binary optimization problems, where the goal is to find the inputxthat minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.