On quantum superpositions of graphs, no-signalling and covariance

We provide a mathematically and conceptually robust notion of quantum superpositions of graphs. We argue that, crucially, quantum superpositions of graphs require node names for their correct alignment, which we demonstrate through a no-signalling argument. Nevertheless, node names are a fiducial construct, serving a similar purpose to the labelling of points through a choice of coordinates in continuous space. Graph renamings, aka isomorphisms, are understood as a change of coordinates on the graph and correspond to a natively discrete analogue of continuous diffeomorphisms. We postulate renaming invariance as a symmetry principle in discrete topology of similar weight to diffeomorphism invariance in the continuous. We explain how to impose renaming invariance at the level of quantum superpositions of graphs, in a way that still allows us to talk about an observable centred at a specific node.