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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
