Faithful orthogonal representations of graphs from partition logics

For nonboolean logics, it is not immediately evident which probability measures should be chosen. The answer is already implicit in Zierler and Schlessinger’s 1965 paper on “Boolean embeddings of orthomodular sets and quantum logic”. Theorem 0 of Kochen and Specker’s 1967 paper (Kochen and Specker 1967) states that separability by dispersion-free states (of image \(2^1={0,1}\)) for every pair of atoms of the lattice is a necessary and sufficient criterion for a homomorphic embedding into some “larger” Boolean algebra. In 1978, Wright explicitly stated (Ron 1978, p. 272) “that every urn weight is “classical,” i.e., in the convex hull of the dispersion-free weights.” In the graph theoretical context Grötschel, Lovász and Schrijver have discussed the vertex packing polytopeVP(G) of a graph G, defined as the convex hull of incidence vectors of independent sets of nodes (Grötschel et al. 1986). This author has employed dispersion-free weights for hull computations on the Specker bug (Svozil 2001) and other (partition) logics supporting a separating set of two-valued states.

Hull computations based on the pentagon (modulo pentagon/pentagram graph isomorphisms) can be found in Refs. Klyachko et al. (2008), Bub and Stairs (2009, 2010), Badzia̧g et al. (2011) (for a survey see Svozil 2018, Section 12.9.8.3). The Bub and Stairs inequality (Bub and Stairs 2009, Equation (10), p. 697) can be directly read off from the partition logic  (2), as depicted in Fig. 1b, which in turn are the cumulated indices of the nonzero dispersion-free weights on the atoms: the sum of the convex hull of the dispersion-free weights on the 5 intertwining atoms (the “vertices” of the pentagon diagram) represented by the subsets \(\{1,2,3\} \), \(\{ 6,8,10\}\), \(\{ 3,5,9\} \), \(\{ 2,7,8\} \), \(\{ 4,5,6\} \) of \({{\mathscr {S}}}_{11}\) is

Motivated by cryptographic issues outside quantum theory, (Lovász 1979) has proposed an “indexing” of vertices of a graph by vectors reflecting their adjacency: the graph-theoretic definition of a faithful orthogonal representation of a graph is by identifying vertices with vectors (of some Hilbert space of dimension d) such that any pair of vectors are orthogonal if and only if their vertices are not orthogonal (Lovász et al. 1989; Parsons and Pisanski 1989). For physical applications (Cabello et al. 2010; Solís-Encina and Portillo 2015) and others have used an “inverse” notation, in which vectors are required to be mutually orthogonal whenever they are adjacent. Both notations are equivalent by exchanging graphs with their complements or inverses.

