In application domains such as routing, network analysis, scheduling, and planning, directed graphs are widely used as both formal models and core data structures for the development of efficient algorithmic solutions. 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 graphs have been implemented both explicitly through adjacency matrices/lists and symbolically as ordered binary decision diagrams. Moreover, ad-hoc visit procedures have been developed to deal with dynamically evolving graphs. Quantum computation, exploiting interference and entanglement, has provided an exponential speed-up for specific problems, e.g., database search and integer factorization. In the quantum framework everything must be represented and manipulated using reversible operators. This poses a challenge when one has to deal with traversals of dynamically evolving directed graphs. Graph traversals are not intrinsically reversible because of converging paths. In the case of dynamically evolving graphs also the creation/destruction of paths comes into play against reversibility. In this paper we propose a novel high level graph representation in quantum computation supporting dynamic connectivity typical of real-world network applications. Our procedure allows to encode any multigraph into a unitary matrix. We devise algorithms for computing the encoding that are optimal in terms of time and space and we show the effectiveness of the proposal with some examples. We describe how to react to edge/node failures in constant time. Furthermore, we present two methods to perform quantum random walks taking advantage of this encoding: with and without projectors. We implement and test our encoding obtaining that the theoretical bounds for the running time are confirmed by the empirical results and providing more details on the behavior of the algorithms over graphs of different densities.

Abstract The lack of purely Quantum Programming Languages constitutes a hurdle in the general description of quantum computational processes; the implementation is heavily dependent on the considered quantum computational model. To bypass the obstacle, this paper pursues a new direction, investigating the compilation of classical programming paradigms over different quantum computational models: Gate-Based, Measurement-Based and Adiabatic Quantum Computation. Since graphs can be exploited to describe both classical and quantum computations, the problem of graph encoding on quantum hardware is tightly connected to our purposes. As such, it holds a major relevance in our quest for quantum compilation. While studying these topics through the lenses of Graph Theory, declarative programming emerges as the ideal candidate for such endeavour. In this paper we consider some existing quantum computational models and for each of them we identify the main subtleties in the compilation of classical languages. In turn, we break these complexities down into easier problems to stimulate further developments in this area of research. As it turns out, the observations for each model differ widely. Nevertheless, as for the tasks here considered, no model seems to claim supremacy over the others. In contrast, declarative programming maintains the spot as the ideal candidate for quantum compilation, independently of the model.

Advancements in Neural Networks have led to larger models, challenging implementation on embedded devices with memory, battery, and computational constraints. Consequently, network compression has flourished, offering solutions to reduce operations and parameters. However, many methods rely on heuristics, often requiring re-training for accuracy. Model reduction techniques extend beyond Neural Networks, relevant in Verification and Performance Evaluation fields. This paper bridges widely-used reduction strategies with formal concepts like lumpability, designed for analyzing Markov Chains. We propose a pruning approach based on lumpability, preserving exact behavioral outcomes without data dependence or fine-tuning. Relaxing strict quotienting method definitions enables a formal understanding of common reduction techniques.

We tackle the (classic) problem of minimizing (non)deterministic finite automata. The algorithm we put forward has the peculiarity of being incremental, i.e., the minimization proceeds by successive iterations, each producing a partially minimized automaton language-equivalent to the input one. Our algorithm builds upon Almeida et al. from 2014, fixing a minor mistake and generalizing it to the nondeterministic case. It relies on a coloring procedure of a graph associated to the automaton, keeping track of partial information. After dealing with the deterministic case, we extend this idea to the bisimulation-minimization of nondeterministic automata. The algorithms for both the deterministic and the nondeterministic cases run in time O(nm) for an automaton with n states and m transitions. The complexity for the deterministic case matches the complexity claimed by Almeida et al.. The nondeterministic case improves the fastest known incremental algorithm for this problem. We conclude introducing and using a notion of signature of a state, whose aim is to exploit pre-computed information potentially available, to speed-up the process. A signature is used to produce an initial partition of the automaton's states and can be easily integrated in both the incremental and the non-incremental algorithm.