A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition

Conference paper (2019)

Authors

Finn de Ridder Radboud Universiteit Nijmegen
Thijs Veugen TNO, Centrum Wiskunde & Informatica (CWI)
Robert Kooij Network Architectures and Services - EEMCS , Singapore University of Technology and Design
Research Group
Network Architectures and Services (EEMCS) (TU Delft)
Copyright: © 2019 Finn de Ridder, Niels Neumann, Thijs Veugen, Robert Kooij
DOI: https://doi.org/10.1007/978-3-030-14082-3_6
More Info
expand_more

Published Date

2019

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Quantum & Computer Engineering

Research Group

Network Architectures and Services

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.

Files

Ridder2019_Chapter_AQuantumAlg... (pdf)
(pdf | 0.814 Mb)
- Embargo expired in 29-11-2021