A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition

Finn de Ridder, Niels Neumann, Thijs Veugen, Robert Kooij

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

Abstract

In this work, we consider the following problem: given a graph, the addition of which single edge minimises the effective graph resistance of the resulting (or, augmented) graph. A graph’s effective graph resistance is inversely proportional to its robustness, which means the graph augmentation problem is relevant to, in particular, applications involving the robustness and augmentation of complex networks. On a classical computer, the best known algorithm for a graph with N vertices has time complexity (Formula Presented). We show that it is possible to do better: Dürr and Høyer’s quantum algorithm solves the problem in time (Formula Presented). We conclude with a simulation of the algorithm and solve ten small instances of the graph augmentation problem on the Quantum Inspire quantum computing platform.

Original languageEnglish
Title of host publicationQuantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings
EditorsSebastian Feld, Claudia Linnhoff-Popien
PublisherSpringer
Pages63-73
Number of pages11
ISBN (Electronic)978-3-030-14082-3
ISBN (Print)978-3-030-14081-6
DOIs
Publication statusPublished - 2019
EventQTOP 2019: 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 - Munich, Germany
Duration: 18 Mar 201918 Mar 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11413 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceQTOP 2019: 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019
CountryGermany
CityMunich
Period18/03/1918/03/19
OtherQTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019

Keywords

  • Dürr and Høyer’s algorithm
  • Effective graph resistance
  • Graph augmentation
  • Quantum Inspire

Fingerprint Dive into the research topics of 'A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition'. Together they form a unique fingerprint.

Cite this