Abstracts-QO-EN

Leveraging Preconditioning to Speed Up Quantum Simulation-Based Optimization

Abstract:

Simulation-based optimization is computationally intensive requiring many evaluations of complex simulations to optimize an objective function. Quantum algorithms can provide a better runtime over classical methods by simultaneously evaluating multiple possible solutions. If the objective function and/or constraints depend on the summary statistic information derived from the result of a simulation, the problem is classified as a Quantum Simulation-Based Optimization (QuSO) problem. A subclass of QuSO is LinQuSO, where the simulation component can be formulated as a system of linear equations. The calculation of the objective function depends on the complexity of solving the corresponding linear system of equations, which is linear influenced by the condition number of the system. A recent paper introduced a quantum algorithm for solving prototypical second-order linear elliptic partial differential equations, which are discretized by 𝑑-linear finite elements on Cartesian grids within a bounded 𝑑-dimensional domain. By using a BPX preconditioner the system of linear equations is transformed into a well-conditioned one. Functionals of the solution can be computed for a given tolerance 𝜀 with a complexity of 𝒪(︀polylog (︀𝜀−1)︀)︀ and a quantum advantage over classical solvers is accomplished for 𝑑 > 1. This work shows how to improve the efficiency of computing optimal input parameters for a LinQuSO problem by inserting the preconditioning algorithm into the Quantum Approximate Optimization Algorithm (QAOA), which results in a runtime of 𝒪(︀𝜀−1 polylog (︀𝜀−1)︀)︀ for the simulation component. The new approach is demonstrated with an example of a topology optimization problem for heat conduction.

Author:

Carlotta von L’Estocq

Advisors:

Jonas Stein, David Bucher, Claudia Linnhoff-Popien

Student Thesis | Published January 2025 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

Warm Starting Variational Quantum Algorithms for Parameterized Combinatorial Optimization

Abstract:

In the Noisy Intermediate Scale era of Quantum Computing (NISQ), Variational Quantum Algorithms (VQAs) are a key paradigm for producing useful results in spite of hardware limitations. These algorithms can be adapted to multiple domains, such as condensed matter physics and combinatorial optimization. Problems in these domains can be modeled as Ising Hamiltonians. To model physical systems, Hamiltonians usually contain parameters controlling global forces, such as magnetic fields. In contrast, Hamiltonians modeling combinatorial optimization problems (COPs) are usually not parametrized in the literature, describing a specific problem instance. However, in reality, multiple global variables, such as the time of the day or the direction of the market, can influence instances of COPs. This thesis introduces parametrized Hamiltonians for combinatorial optimization through the Maximum-Cut and Knapsack problems, presenting a framework that can be extended to other COPs. The framework widens current approaches for modeling COPs to describe multiple problem instances using a single Hamiltonian with global parameters. Subsequently, this work investigates the optimization of parametrized COPs using various variants of VQAs, testing alternative objective functions tailored specifically for COPs. Finally, this work investigates the transfer of optimized parameters between problem instances corresponding to different Hamiltonian parameter values, evaluating whether parameters producing satisfactory solutions for one configuration of a problem can produce similar results for different configurations. Two simple modifications to existing techniques are presented for this task, termed Adaptive Start and Aggregated Learning. This thesis presents a different approach to combinatorial optimization and investigates the potential of this new framework.

Author:

Federico Harjes Ruiloba

Advisors:

Tobias Rohe, Jonas Stein, Claudia Linnhoff-Popien

Student Thesis | Published December 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

Circuit Partitioning and Genetic Optimization for Efficient Qubit Distribution in Distributed Quantum Computing

Abstract:

Quantum computers are capable of solving specific computational problems in a time frame that is faster than that of a classical computer. The current era is that of Noisy Intermediate-Scale Quantum Computing, which is defined by the presence of noise that limits the capabilities of quantum computation. This presents a significant challenge in the development of large-scale quantum computers. The encoding of problems is accomplished through the use of quantum circuits comprising qubits. The distribution of qubits across quantum computers may facilitate the execution of larger circuits. In Distributed Quantum Computing, qubits are distributed across multiple Quantum Processing Units, which are connected via a quantum network. Alternatively, large quantum circuits can be run using circuit partitioning, which reduces depth and allows for parallel execution. However, partitioning a circuit might not take the constraints of the network into account. A method for integrating network constraints into the distribution process is through the use of an evolutionary algorithm. This approach has been employed to improve the distribution of qubits on a quantum network, albeit to a limited extent. The objective of this study is to consider the distinctive characteristics of a network and, moreover, the particular costs associated with each operation. To evaluate the efficiency of our algorithm, we conducted experiments on two distinct network topologies and compared the results to three baselines. The results demonstrate that our approach exhibits superior performance in the distribution of circuits across diverse topologies when compared to the established baselines.

