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

Finn de Ridder; Niels Neumann; Thijs Veugen; Robert Kooij

doi:10.1007/978-3-030-14082-3_6

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

Finn de Ridder^*
, Niels Neumann
, Thijs Veugen
, Robert Kooij

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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
Subtitle of host publication	First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings
Editors	Sebastian Feld, Claudia Linnhoff-Popien
Place of Publication	Cham
Publisher	Springer
Pages	63-73
Number of pages	11
ISBN (Electronic)	978-3-030-14082-3
ISBN (Print)	978-3-030-14081-6
DOIs	https://doi.org/10.1007/978-3-030-14082-3_6
Publication status	Published - 2019
Externally published	Yes
Event	1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 - Munich, Germany Duration: 18 Mar 2019 → 18 Mar 2019 Conference number: 1

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11413
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019
Abbreviated title	QTOP 2019
Country/Territory	Germany
City	Munich
Period	18/03/19 → 18/03/19
Other	was held in conjunction with the International Conference on Networked Systems, NetSys 2019

Keywords

Dürr and Høyer’s algorithm
Effective graph resistance
Graph augmentation
Quantum Inspire
n/a OA procedure

Access to Document

10.1007/978-3-030-14082-3_6

Cite this

de Ridder, F., Neumann, N., Veugen, T., & Kooij, R. (2019). A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition. In S. Feld, & C. Linnhoff-Popien (Eds.), Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings (pp. 63-73). (Lecture Notes in Computer Science; Vol. 11413). Springer. https://doi.org/10.1007/978-3-030-14082-3_6

de Ridder, Finn ; Neumann, Niels ; Veugen, Thijs et al. / A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition. Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings. editor / Sebastian Feld ; Claudia Linnhoff-Popien. Cham : Springer, 2019. pp. 63-73 (Lecture Notes in Computer Science).

@inproceedings{d374f3b52c314d8cb68a7eaa71428363,

title = "A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition",

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{\textquoteright}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{\"u}rr and H{\o}yer{\textquoteright}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.",

keywords = "D{\"u}rr and H{\o}yer{\textquoteright}s algorithm, Effective graph resistance, Graph augmentation, Quantum Inspire, n/a OA procedure",

author = "\{de Ridder\}, Finn and Niels Neumann and Thijs Veugen and Robert Kooij",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 , QTOP 2019 ; Conference date: 18-03-2019 Through 18-03-2019",

year = "2019",

doi = "10.1007/978-3-030-14082-3\_6",

language = "English",

isbn = "978-3-030-14081-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "63--73",

editor = "Sebastian Feld and Claudia Linnhoff-Popien",

booktitle = "Quantum Technology and Optimization Problems",

address = "Germany",

}

de Ridder, F, Neumann, N, Veugen, T & Kooij, R 2019, A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition. in S Feld & C Linnhoff-Popien (eds), Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11413, Springer, Cham, pp. 63-73, 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019 , Munich, Germany, 18/03/19. https://doi.org/10.1007/978-3-030-14082-3_6

A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition. / de Ridder, Finn; Neumann, Niels; Veugen, Thijs et al.
Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings. ed. / Sebastian Feld; Claudia Linnhoff-Popien. Cham: Springer, 2019. p. 63-73 (Lecture Notes in Computer Science; Vol. 11413).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - de Ridder, Finn

AU - Neumann, Niels

AU - Veugen, Thijs

AU - Kooij, Robert

N1 - Conference code: 1

PY - 2019

Y1 - 2019

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

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

KW - Dürr and Høyer’s algorithm

KW - Effective graph resistance

KW - Graph augmentation

KW - Quantum Inspire

KW - n/a OA procedure

UR - https://www.scopus.com/pages/publications/85064057227

U2 - 10.1007/978-3-030-14082-3_6

DO - 10.1007/978-3-030-14082-3_6

M3 - Conference contribution

AN - SCOPUS:85064057227

SN - 978-3-030-14081-6

T3 - Lecture Notes in Computer Science

SP - 63

EP - 73

BT - Quantum Technology and Optimization Problems

A2 - Feld, Sebastian

A2 - Linnhoff-Popien, Claudia

PB - Springer

CY - Cham

T2 - 1st International Workshop on Quantum Technology and Optimization Problems, QTOP 2019

Y2 - 18 March 2019 through 18 March 2019

ER -

de Ridder F, Neumann N, Veugen T, Kooij R. A Quantum Algorithm for Minimising the Effective Graph Resistance upon Edge Addition. In Feld S, Linnhoff-Popien C, editors, Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings. Cham: Springer. 2019. p. 63-73. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-14082-3_6

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

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this