Quantum computing has the potential to surpass the capabilities of current classical computers when solving complex problems. Combinatorial optimization has emerged as a pivotal target area for quantum computers, as problems in this field are renowned for their complexity and resource-intensive nature. Moreover, these challenges play a critical role in various industrial sectors, including logistics, manufacturing, and finance. This thesis explores the integration of quantum computation into classical software tools as a means to potentially address combinatorial optimization problems more efficiently and effectively. This work introduces QPLEX, a Python software library that enables practitioners and researchers to implement the general mathematical formulation of a given combinatorial optimization problem once and execute it seamlessly on multiple quantum devices using various quantum algorithms. This software solution automatically adapts a general optimization model to the specific instructions utilized by the target quantum device’s SDK. It offers a versatile execution workflow capable of running gate-based hybrid quantum-classical algorithms for combinatorial optimization in a platform-agnostic manner. This approach reduces the programming overhead required for modeling and experimenting with combinatorial optimization solutions. Within this manuscript, we address and introduce the various aspects associated with the development of QPLEX in a clear and comprehensive manner. These aspects encompass the quantum algorithms and quantum hardware available in the library, along with QPLEX’s system design and implementation. Additionally, we provide a guide on how to use the library and conduct a thorough evaluation of the software solution within a specific use case as part of this thesis.
Quantum computing has the potential to surpass the capabilities of current classical computers when solving complex problems. Combinatorial optimization has emerged as a pivotal target area for quantum computers, as problems in this field are renowned for their complexity and resource-intensive nature. Moreover, these challenges play a critical role in various industrial sectors, including logistics, manufacturing, and finance. This thesis explores the integration of quantum computation into classical software tools as a means to potentially address combinatorial optimization problems more efficiently and effectively. This work introduces QPLEX, a Python software library that enables practitioners and researchers to implement the general mathematical formulation of a given combinatorial optimization problem once and execute it seamlessly on multiple quantum devices using various quantum algorithms. This software solution automatically adapts a general optimization model to the specific instructions utilized by the target quantum device’s SDK. It offers a versatile execution workflow capable of running gate-based hybrid quantum-classical algorithms for combinatorial optimization in a platform-agnostic manner. This approach reduces the programming overhead required for modeling and experimenting with combinatorial optimization solutions. Within this manuscript, we address and introduce the various aspects associated with the development of QPLEX in a clear and comprehensive manner. These aspects encompass the quantum algorithms and quantum hardware available in the library, along with QPLEX’s system design and implementation. Additionally, we provide a guide on how to use the library and conduct a thorough evaluation of the software solution within a specific use case as part of this thesis.
Combinatorial optimization (CO) problems are computationally challenging as evidenced in various industry and research domains. With recent advances in quantum computing hardware and algorithms, such problems represent an excellent case study for these technologies. Nevertheless, current software tools for CO lack platform-agnostic abstractions to enable researchers and practitioners to utilize quantum resources effectively. This thesis aims to validate and extend the QPLEX Python library, a platform-agnostic CO package built on DOcplex which integrates execution across multiple quantum providers using various algorithms. We focus on two key software quality attributes: completeness, examining the quantum providers QPLEX supports to look for features that could be added to our library, enhancing its capabilities for handling CO problems; and extensibility, making the library more adaptable for future expansions. We first compile a high-level workflow for solving CO problems to ensure that our elicited software requirements align with the actual process practitioners follow when solving these problems. Subsequently, we evaluate QPLEX through a comprehensive analysis of its completeness by comparing features against alternative solutions including platform-specific SDKs, and its extensibility by examining how easily new features can be integrated without disrupting existing functionality. Based on the identified functional and non-functional requirements, we design and implement several extensions to QPLEX, including support for Qiskit Runtime Sessions, integration with D-Wave's quantum solvers and implementation of the QAOAnsatz algorithm. Furthermore, we enhance the extensibility of the library through comprehensive documentation, automated testing, and CI/CD pipelines to ensure smooth integration of future open-source contributions. Validation results demonstrate that these enhancements successfully extend QPLEX's capabilities for solving CO problems using quantum resources, providing a more comprehensive suite of features for quantum-based CO while establishing robust foundations for future development. This work contributes to the evolving field of quantum software engineering by advancing an abstraction layer that shields practitioners from low-level quantum details, allowing them to focus on problem formulation. As quantum hardware and algorithms continue to advance, such platform-agnostic libraries will play a crucial role in broadening quantum computing adoption, enabling domain experts to leverage quantum resources without requiring deep quantum computing knowledge.
Quantum computing has the potential to surpass the capabilities of current classical computers when solving complex problems. Combinatorial optimization has emerged as one of the key target areas for quantum computers as problems found in this field play a critical role in many different industrial application sectors (e.g., enhancing manufacturing operations or improving decision processes). Currently, there are different types of high-performance optimization software (e.g., ILOG CPLEX and Gurobi) that support engineers and scientists in solving optimization problems using classical computers. In order to utilize quantum resources, users require domain-specific knowledge of quantum algorithms, SDKs and libraries, which can be a limiting factor for any practitioner who wants to integrate this technology into their workflows. Our goal is to add software infrastructure to a classical optimization package so that application developers can interface with quantum platforms readily when setting up their workflows. This paper presents a tool for the seamless utilization of quantum resources through a classical interface. Our approach consists of a Python library extension that provides a backend to facilitate access to multiple quantum providers. Our pipeline enables optimization software developers to experiment with quantum resources selectively and assess performance improvements of hybrid quantum-classical optimization solutions.
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.
Optimization problems are widely encountered in real-world domains such as energy systems, financial markets, transportation networks, supply chain logistics, manufacturing processes, and e-commerce platforms. Traditional classical computing methods often struggle to solve large combinatorial optimization problems due to the exponential growth of the solution space. Quantum computing has emerged as a promising approach to address these challenges by leveraging quantum mechanical principles such as superposition and entanglement. However, current quantum hardware is limited by noise, restricted qubit availability, and scalability issues, making fully quantum solutions impractical for large-scale applications. To overcome these limitations, this research proposes a hybrid quantum–classical supercomputing framework for solving complex optimization problems across multiple domains. The framework integrates classical data processing and optimization techniques with quantum-inspired algorithms, specifically the Quantum Approximate Optimization Algorithm (QAOA), to efficiently explore large solution spaces. Real-world datasets from energy systems, supply chain logistics, financial markets, transportation networks, manufacturing processes, and e-commerce platforms are used for experimental evaluation. The results demonstrate that the hybrid optimization approach can generate higher-quality solutions and improved optimization accuracy compared to traditional classical methods. These findings highlight the potential of hybrid quantum–classical systems as an effective and scalable solution for solving complex optimization problems in modern computational applications.
Context: Quantum computing offers promising approaches to solving combinatorial optimization problems. While there are many software frameworks for these approaches, they are developed by different providers, requiring users to re-implement their problems separately in each environment to facilitate comparisons. Additionally, due to the current limitations of quantum hardware, classical solvers are often used as reference methods, further increasing implementation overhead. This lack of integration highlights the need for a unified API that seamlessly connects all approaches, enabling efficient problem formulation and comparison of different methods. Objective: This work aims to provide a research tool with a unified interface for specifying combinatorial optimization problems, selecting different solvers, managing problem hyperparameters, and standardizing the output for effortless analysis and comparison. Methods: We have developed an open-source research tool with a modular architecture that fulfills the aforementioned objective. QHyper’s design provides an independent representation of the problem along with a converter that supports various formulations compatible with available solvers. Among them are the Quantum Approximate Optimization Algorithm implemented in PennyLane, the D-Wave Advantage solver, and the Gurobi optimizer. For optimization, QHyper offers various methods, from local techniques based on gradient descent to custom global Monte Carlo methods for hyperparameter optimization. Results: QHyper’s overhead is within the statistical margin of error compared to the stand-alone use of solvers. The included illustrative example shows how to create a custom problem and easily switch between the chosen solvers. The paper also contains references to real-life scientific use cases for the presented tool. Conclusion: QHyper’s design ensures easy extensibility to new problems, solvers, and optimizers, and has proven its usefulness for several scientific use cases mentioned in the paper. With simple configuration options and easy management, such as through Jupyter Notebooks, this library can be useful for practitioners, engineers, and academics working on combinatorial optimization research.
This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. QAOA operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.