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:

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