Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Knapsack: Optimizing Resource Allocation with QAOA

Mahfouz, Zein, Bhaskaran Potty Thulasi Lakshmi, Sreedevi

Published Nov 17, 2025• 0 citations
Publisher

Abstract

Combinatorial Optimization (CO) is one of the most important areas in the field of optimization, with practical applications found in every industry, including both the private and public sectors. In recent years, it was discovered that a mathematical formulation known as QUBO (Quadratic Unconstrained Binary Optimization) problem can embrace an exceptional variety of important CO problems found in the industry. In this work, we explore the Quantum Approximate Optimization Algorithm (QAOA) as a quantum computing approach to solve the Knapsack Problem efficiently by formulating the problem as a QUBO model. Here we implemented QAOA on a quantum emulator, leveraging quantum superposition and entanglement to explore multiple solutions simultaneously. The method offers a promising route for solving large, complex scheduling and resource allocation problems that are tough for classical algorithms, with potential applications in logistics, HPC resource scheduling, and energy optimization.

DOI
10.5281/zenodo.17516187

Related papers

Quantum Computing For Combinatorial Optimization: Algorithms, Complexity Analysis, And Real-World Applications.

G. Swapna, P. Sunil

Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.

•Jan 1, 2026•0 citations

Resource-efficient QUBO formulations for the Knapsack and Bin Packing problem

Pim van den Heuvel

Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.

•Jan 1, 2025•0 citations

Quantum Optimization for Airline Itinerary and Scheduling: A QUBO and QAOA Approach

Vaibhav V. Khedekar

Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.

•Apr 22, 2025•0 citations

Quantum Approaches to the 0/1 Multi-Knapsack Problem: QUBO Formulation, Penalty Parameter Characterization and Analysis

Evren Güney, Joachim C.F. Ehrenthal, Thomas Hanne

The 0/1 Multi-Knapsack Problem (MKP) is a combinatorial optimization problem with applications in lo gistics, finance, and resource management. Advances in quantum computing have enabled the exploration of problems like the 0/1 MKP through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work develops QUBO formulations for the 0/1 MKP, with a focus on optimizing penalty parameters for encoding constraints. Using simulation experiments across quantum platforms, we evaluate the feasibility of solving small-scale instances of the 0/1 MKP. The results provide insights into the challenges and opportuni ties associated with applying quantum optimization methods for constrained resource allocation problems. © 2025 by SCITEPRESS– Science and Technology Publications, Lda.

International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2025•1 citation

Two-Step QAOA: Enhancing Quantum Optimization by Decomposing K-hot Constraints in QUBO Formulations

Yuichiro Minato

The Quantum Approximate Optimization Algorithm (QAOA) has shown promise in solving combinatorial optimization problems by leveraging quantum computational power. We propose a simple approach, the Two-Step QAOA, which aims to improve the effectiveness of QAOA by decomposing problems with k-hot encoding QUBO (Quadratic Unconstrained Binary Optimization) formulations. By identifying and separating the problem into two stages, we transform soft constraints into hard constraints, simplifying the generation of initial conditions and enabling more efficient optimization. The method is particularly beneficial for tackling complex societal problems that often involve intricate constraint structures.

arXiv:2408.05383•Aug 9, 2024•0 citations

Simulations of Quantum Approximate Optimization Algorithm on HPC-QC Integrated Systems