There is no systematic algorithm to compute the minimal dimension for a faithful orthogonal representation of a graph. Lovász (1979), Cabello et al. (2013) gave a (relative to entropy measures (Haemers 1979) “optimal” vector representation of the pentagon graph depicted in Fig. 1b in three dimensions [\(L_{12}\) depicted in Fig. 1a is a sublogic thereof]: modulo pentagon/pentagram graph isomorphisms which in two-line notation is \(\begin{pmatrix} 1&{}2&{}3&{}4&{}5\\ 1&{}4&{}2&{}5&{}3 \end{pmatrix}\) and in cycle notation is (1)(2453); its set of five intertwining vertices \(\{v_1,\ldots ,v_5\}=\{u_1,u_3,u_5,u_2,u_4\}\) are represented by the three-dimensional unit vectors (the five vectors corresponding to the “inner” vertices/atoms can be found by a Gram–Schmidt process)which, by preparing the “(umbrella) handle” state vector \(\begin{pmatrix} 1,0,0 \end{pmatrix} \), turns out to render the maximal (Bub and Stairs 2009; Badzia̧g et al. 2011) quantum-bound \(\sum _{j=1}^5 \vert \langle c\vert u_l \rangle \vert ^2 =\sqrt{5}\), which exceeds the “classical” bound (3) of 2 from the computation of the convex hull of the dispersion-free weights.

Based on Lovász’s vector representation by graphs, Grötschel, Lovász and Schrijver have proposed (Grötschel et al. 1986, Section 3) a Gleason–Born type probability measure (Cabello 2019) which results in convex sets different from polyhedra defined via convex hulls of vectors discussed earlier in Sect. 2.1. Essentially their probability measure is based upon m-dimensional faithful orthogonal representations of a graph G whose vertices \(v_i\) are represented by unit vectors \(\vert v_i\rangle \) which are orthogonal within, and nonorthogonal outside, of cliques/contexts. Every vertex \(v_i\) of the graph G, represented by the unit vector \(\vert v_i\rangle \), can then be associated with a “probability” with respect to some unit “preparation” (state) vector \(\vert c\rangle \) by defining this “probability” to be the absolute square of the inner product of \(\vert v_i\rangle \) and \(\vert c\rangle \), that is, by \(P(c,v_i)=\left| \langle c \vert v_i\rangle \right| ^2\). Iff the vector representation (in the sense of Cabello–Portillo) of G is faithful, the Pythagorean theorem assures that, within every clique/context of G, probabilities are positive and additive, and (as both \(\vert v_i\rangle \) and \(\vert c\rangle \) are normalized) the sum of probabilities on that context adds up to exactly one, that is, \(\sum _{i \in \text {clique/context}} P(c,v_i)=1\). Thereby, probabilities and expectations of simultaneously co-measurable observables, represented by graph vertices within cliques or contexts, obey Specker’s exclusivity principle and “behave classically.” It might be challenging to motivate “quantum type” probabilities and their convex expansion, the theta body (Grötschel et al. 1986), by the very assumptions such as exclusivity (Cabello et al. 2014; Cabello 2019).

A very similar measure on the closed subspaces of Hilbert space, satisfying Specker’s exclusivity principle and additivity, had been proposed by Gleason Gleason (1957), first and second paragraphs, p. 885: “A measure on the closed subspaces means a function\(\mu \)which assigns to every closed subspace a nonnegative real number such that if\(\{A_i\}\)is a countable collection of mutually orthogonal subspaces having closed linear spanB, then\(\mu (B) = \sum _i \mu (A_i)\). It is easy to see that such a measure can be obtained by selecting a vectorvand, for each closed subspaceA, taking\(\mu (A)\)as the square of the norm of the projection ofvonA.” Gleason’s derivation of the quantum mechanical Born rule (Born 1926, Footnote 1, Anmerkung bei der Korrektur, p. 865) operates in dimensions higher than two and allows also mixed states, that is, outcomes of nonideal measurements. However, mixed states can always be “completed” or “purified” (Nielsen and Chuang 2010, Section 2.5, pp. 109–111) (and thus outcomes of nonideal measurements made ideal Cabello 2019) by the inclusion of auxiliary dimensions.

Wrights generalized urn model (Ron 1978; Wright 1990), in a nutshell, is the observation of black balls, on which multiple colored symbols are painted, with monochromatic filters in only one of those colors. Complementarity manifests itself in the necessity of choice of the particular color one observes: one may thereby obtain knowledge of the information encoded in this color, but thereby invariable loses messages encoded in different colors. A typical example is the logic \(L_{12}\) encoded by the partition logic enumerated in (1) and depicted in Fig. 1(a): suppose that there are 4 ball types and two colors on black backgrounds:Suppose an urn is loaded with balls of all four types. Suppose further that an agent’s task is to draw one ball from the urn and, by observing this ball, to find which type it is. Of course, if the observer is allowed to look at both colors simultaneously, this would allow to single out exactly one ball type. But that maximal resolution can no longer be maintained in experiments restricted to one of the two colors. Any one of such two experiment varieties could resolve different, complementary properties: looking at the drawn ball with orange glasses, the agent is able to resolve between balls (i) of type 1 associated with the symbol a; (ii) of type 2 associated with the symbol b; and (iii) of type 3 or 4 associated with the symbol c. The resolution between type 3 and 4 balls is lost. Alternatively, by looking at the drawn ball with blue glasses the agent is able to resolve between balls (i) of type 1 associated with the symbol a; (ii) of type 3 associated with the symbol b; and (iii) of type 2 or 4 associated with the symbol c, that is, for the color blue the resolution between type 2 and 4 balls is lost. In any case, the state of ball type is partitioned in different ways, depending on the color of the filter. (Similar considerations apply for initial state identification problems on finite automata.)

Tables 1 and 2 enumerate a relational encoding among two or more colors not dissimilar to Peres’ detonating bomb model (Peres 1978). Suppose that an urn is loaded with balls of the type occurring in subensemble \(E_6\) of Table 1. The observation of some symbol \(s\in \{0,1\}\) in green implies the (counterfactual) observation of the same symbol s in red, and vice versa. Table 2 is just an extension to two colors per observer, and an urn loaded with subensembles \((E_6)^2\). Agent Alice draws a ball from the urn and looks at it with her red (exclusive) or blue filters. Then, Alice hands the ball over to Bob. Agent Bob looks at the ball with his green (exclusive) or orange filters. This latter scenario is similar to a Clauser–Horne–Shimony–Holt scenario of the Einstein–Podolsky–Rosen type, except that the former is totally local and its probabilities derived from the convex hull of the dispersion-free weights can never violate classical bounds, whereas the latter one may be (and hopefully is) nonlocal, and its performance with a quantum resource violates the classical bounds.