## 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: 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.

Original language | English |
---|---|

Title of host publication | Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings |

Editors | Sebastian Feld, Claudia Linnhoff-Popien |

Publisher | Springer |

Pages | 63-73 |

Number of pages | 11 |

ISBN (Electronic) | 978-3-030-14082-3 |

ISBN (Print) | 978-3-030-14081-6 |

DOIs | |

Publication status | Published - 2019 |

Event | QTOP 2019: 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 - Munich, Germany Duration: 18 Mar 2019 → 18 Mar 2019 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 11413 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | QTOP 2019: 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 |
---|---|

Country/Territory | Germany |

City | Munich |

Period | 18/03/19 → 18/03/19 |

Other | QTOP 2019 was held in conjunction with the International Conference on Networked Systems, NetSys 2019 |

### Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-careOtherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

## Keywords

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