Author:

Simon Schlichting

Advisors:

Leo Sünkel, Maximilian Zorn, Claudia Linnhoff-Popien

Student Thesis | Published December 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

Evaluating Mutation Techniques in Genetic Algorithm-Based Quantum Circuit Synthesis

Abstract:

Quantum computing has the potential to solve complex problems that are intractable for classical computers, while serving as a cornerstone of next-generation systems offering extreme computational power. This capability arises from the unique properties of qubits and quantum parallelism, allowing quantum computers to perform certain calculations much faster than classical counterparts.
The optimization of quantum circuits is essential for advancing quantum computing, particularly for noisy intermediate-scale quantum (NISQ) devices. These devices face significant challenges due to their limited number of qubits and high error rates, making efficient circuit synthesis critical. Genetic algorithms (GAs) have emerged as a promising solution for optimizing quantum circuits by automating a task that is otherwise manually solved in an inefficient manner.
This thesis investigates the impact of various mutation strategies within a GA frame- work for quantum circuit synthesis. Mutations interact at the most fundamental level of a circuit and can significantly influence overall performance. Collecting data on how these mutations transform circuits and determining which strategies are most efficient is a key step in developing a robust GA optimizer for quantum synthesis.
The experiments conducted in this research employed a fitness function primarily based on fidelity, while also considering circuit depth and the number of T operations. The experiments focused on optimizing four to six qubit circuits with extensive hyperparameter testing to identify optimal solutions for practical quantum computing. The results indicate that the combination of delete and swap strategies, without employing change or add strategies, provided the best performance under the given constraints.

Author:

Tom Bintener

Advisors:

Michael Kölle, Maximilian Zorn, Thomas Gabor, Claudia Linnhoff-Popien

Student Thesis | Published December 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

State Preparation on Quantum Hardware Using an Island Genetic Algorithm

Abstract:

As genetic algorithms demonstrate a remarkable versatility and extensive range of applications, their utilisation in the context of quantum circuit synthesis remains a notable area of interest. Given the considerable challenge presented by the vast search space inherent to quantum circuit generation, the theoretical suitability of genetic algorithms is evident, particularly in view of their intrinsic exploration capability. In addition to the utilisation of quantum algorithms for the attainment of up to exponential runtime advantages, all such algorithms necessitate the preparation of specific states in order to confer said advantages. It is therefore crucial to be able to create specific states, even in the absence of knowledge regarding the underlying circuits. One notable state is the Greenberger–Horne–Zeilinger (GHZ) state, which unites the superposition and entanglement characteristics inherent to quantum computing. Accordingly, this circuit is used as the target state for reproduction in this thesis, and two additional circuits with distinctive states are employed to illustrate the general applicability of this approach. Additionally, the genetic algorithm is executed not only on the simulator but also on the IONQ Aria-1 quantum processing unit (QPU).

This thesis elucidates the distinctions between the population-based and the island-based approach. These approaches differ in terms of whether the individuals are part of a single population or whether they develop separately into smaller groups dispersed across multiple islands and interact with each other solely through a process of migration between the islands. This thesis presents evidence of the superiority of the island-based approach in comparison to the population-based approach for the GHZ-state, as well as the two other circuits. Moreover, it demonstrates that the constraints of the hardware execution could be met by employing the island-based approach on the IONQ Aria-1 QPU to generate a solution candidate for the GHZ-state. Furthermore, the provenance of the generated solution candidates indicates the efficacy of the genetic algorithm itself and also the enhanced diversity of the different approaches.

Author:

Jonathan Philip Wulf

Advisors:

Jonas Stein, Maximilian Zorn, Claudia Linnhoff-Popien

Student Thesis | Published October 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

Explainable Time Series Forecasting using exogenous variables – How weather affects the stock market

Abstract:

Climate Change is real, and this has been affecting the weather all around the world. With weather conditions changing, this thesis aims to understand how weather can be used to forecast market changes over a longer term. The aim is to understand how the ability to forecast weather can help mitigate risk during acute weather crises and disruptions, and help arbitrage the industries most affected by weather in order to stabilize the market. Modern Deep learning methods such as Temporal Fusion Transformers (TFTs) and Neural Hierarchical Interpolation for Time Series Forecasting (N-HiTS) are needed to allow the inclusion of static and historical exogenous variables such as weather and location data. We therefore, use the existing state-of-the-art N-HiTS architecture, as it outperforms other models in long-horizon forecasting by incorporating hierarchical interpolation and multi-rate data sampling techniques and provides a large average accuracy improvement over the latest Transformer architectures while reducing the computation time by order of magnitude. We then modify this existing architecture by developing a novel approach that integrates weather data in the model, so that it performs better for stock data and weather covariates. We call this novel approach WiN-HiTs, Weather induced N-HiTS, and show that weather covariates can help forecast the market movements better for certain sectors like Utilities and Materials over a long forecast horizon.

