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

Network Architectures and Services

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

30 Downloads (Pure)

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	https://doi.org/10.1007/978-3-030-14082-3_6
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-care
Otherwise 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

Access to Document

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

Ridder2019_Chapter_AQuantumAlgorithmForMinimisingFinal published version, 695 KB

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 - 1st International Workshop, QTOP 2019, Proceedings (pp. 63-73). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11413 LNCS). 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 - 1st International Workshop, QTOP 2019, Proceedings. editor / Sebastian Feld ; Claudia Linnhoff-Popien. Springer, 2019. pp. 63-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6eddf8da9b2e4c6a8d4909e72ff0f2dc,

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

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

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise 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. ; QTOP 2019: 1st International Workshop on Quantum Technology and Optimization Problems, 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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "63--73",

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

booktitle = "Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings",

}

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 - 1st International Workshop, QTOP 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11413 LNCS, Springer, pp. 63-73, QTOP 2019: 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 - 1st International Workshop, QTOP 2019, Proceedings. ed. / Sebastian Feld; Claudia Linnhoff-Popien. Springer, 2019. p. 63-73 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11413 LNCS).

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › 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 - 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-care Otherwise 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.

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

UR - http://www.scopus.com/inward/record.url?scp=85064057227&partnerID=8YFLogxK

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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 63

EP - 73

BT - Quantum Technology and Optimization Problems - 1st International Workshop, QTOP 2019, Proceedings

A2 - Feld, Sebastian

A2 - Linnhoff-Popien, Claudia

PB - Springer

T2 - QTOP 2019: 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 - 1st International Workshop, QTOP 2019, Proceedings. Springer. 2019. p. 63-73. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). 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

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this