2019-03-18

# A quantum algorithm for minimising the effective graph resistance upon edge addition

## Publication

### Publication

*Presented at the Quantum Technology and Optimization Problems (March 2019), Munich, Germany*

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

Dürr and Høyer’s algorithm, Effective graph resistance, Graph augmentation, Quantum Inspire | |

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, 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 |