elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Compilation Algorithms for Gate-Based Quantum Computing

Timme, Paul (2021) Compilation Algorithms for Gate-Based Quantum Computing. Master's, Rheinische Friedrich-Wilhelms-Universität Bonn.

[img] PDF - Only accessible within DLR
750kB

Abstract

This thesis addresses the compilation of quantum circuits by swap gate insertion, a process in which a series of quantum gates, is to be made executable on a given device by manipulating its storage pattern. Utilizing results by Even and Miltzow et al. we find an abstract linear programming formulation of sequential quantum compilation approximately minimizing the compilation effort on lattice quantum architectures for a broad class of quantum circuits. The linear program is polynomial-time solvable and its solution can be used to extract feasible compilations at polylogarithmic overhead in total gate count by adaption of results on high-dimensional embeddings and random projections by Feige and Vempala. A method of Rotter and Vygen can be applied to improve the approximation ratio under the assumption of a conjecture on optimal solutions for periodic boundary conditions. For a general parallel model of quantum compilation we find that attaining similar approximations reduces to the choice of an appropriate gate execution order, applying results by Demaine et al. on parallel motion planning. Furthermore two locally optimal compilation heuristics are presented and their performance tested on benchmarks from Tan and Cong's optimality study of existing quantum computing layout synthesis tools.

Item URL in elib:https://elib.dlr.de/146962/
Document Type:Thesis (Master's)
Additional Information:Betreut von: Dr. Tobias Stollenwerk korrigierte Version
Title:Compilation Algorithms for Gate-Based Quantum Computing
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Timme, PaulUNSPECIFIEDUNSPECIFIED
Date:14 July 2021
Refereed publication:No
Open Access:No
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Number of Pages:53
Status:Published
Keywords:Gate-based quantum computing, compilation, quantum circuit, swap gate
Institution:Rheinische Friedrich-Wilhelms-Universität Bonn
Department:Mathematisch-Naturwissenschaftliche Fakultät
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Quantum computing
Location: Köln-Porz
Institutes and Institutions:Institute for Software Technology > High-Performance Computing
Institute for Software Technology
Deposited By: Lobe, Elisabeth
Deposited On:13 Dec 2021 09:09
Last Modified:13 Dec 2021 09:09

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.