Abstracts-QO-EN

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

Evaluating Metaheuristic Optimization Methods for Quantum Reinforcement Learning

Abstract:

Quantum Reinforcement Learning offers the potential for advantages over classical Reinforcement Learning, such as a more compact representation of the state space through quantum states. Furthermore, theoretical studies suggest that Quantum Reinforcement Learning can exhibit faster convergence than classical approaches in certain scenarios. However, further research is needed to validate the actual benefits of Quantum Reinforcement Learning in practical applications. This technology also faces challenges such as a flat solution landscape, characterized by missing or low gradients, which makes the application of traditional, gradient-based optimization methods inefficient. In this context, it is necessary to examine gradient-free algorithms as an alternative. The present work focuses on the integration of metaheuristic optimization algorithms such as Particle Swarm Optimization, Ant Colony Optimization, Tabu Search, Simulated Annealing, and Harmony Search into Quantum Reinforcement Learning. These algorithms offer flexibility and efficiency in parameter optimization, as they utilize specialized search strategies and adaptability. The approaches are evaluated within two Reinforcement Learning environments and compared to random action selection. The results show that in the MiniGrid environment, all algorithms lead to acceptable or even very good results, with Simulated Annealing and Particle Swarm Optimization achieving the best performance. In the Cart Pole environment, Simulated Annealing and Particle Swarm Optimization achieve optimal results, while Ant Colony Optimization, Tabu Search, and Harmony Search perform only slightly better than an algorithm with random action selection. These results demonstrate the potential of metaheuristic optimization methods such as Particle Swarm Optimization and Simulated Annealing for efficient learning in Quantum Reinforcement Learning systems, but also highlight the need for careful selection and adaptation of the algorithm to the specific problem.

Author:

Daniel Seidl

Advisors:

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

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

Finding Arbitrage with different Quantum Algorithms

Abstract:

Quantum computing, a discipline that leverages the principles of quantum physics to perform complex calculations, has emerged as a transformative field since its initial conceptualization by Richard Feynman and Yuri Manin in the 1980s. Recent advancements in quantum hardware, coupled with a surge in investment, have accelerated the application of quantum computing across a diverse range of sectors with one of them being finance. Financial operations often boil down to combinatoric optimization problems, which makes them are well suited to quantum methods. Specifically, this work focuses on identifying optimal arbitrage opportunities in financial markets, such as currency exchange. Arbitrage can be framed as a combinatorial optimization problem, solvable through quantum annealing or quantum gate-based computing methods.
Building on the foundation laid by Gili Rosenberg, this work explores the efficacy of quantum annealing and conducts comprehensive benchmarks against other quantum algorithms, such as the Quantum Approximate Optimization Algorithm (QAOA). Also a novel oracle encoding enhanced by Quantum Fourier Transformation (QFT) to solve the arbitrage problem using Grover’s algorithm is introduced. Recognizing that the number of qubits and the size of the quantum circuit are among today’s major computational bottlenecks, recently established pre-processing and post-processing techniques are employed to optimize computational efficiency across the various quantum algorithms studied.

(This research was produced in cooperation with Aqarios GmbH)

Author:

Jakob Anton Mayer

Advisors:

Jonas Nüßlein, Jonas Stein, Nico Kraus, Claudia Linnhoff-Popien

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