This research also emphasizes on the importance of forecast decomposition in AI models, particularly in a financial and stock market context where understanding the decision-making process is crucial. The WiN-HiTS architecture allows the separation of the stack prediction components of the time series forecast, which helps us interpret how different weather factors contribute to stock price fluctuations, and how these factors are chosen. In this thesis, we use a diverse set of test data for evaluation, including historical weather and stock market data from multiple geographic locations and industries across the S&P500 stocks. Baselines for comparison include traditional models such as Auto ARIMA, as well as modern machine learning approaches like Transformer-based models (TFT) and N-HiTS itself, and results show, that WiN-HiTS performs on par for most sectors, and better than these models in certain sectors. Key Performance Indicators (KPIs) used for benchmarking include Mean Absolute Error (MAE), Mean Squared Error (MSE), and Mean Absolute Percentage Error (MAPE) to assess prediction accuracy. The evaluation of this thesis ensures the robustness and practicality of the proposed WiN-HiTS model in real-world financial forecasting scenarios.

Author:

Het Dave

Advisors:

Claudia Linnhoff-Popien, Jonas Stein, Arnold Unterauer, Nico Kraus

Student Thesis | Published September 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

A Path Towards Quantum Advantage for the Unit Commitment Problem

Abstract:

This work presents a solution to the unit commitment problem (UCP) in energy grid management, an optimization problem that involves solving a system of equations to calculate costs for a given solution. We characterize the UCP as a Mixed-Integer Nonlinear Programming (MINLP) problem and solve it using a quantum simulation-based optimization (QuSO) approach, defining a class of equivalent problems solvable with the proposed algorithm. By modeling the energy grid as a specific graph, we gain valuable insights into the structure and characteristics of the susceptance matrix. We also incorporate approximate Direct Current (DC) power flow constraints into the model. The proposed quantum routine begins by inverting the reduced susceptance matrix via Quantum Singular Value Transformation (QSVT) using a specific matrix inversion polynomial. A quantum phase estimation routine, along with an additional QSVT procedure, is used to construct the cost function, which is then optimized using the Quantum Approximate Optimization Algorithm (QAOA). This hybrid quantum-classical approach leverages the computational power of quantum algorithms to enhance efficiency in solving such optimization problems. Our results evaluate the algorithm’s complexity and demonstrate its significant potential for QuSO problems. Specifically, the QSVT matrix inversion can reduce time complexity exponentially in scenarios where classical methods scale poorly with problem size. This reduction in complexity could enable real-time optimization of large-scale energy grids, thereby improving operational efficiency and reliability.

Author:

David Fischer

Advisors:

Claudia Linnhoff-Popien, Dirk André Deckert, Jonas Stein, Jago Silberbauer, Philipp Altmann

Student Thesis | Published September 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors

Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games

Abstract:

Switching to 100 % renewable energy production is one of the most important steps societies are currently taking in combating the climate crisis. This switch however requires new techniques for the management of power networks, such as their division into micro-grids containing sensible subsets of prosumers. Creating this division in an optimal manner is a challenging optimization problem which can be simplified to the Coalition Structure Generation problem in Induced Subgraph Games. This is a problem formulation in which one seeks to divide an undirected, fully-connected, weighted graph into a set of fully-connected subgraphs, in a manner that maximizes the sum over the weights of the edges contained in these subgraphs. In the last few years, several Quantum Annealing (QA)-based approaches have been proposed to solve this problem, the most recent of which is an efficient, but greedy algorithm called GCS-Q. In this thesis, we propose many different, less greedy QA-based approaches to solving the above-mentioned problem, to see if any of these algorithms can outperform GCS-Q in terms of solution quality. Testing these approaches on three different solvers – the QBSolv software, the D-Wave Advantage 4.1 quantum annealer and the QAOA algorithm using qiskit’s simulation software – we find that, while none of our suggested approaches can outperform the quantum state- of-the-art algorithm on current QA hardware, most of them do when using the QBSolv software. The best of these approaches is an algorithm we call 4-split iterative R-QUBO, which finds the optimum for all problem graphs in our dataset and scales quite favorably with the graph size in terms of runtime. Thus, we see this algorithm as a promising candidate for future research on quantum approaches for the problem in question.

Author:

Daniëlle Schuman

Advisors:

Jonas Nüßlein, David Bucher, Claudia Linnhoff-Popien

Student Thesis | Published May 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors