2019-03-18
A quantum algorithm for minimising the effective graph resistance upon edge addition
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1007/978-3-030-14082-3_6 | |
| Lecture Notes in Computer Science | |
| Quantum Technology and Optimization Problems | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
de Ridder, F., Neumann, N., Veugen, T., & Kooij, R. (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 |
|
