August 2023

a:3:{s:6:"locale";s:5:"en_US";s:3:"rtl";i:0;s:9:"flag_code";s:2:"us";}
Application of graph partitioning algorithms and genetic algorithms to optimize teleportation costs in distributed quantum circuits.

Application of graph partitioning algorithms and genetic algorithms to optimize teleportation costs in distributed quantum circuits.

Abstract:

Currently, we are in the Noisy Intermediate Scale Quantum (NISQ) era, where the number of qubits that can be used in a single quantum computer is increasing. However, with this development come challenges in handling large quantum systems. Distributed quantum computation is therefore gaining importance to overcome these challenges. In this process, multiple quantum computers or quantum processing units are connected to work together on a problem. This enables the use of larger computational capacities and more efficient solutions to complex tasks. In distributed quantum computing, different units or subsystems communicate with each other to exchange quantum information. The basic teleportation protocol plays an important role in this process. It enables the transfer of quantum information between subsystems. An important aspect is to minimize the number of teleportations. Thus, the aim is to increase the accuracy of quantum computations, reduce the error-proneness of qubits, and at the same time make resource consumption more efficient.In this work, different graph partitioning algorithms, such as the Kernighan-Lin algorithm and spectral partitioning, a genetic algorithm (GA), and two hybrid genetic algorithms (HGA), which are a combination of the graph partitioning algorithms and a GA, are applied and investigated to minimize the number of global quantum gates and the associated teleportation costs. First, the graph partitioning algorithms are used to partition the nodes as uniformly as possible. In addition, a GA is implemented to take care of the partitioning of qubits using random partitions. The two HGAs lead to a near-optimal arrangement of the global quantum gates after the qubits are partitioned using the graph partitioning algorithms. Finally, the proposed approaches are investigated using nine benchmark circuits and compared in terms of the number of global quantum gates and teleportation costs. Random searches are also performed for the GA and the two HGAs to verify their performance with respect to the optimization objective. The results indicate a significant improvement in teleportation cost.

Author:

Teodor Slaveykov

Advisors:

Leo Sünkel Thomas Gabor, Claudia Linnhoff-Popien

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


NISQ-ready community detection on weighted graphs using separation-node identification

NISQ-ready community detection on weighted graphs using separation-node identification

Abstract:

An important optimization problem in computer science is the detection of communities. By analyzing networks, so-called communities can be found and important information in many fields – from biology to social structures – can be derived. By weighting individual edges, even more information can be processed than by the mere presence of these edges. However, for community detection on weighted graphs, more factors must be considered as a result. Since this is an NP-hard optimization problem, heuristics are often used to find an acceptable solution faster and more efficiently. One promising approach is the use of quantum computers, as it has already been experimentally shown that they can achieve more efficient results than classical computers in certain domains (e.g., Grover or Shor algorithm). However, since most approaches to community detection using QUBO matrices consume a lot of memory, the goal of this work is to find an approach with a good memory efficiency. To this end, this work presents a promising community detection approach based on the detection and analysis of separation nodes, which has the advantage that the dimensions of the resulting QUBO matrix do not exceed the number of nodes and the matrix itself is as sparse as the adjacency matrix of the graph. These separating nodes are designed to divide the graph when they are removed such that the remaining components are each exactly part of a community. This approach is extended to weighted graphs by determining the probability that an edge is a separating edge based on the information flow of the neighborhood. This approach is tested using synthesized graphs with a fixed ground truth about their communities, to which weights are assigned without changing the community structure.

Translated with www.DeepL.com/Translator (free version)

Author:

Dominik Ott

Advisors:

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

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


Influence of Embedding-Methods on the Generalization of Quantum Machine Learning

Influence of Embedding-Methods on the Generalization of Quantum Machine Learning

Abstract:

Quantum Machine Learning is a promising field of application for quantum computers. However, to see real advantages over classical computers, advanced quantum fundamentals are needed. One of the building blocks of quantum computers are embeddings, which convert real data into quantum data. In this work, the focus is on the influence of various embedding methods on the ”quality” of a Quantum Machine Learning model. As the focus is on these embeddings, the model and quantum circuit are kept simple. They solve a binary classification problem. Nevertheless, the interplay of certain embeddings with different circuits is also of interest and is briefly discussed in this work. Since much already exists in the literature about the embedding methods ”Angle Embedding” and ”Amplitude Embedding”, this work also focuses on other embedding methods from the literature. To determine the quality of a model, we examined its generalizability. For this, we used various metrics from classical Machine Learning. Although the question of the best embedding could not be answered, interesting insights were gained about the effects of the embeddings on different datasets.

Author:

Steffen Brandenburg

Advisors:

Einfluss von Embedding Methoden auf Generalisierbarkeit in Quantum Machine Learning

Leo Sünkel, Thomas Gabor, Claudia Linnhoff-Popien

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