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

A Measurement-based Algorithm for Graph Colouring

Epping, Michael and Stollenwerk, Tobias (2021) A Measurement-based Algorithm for Graph Colouring. Quantum. Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften. ISSN 2521-327X. (Submitted)

[img] PDF - Preprint version (submitted draft)


We present a novel algorithmic approach to find a proper vertex colouring of a graph with d colours, if it exists. We associate a d-dimensional quantum system with each vertex and the initial state is a mixture of all possible colourings, from which we obtain a random proper colouring of the graph by measurements. The non-deterministic nature of the quantum measurement is tackled by a reset operation, which can revert the effect of unwanted projections. As in the classical case, we find that the runtime scales exponentially with the number of vertices. However, we provide numerical evidence that the average runtime for random graphs scales polynomially in the number of edges.

Item URL in elib:https://elib.dlr.de/148460/
Document Type:Article
Title:A Measurement-based Algorithm for Graph Colouring
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Epping, MichaelMichael.Epping (at) dlr.dehttps://orcid.org/0000-0003-0950-6801
Stollenwerk, TobiasTobias.Stollenwerk (at) dlr.dehttps://orcid.org/0000-0001-5445-8082
Journal or Publication Title:Quantum
Refereed publication:No
Open Access:Yes
Gold Open Access:Yes
In ISI Web of Science:Yes
Publisher:Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
Keywords:Algorithmus, Graphfärbung, Quantenalgorithmus
HGF - Research field:other
HGF - Program:other
HGF - Program Themes:other
DLR - Research area:Digitalisation
DLR - Program:D - no assignment
DLR - Research theme (Project):D - EQUATE
Location: Köln-Porz
Institutes and Institutions:Institute for Software Technology
Deposited By: Epping, Michael
Deposited On:14 Feb 2022 10:08
Last Modified:14 Feb 2022 10:08

Repository Staff Only: item control page

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