Print Email Facebook Twitter A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition Title A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition Author de Ridder, F. Neumann, N.M.P. Veugen, P.J.M. Kooij, R. Contributor Linnhoff-Popien, S. (editor) Feld, C. (editor) Publication year 2019 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: Durr 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. © 2019, Springer Nature Switzerland AG. Subject Durr and Høyer’s algorithmEffective graph resistanceGraph augmentationQuantum InspireOptimizationQuantum computersQuantum theorySimulation platformBest-known algorithmsFollowing problemGraph augmentationQuantum algorithmsQuantum InspireS-algorithmsTime complexityComplex networks To reference this document use: http://resolver.tudelft.nl/uuid:ec8767f6-88a1-48c4-bf88-a618a8e406d8 TNO identifier 866718 Publisher Springer Verlag ISBN 9783030140816 ISSN 3029-743 Source Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019, 18 March 2019 through 18 March 2019, 63-73 Document type conference paper Files To receive the publication files, please send an e-mail request to TNO Library.