TY - GEN

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

AU - de Ridder, Finn

AU - Neumann, Niels

AU - Veugen, Thijs

AU - Kooij, Robert

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Dürr and Høyer’s algorithm

KW - Effective graph resistance

KW - Graph augmentation

KW - Quantum Inspire

UR - http://www.scopus.com/inward/record.url?scp=85064057227&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14082-3_6

DO - 10.1007/978-3-030-14082-3_6

M3 - Conference contribution

AN - SCOPUS:85064057227

SN - 978-3-030-14081-6

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 63

EP - 73

BT - Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings

A2 - Feld, Sebastian

A2 - Linnhoff-Popien, Claudia

PB - Springer

T2 - QTOP 2019: 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019

Y2 - 18 March 2019 through 18 March 2019

ER -