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.
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.
Grover-Mixer QAOA (GM-QAOA) is a promising quantum framework for constrained combinatorial optimization. However, its practical implementation requires the efficient preparation of a uniform superposition over feasible states. In this work, we propose a two-stage variational approach. First, a parameterized quantum circuit is trained to prepare this superposition, using an entropy-based cost function that favors a uniform distribution over feasible bitstrings. The trained circuit is then embedded in GM-QAOA, where it provides both the initial state and, together with its inverse, yields the Grover mixer. The resulting method is evaluated on two representative benchmark problems: the Maximum Weight Independent Set (MWIS) problem and the Multidimensional Knapsack Problem (MKP). While the results demonstrate consistent improvements over standard QAOA for MWIS, only marginal gains are observed for MKP, with the advantage diminishing as the problem size increases. The reduced performance on MKP reflects the growing difficulty of training the variational mixer, likely due to increasingly challenging optimization landscapes. Overall, these findings highlight both the potential of variational Grover mixers and the trade-off between their performance gains and the additional resources required for their training.
Constrained combinatorial optimization problems are challenging for quantum computing, particularly at utility-relevant scales and on near-term hardware. At the same time, these problems are of practical significance in industry; for example, the Unit Commitment (UC) problem in energy systems involves complex operational constraints. To address this challenge, we apply copula-QAOA (cop-QAOA), a hardware-efficient approach for constrained optimization to a single-period UC that can be reduced to a one-dimensional knapsack. Cop-QAOA biases the quantum state toward feasible solutions using constant-depth mixers and appropriately biased initial states. We implement our benchmark on problem instances that are confirmed to be hard for classical solvers such as Gurobi. Our results show that cop-QAOA often finds solutions better than a lazy greedy baseline and very close to, and in some instances surpasses, those obtained by Gurobi, with only a few QAOA rounds. This work presents the largest successful demonstration of the knapsack problem on IBM Quantum hardware using up to 150 qubits, and more generally, the largest demonstration of constrained combinatorial optimization where constraints are enforced via shallow mixers.
Combinatorial optimization problems play a central role in computer science and real-world decision-making, as they aim to find the optimal solution from a large set of possibilities. Among these, the Knapsack Problem is a fundamental example with many practical applications. The Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid approach designed to address such problems. However, existing simulation approaches for QAOA applied to the Knapsack Problem do not scale well because they fail to exploit the problem's structural properties. To overcome these limitations, this study exploits the entangling characteristics of circuits in the Knapsack Problem and develops an optimized solver tailored to this setting. The key technical contributions include an entanglement-free circuit simulation method that reduces complexity from exponential to linear for non-entangling circuits, enabling 24,000x speedups for QAOA ansatz circuit simulations, and a two-phase parameter selection strategy that enhances the efficiency of finding optimal Knapsack solutions. Our solver extends the scalability of QAOA simulations from the previous limit of approximately 10 qubits to 100 qubits within a system memory of 256 GB. It achieves performance gains of over 100,000x for solving Knapsack Problems while maintaining high solution quality.
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.
Traditional methods for handling (inequality) constraints in the quantum approximate optimization (QAOA) typically rely on penalty terms and slack variables, which increase problem complexity and expand the search space. More sophisticated mixer-based QAOA variants restrict the search within the feasible assignments but often suffer from prohibitive circuit complexity. This paper presents a penalty-free formalism for incorporating inequality constraints into the cost function of QAOA using an oracle-based subroutine that evaluates constraint satisfaction in an additional register, subsequently called indicator function QAOA (IF-QAOA). Applied to the knapsack problem, we demonstrate in numerical simulations the superior performance of IF-QAOA over conventional penalty-based approaches. Using advanced QAOA simulation techniques, we find that IF-QAOA achieves significantly higher solution quality and a faster time to solution in 82% of our benchmark cases, even though circuit depth is approximately three times larger. Analysis of the scaling behavior shows favorable scaling of IF-QAOA compared to penalty-based methods. Also, benchmarks against the recently developed quantum tree generator QAOA for knapsack problems (P. Christiansen , ) demonstrated higher solution quality for circuits of similar depth. Additionally, this paper introduces a method for approximating the indicator function when the number of ancillary qubits is limited or the constraint function is noninteger. With a specialized simulation algorithm based on projective measurements, we empirically demonstrate that this formalism can encode general inequality constraints using a fixed number of ancillary qubits.
Quantum technologies have recently scaled up from laboratories into commercial applications thanks to the rapid technical developments and the growing investments in quantum computing. These developments open up the way for the emergence of the so-called noisy intermediate-scale quantum (NISQ) devices, where the quantum approximation optimization algorithms (QAOAs) represent a class of algorithms tailored for the NISQera computing for provisioning tangible quantum advantages. Meanwhile, wireless communications networks have become more complex over time and the pressure to conquer communications complexity is intense for both researchers and system designers. Specifically, a major optimization problem in this context is the resource allocation in modern communications where typically appears as an intricate 0/1 knapsack (0/1-KP) problem and finding its optimal solution using classical computers is prohibitively difficult. Thus, a parallel QAOA framework for optimizing the 0/1- KP problems is proposed in this paper. The proposal has the space complexity ofO(n)and pseudopolynomial time complexity ofO(nW), whereWis the knapsack's total capacity andnis the total number of items. However, the proposed QAOA solution is highly parallel and can be implemented onMNISQ devices of n-qubits each to obtainO(nW/M)time complexity andO(nM)space complexity. Numerical experiments show high approximation ratios even for shallow depth QAOA instances.