Seongmin Kim, In‐Saeng Suh

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising tool for accelerating optimization processes in the Noisy Intermediate-Scale Quantum (NISQ) era. Compared to classical methods, QAOA efficiently solves optimization problems, often formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. Classical quantum simulators are crucial for evaluating quantum algorithms due to limited quantum resources. However, QAOA's performance can vary with different simulation methods. This study analyzes QAOA's performance using various quantum simulators (e.g., density _matrix, statevector, and matrix_product_state) and demonstrates the benefits of HPC-QC integrated systems in solving QUBO problems on an active learning workflow. By simulating QAOA on dense, large-matrix QUBO problems, we evaluate accuracy and problem-solving time. We also assess QAOA's performance on local computers and HPC-QC inte-grated systems, using Oak Ridge Leadership Computing Facility (OLCF)'s Frontier supercomputer with local Qiskit Aer and remote IBM Quantum simulators.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•3 citations
Combinatorial Optimization (CO) is one of the most important areas in the field of optimization, with practical applications found in every industry, including both the private and public sectors. In recent years, it was discovered that a mathematical formulation known as QUBO (Quadratic Unconstrained Binary Optimization) problem can embrace an exceptional variety of important CO problems found in the industry. In this work, we explore the Quantum Approximate Optimization Algorithm (QAOA) as a quantum computing approach to solve the Knapsack Problem efficiently by formulating the problem as a QUBO model. Here we implemented QAOA on a quantum emulator, leveraging quantum superposition and entanglement to explore multiple solutions simultaneously. The method offers a promising route for solving large, complex scheduling and resource allocation problems that are tough for classical algorithms, with potential applications in logistics, HPC resource scheduling, and energy optimization.
Combinatorial optimization problems play a vital role in computer science and engineering, with applications in logistics, network design, finance, and resource allocation. However, many of these problems are NP-hard, making them computationally expensive to solve using classical optimization techniques, especially for large-scale instances. In recent years, quantum computing has emerged as a promising paradigm capable of addressing these limitations by leveraging quantum mechanical principles such as superposition and entanglement. This study investigates the application of quantum computing for solving combinatorial optimization problems, with a focus on algorithm design, complexity analysis, and real-world applicability. The research primarily employs the Quantum Approximate Optimization Algorithm (QAOA) and Grover's search algorithm to solve representative problems such as Max-Cut and the Knapsack problem. The performance of these algorithms is evaluated using key metrics including accuracy, execution time, and approximation ratio, and is compared with classical optimization techniques. The results demonstrate that QAOA is capable of generating near-optimal solutions, achieving accuracy levels of up to 93% for small problem instances. However, the study also highlights the challenges associated with current quantum systems, including noise, limited qubit availability, and increased execution time. Comparative analysis reveals that while classical methods remain more efficient for small-scale problems, quantum algorithms show significant potential for scalability and handling complex optimization tasks. The findings suggest that hybrid quantum-classical approaches offer a practical solution in the current Noisy Intermediate-Scale Quantum (NISQ) era. The study concludes that although quantum computing is still evolving, it holds strong potential for transforming combinatorial optimization in the future.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Abstract Airline itinerary and scheduling represent some of the most difficult computational problems that exist in transportation. The problems require choosing the best flight routes while determining schedules and allocating resources through various constraints which include regulatory requirements and maintenance schedules and dynamic demand patterns. The solution of small and medium-scale instances has been achieved through mixed-integer programming and heuristic methods including simulated annealing and genetic algorithms and branch-and-price but these methods become impractical for larger real-world instances due to exponential scaling issues. Quantum computing has introduced fresh solutions which enable the resolution of these problems. Quantum mechanical phenomena particularly superposition and entanglement enable optimization algorithms to examine an exponentially expanded solution space simultaneously. Our research applies a basic airline scheduling problem to the Traveling Salesman Problem (TSP) before converting it into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The Quantum Approximate Optimization Algorithm (QAOA) serves as a hybrid quantum-classical method to solve this formulation. The experimental evaluation of a 4-city scenario shows that quantum-based optimization generates performance levels comparable to traditional methods and indicates that improved quantum hardware development will provide computational benefits for complex airline scheduling problems. This research holds dual importance because it can minimize operational expenses and improve scheduling performance and it establishes fundamental principles for complex combinatorial problem optimization across the transportation industry. The research establishes fundamental principles for quantum-enabled applications that will revolutionize airline operations and other transportation networks by solving critical scalability and solution quality problems.
The 0/1 Multi-Knapsack Problem (MKP) is a combinatorial optimization problem with applications in lo gistics, finance, and resource management. Advances in quantum computing have enabled the exploration of problems like the 0/1 MKP through Quadratic Unconstrained Binary Optimization (QUBO) formulations. This work develops QUBO formulations for the 0/1 MKP, with a focus on optimizing penalty parameters for encoding constraints. Using simulation experiments across quantum platforms, we evaluate the feasibility of solving small-scale instances of the 0/1 MKP. The results provide insights into the challenges and opportuni ties associated with applying quantum optimization methods for constrained resource allocation problems. © 2025 by SCITEPRESS– Science and Technology Publications, Lda.
The Quantum Approximate Optimization Algorithm (QAOA) has shown promise in solving combinatorial optimization problems by leveraging quantum computational power. We propose a simple approach, the Two-Step QAOA, which aims to improve the effectiveness of QAOA by decomposing problems with k-hot encoding QUBO (Quadratic Unconstrained Binary Optimization) formulations. By identifying and separating the problem into two stages, we transform soft constraints into hard constraints, simplifying the generation of initial conditions and enabling more efficient optimization. The method is particularly beneficial for tackling complex societal problems that often involve intricate constraint structures.
The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising tool for accelerating optimization processes in the Noisy Intermediate-Scale Quantum (NISQ) era. Compared to classical methods, QAOA efficiently solves optimization problems, often formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. Classical quantum simulators are crucial for evaluating quantum algorithms due to limited quantum resources. However, QAOA's performance can vary with different simulation methods. This study analyzes QAOA's performance using various quantum simulators (e.g., density _matrix, statevector, and matrix_product_state) and demonstrates the benefits of HPC-QC integrated systems in solving QUBO problems on an active learning workflow. By simulating QAOA on dense, large-matrix QUBO problems, we evaluate accuracy and problem-solving time. We also assess QAOA's performance on local computers and HPC-QC inte-grated systems, using Oak Ridge Leadership Computing Facility (OLCF)'s Frontier supercomputer with local Qiskit Aer and remote IBM Quantum simulators.