Graphs are one of the most common data structures in classical computer science and graph theory has been widely used in complexity and computability. Recently, the use of graphs in application domains such as routing, network analysis and resource allocation has become crucial. In these areas, graphs are often evolving in time: for example, connection links may fail due to temporary technical issues, meaning that edges of the graph cannot be traversed for some time interval and alternative paths have to be followed. In classical computation, where graphs are represented as adjacency matrices or lists, these problems are well studied and ad-hoc visit procedures have been developed. For specific problems quantum computation, through superpositions and entanglement has provided faster algorithms than their classical counterpart. However, in this model, only reversible operations are allowed and this poses the quest of augmenting a graph in order to be able to reverse edge traversals. In this paper we present a novel graph representation in quantum computation supporting dynamic connectivity typical of real-world network applications. Our proposal has the advantage of being closer than others in literature to the adjacency matrix of the graph. This makes easy dynamic edge-failure modeling. We introduce optimal algorithms for computing our graph encoding and we show the effectiveness of our proposal with some examples.

Della Giustina, D., Piazza, C., Riccardi, B., Romanello, R. (2022). Directed Graph Encoding in Quantum Computing Supporting Edge-Failures. In Reversible Computation 14th International Conference, RC 2022, Urbino, Italy, July 5–6, 2022, Proceedings (pp.75-92). Springer [10.1007/978-3-031-09005-9_6].

Directed Graph Encoding in Quantum Computing Supporting Edge-Failures

Riccardi B.;
2022

Abstract

Graphs are one of the most common data structures in classical computer science and graph theory has been widely used in complexity and computability. Recently, the use of graphs in application domains such as routing, network analysis and resource allocation has become crucial. In these areas, graphs are often evolving in time: for example, connection links may fail due to temporary technical issues, meaning that edges of the graph cannot be traversed for some time interval and alternative paths have to be followed. In classical computation, where graphs are represented as adjacency matrices or lists, these problems are well studied and ad-hoc visit procedures have been developed. For specific problems quantum computation, through superpositions and entanglement has provided faster algorithms than their classical counterpart. However, in this model, only reversible operations are allowed and this poses the quest of augmenting a graph in order to be able to reverse edge traversals. In this paper we present a novel graph representation in quantum computation supporting dynamic connectivity typical of real-world network applications. Our proposal has the advantage of being closer than others in literature to the adjacency matrix of the graph. This makes easy dynamic edge-failure modeling. We introduce optimal algorithms for computing our graph encoding and we show the effectiveness of our proposal with some examples.
paper
Edge-failure; Graphs; Quantum walks;
English
14th International Conference on Reversible Computation, RC 2022 - 5 July 2022 through 6 July 2022
2022
Mezzina, CA; Podlaski, K
Reversible Computation 14th International Conference, RC 2022, Urbino, Italy, July 5–6, 2022, Proceedings
9783031090042
2022
13354 LNCS
75
92
none
Della Giustina, D., Piazza, C., Riccardi, B., Romanello, R. (2022). Directed Graph Encoding in Quantum Computing Supporting Edge-Failures. In Reversible Computation 14th International Conference, RC 2022, Urbino, Italy, July 5–6, 2022, Proceedings (pp.75-92). Springer [10.1007/978-3-031-09005-9_6].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/447040
Citazioni
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 1
Social impact