Towards Quantum-based Graph Matching for IoT Systems

Heterogeneous, large, and complex federations of Internet of Things (IoT) systems pose ever-increasing challenges to current computing paradigms. Especially the continuous changes in the system structure make planning tedious. Taking a smart city as an example, the system experiences (de-)activations of individual devices and subsystems, device roaming, the movement of people and infrastructure, and volatile traffic and communication scenarios due to mass events (e.g., concerts). It is common to abstract large Cyber-Physical System (CPS) and IoT federations, such as smart cities, logistics management systems, and large production plants, as heterogeneous graphs, whose nodes and edges can be added, altered, and removed dynamically at runtime. This dynamic adaptability requires several computational problems to be addressed, among others, the so-called graph isomorphism problem, or its generalization, the Sub-Graph Isomorphism (SGI) problem [1]. The latter refers to the task of finding occurrences of a smaller template graph in a larger target graph. The SGI problem (a.k.a. graph (pattern) matching) is known to be NP-complete.