nonlocal games (see Remark \[rem:quantumhomMancinska\]) and have been the subject of intensive study in their various forms [@Mancinska2016; @Scarpa2012; @Avis2006; @Cameron2007; @Paulsen2015; @Paulsen2016; @Roberson2016]. Quantum graph isomorphisms are originally due to Atserias et al [@Atserias2016] (see Remark \[rem:Atseriasquantumiso\]).

A related $C^*$-algebraic approach to quantum homomorphisms between classical graphs was recently discovered by Ortiz and Paulsen [@Ortiz2016]. They define a $C^*$-algebra which is essentially an internal hom, analogous to the algebra of quantum functions in Remark \[rem:quantumfunctionalgebra\].

Our notion of reflexive quantum graph coincides with that of Kuperberg and Weaver [@Kuperberg2012; @Weaver2015; @Weaver2010] (see Remark \[rem:literatureqgraph\] and Theorem \[thm:relationadjacency\]) and in particular generalises Duan, Severini and Winter’s noncommutative graphs [@Duan2013] (see Proposition \[prop:quantumgraphDuanthesame\]). Quantum graph homomorphisms between noncommutative graphs can be understood as pure versions of Stahlke’s entanglement-assisted morphisms [@Stahlke2016] (see Remark \[rem:stahlkegraphhoms\]).

#### Categorical quantum mechanics (CQM).

Our work emerges from the CQM research programme, initiated by Abramsky and Coecke [@Abramsky2008] and developed by them and others [@Coecke2008; @Coecke2007; @Coecke2009; @Vicary2010; @Coecke2014], which uses the graphical calculus of monoidal categories to provide a high-level syntax for quantum information flow. In particular, Vicary’s reformulation of the theory of finite-dimensional $C^*$-algebras in terms of Frobenius algebras [@Vicary2010] and Coecke, Pavlovi[ć]{} and Vicary’s 