On quantum superpositions of graphs, no-signalling and covariance

Abstract We provide a mathematically and conceptually robust notion of quantum superpositions of graphs. The formalism may be useful for the purpose of modelling a ‘fully quantum internet’ and states of geometry in quantum gravity. We argue that quantum superpositions of graphs do require node names for their correct alignment, which we demonstrate through a no-signalling argument. The need for node names was often overlooked or disagreed upon in previous proposals. Still, node names should remain 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. We explain how to impose renaming invariance at the level of operators over quantum superpositions of graphs, in a way that still allows us to talk about local operators.