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.

, , ,
doi.org/10.1007/978-3-030-14082-3_6
Lecture Notes in Computer Science
Quantum Technology and Optimization Problems
Centrum Wiskunde & Informatica, Amsterdam, The Netherlands

de Ridder, F, Neumann, N.M.P, Veugen, P.J.M, & Kooij, R.E. (2019). A quantum algorithm for minimising the effective graph resistance upon edge addition. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence (pp. 63–73). doi:10.1007/978-3-030-14082-3_6