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.

Dürr and Høyer’s algorithm, Effective graph resistance, Graph augmentation, Quantum Inspire
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