A classical graph is a set of vertices V and a set E of two element sets of vertices called edges. You can think of this as a set of points with lines connecting pairs of points. The quantum graphs I will define are actually counterparts to directed graphs.
A directed graph is a set of vertices V and a set E of ordered pairs of vertices called edges. Imagine putting arrows on all the lines in the figure described above indicating their direction. Also, edges which connect a point to itself are now allowed.
A quantum point is a vector in a complex Hilbert space whose basis vectors correspond to the vertices of a classical graph. I will denote the space of points as P and an element of P as |p). The elements of P can be thought of as quantum superpositions of vertices. A quantum point can be represented by a complex column vector by projecting onto a basis:
|p) = Sum(i) |v_i)(v_i|p) = Sum(i) p_i |v_i) where the |v_i) form an orthonormal basis for P
A co-point is an element of the dual space of P, denoted P'. An element of P' is denoted (p| and may be represented by a complex row vector.
(p| = Sum(i) (p|v_i)(v_i| = Sum(i) p_i (v_i| where the (v_i| form an orthonormal basis for P'
A quantum arrow is an element of the space P'@P. An arrow from the point p to the point q is written |q)(p|. This may also be thought of as an operator which destroys p and creates q. A quantum arrow may be represented as a complex matrix. The (i,j) element of the matrix is the amplitude for the arrow to be from point v_j to point v_i, where the v_i form an orthonormal basis for P. A general quantum arrow may be written:
A = Sum(i,j) A_ij |v_i)(v_j|
A quantum arrow usually cannot be written as a product of a co-point and a point. One can think of it as a superposition of classical directed edges of a graph. The amplitude for the arrow A to be from point p to point q is (q|A|p).
There is a natural operation multiplying arrows by points and arrows by arrows represented by ordinary matrix multiplication.
The reverse of a quantum arrow is found by taking the Hermitian conjugate of its matrix. A Hermitian arrow is one that is its own reverse. Reversal is a basis independent property of an arrow.
Another important type of arrow is a unitary arrow which is represented by a unitary matrix. A unitary arrow may be used to carry out a change of basis on the point space. The property of being unitary is also basis independent. Change of basis effected by the unitary arrow U:
Initial basis |v_i) where (v_i|v_j) = 1 if i=j, 0 otherwise Final basis |w_i) = U|v_i) for all i then (w_i|w_j) = 1 if i=j, 0 otherwise if |p) is a vector in the v basis, then U|p) is the representation of the same point in the w basis. if (p| is a row vector in the v basis, then (p|U' is the representation of the same co-point in the w basis. if A is an arrow in the v basis, then UAU' is the representation of the same arrow in the w basis.
A quantum graph is an element of the Grassmann algebra over the space of arrows. If the space of points is N dimensional, then the space of arrows is N^2 dimensional, and the space of quantum graphs is 2^(N^2) dimensional. The basis for the space of quantum graphs is the Grassmann product of a number of basis elements of the space of arrows. The Grassmann product is associative, distributive, and antisymmetric. Because of the very limited number of symbols available in HTML, I will use * for the Grassmann product.
A * B = - B * A, A * A = 0 A * (B * C) = (A * B) * C A * (B + C) = (A * B) + (A * C)
Here is a simple example of a basis for a quantum graph:
Let the basis for the point space be two dimensional
and let its basis elements be |0) and |1).
The basis for the arrow space is four dimensional
and its basis elements are:
|0)(0|, |0)(1|, |1)(0|, and |1)(1|
The basis for the graph space is 16 dimensional
and its basis elements are:
1 graph with no edges (the empty graph):
1
4 graphs with one edge:
|0)(0|, |0)(1|, |1)(0|, |1)(1|
6 graphs with two edges:
|0)(0|*|0)(1|, |0)(0|*|1)(0|, |0)(0|*|1)(1|,
|0)(1|*|1)(0|, |0)(1|*|1)(1|, |1)(0|*|1)(1|
4 graphs with three edges:
|0)(0|*|0)(1|*|1)(0|, |0)(0|*|0)(1|*|1)(1|,
|0)(0|*|1)(0|*|1)(1|, |0)(1|*|1)(0|*|1)(1|
1 graph with four edges (the complete graph):
|0)(0|*|0)(1|*|1)(0|*|1)(1|
Each basis element of the quantum graph corresponds to a classical directed graph. A general element of the Grassman algebra is a sum of basis elements times complex coefficients. Thus, a quantum graph may be thought of as a superposition of classical directed graphs. An example of a quantum graph would be:
G = 0.7 |0)(1| + 0.7i |0)(0|*|1)(1| - 0.1 |0)(1|*|1)(0|*|1)(1|
It is useful to enumerate the basis elements for points, arrows, and graphs in the following way. Suppose the point basis is N dimensional. A basis for the point space will be written v_0 = |0), v_1 = |1), ... , v_N-1 = |N-1). The N^2 basis elements of the arrow space are enumerated:
A_k = |i)(j| where k = iN+j If N = 10, then A_53 is the arrow from |3) to |5).
The 2^(N^2) basis elements of the graph space are enumerated:
G_0 = 1 G_k = A_i_1 * A_i_2 * ... * A_i_m where k = Sum(j) 2^(i_j) where i_1 < i_2 < ... < i_m For example, G_74 = A_1 * A_3 * A_6 since 2^1 + 2^3 + 2^6 = 2 + 8 + 64 = 74
In words, in G_k, the bits which are set in the binary representation of k indicate which arrows must be multiplied to form G_k. The order of factors is important since the Grassmann product is antisymmetric.
The number of arrows that must be multiplied to obtain a basis element is called the grade of that element. The empty graph 1 has grade 0.
Two quantum graphs G and H are isomorphic if there is a unitary operator U on the point space which will convert a ray of one into a ray of the other: G=cUHU' where c is complex. This corresponds to the classical concept of graph isomorphism where two graphs are isomorphic if there is a permutation of points which carries one into the other.
There is a unique natural inner product on the space of quantum graphs.
If G = Sum(i) g_i G_i and H = Sum(i) h_i G_i then (G|H) = Sum(i) g_i' h_i |G|^2 = (G|G)
The complement of a classical graph G is the graph H which contains all the edges that G does not and vice versa. I define the right complement of a basis element G_k of the graph space to be the basis element by which it must be multiplied on the right to obtain the complete graph G_M where M = 2^(N^2) - 1. This complement will be either G_M-k or -G_M-k depending on whether an even or an odd number of swaps must be performed to get the arrows into order. The left complement of a basis element is likewise defined.
G_k * G_M-k = +- G_M
The left and right complements of general elements are formed by taking the complement to be antilinear. For example:
Let N=2 so M=15. The basis elements of the graph space
are G_0, G_1, ... , G_15
Element G_0 G_1 G_2 G_3 G_4 G_5 G_6 G_7
Left Compl +G_15 -G_14 +G_13 +G_12 -G_11 -G_10 +G_9 -G_8
Right Compl +G_15 +G_14 -G_13 +G_12 +G_11 -G_10 +G_9 +G_8
Element G_8 G_9 G_10 G_11 G_12 G_13 G_14 G_15
Left Compl +G_7 +G_6 -G_5 +G_4 +G_3 -G_2 +G_1 +G_0
Right Compl -G_7 +G_6 -G_5 -G_4 +G_3 +G_2 -G_1 +G_0
Take a general graph G:
G = (5+2i) G_4 + (3-i) G_6 + (1+3i) G_9
LC(G) = (5-2i)(-G_11) + (3+i)(+G_9) + (1-3i)(+G_6)
= (-5+2i) G_11 + (3+i) G_9 + (1-3i) G_6
RC(G) = (5-2i)(+G_11) + (3+i)(+G_9) + (1-3i)(+G_6)
= (5-2i) G_11 + (3+i) G_9 + (1-3i) G_6
LC( RC(G) ) = RC( LC(G) ) = G for all graphs G.
LC(LC(LC(LC(G)))) = RC(RC(RC(RC(G)))) = G for all graphs G.
Having defined the inner product and graph complement, it is now possible to define what is meant by one graph being a subgraph of another. For classical graphs S and G, S is a subgraph of G if every edge of S is also in G. In quantum graph theory, this concept is expressed in terms of arrow creators and annihilators. For every quantum arrow there is a corresponding operator which creates that arrow. This is very simply expressed in the Grassmann algebra. The creator of arrow A applied to graph G results in G*A. If G contains A then the operation results in zero since arrows obey fermionic statistics (i.e. the algebra is anticommutative). The corresponding destructor of A applied to G is LC(LC(G)*A).
Every graph may be written as a sum of products of arrow creators applied to the empty graph. If S is the operator that creates graph S when applied to 1, then S operating on a general graph G results in G*S. Likewise, the destructor of the graph S, S', applied to G gives LC(LC(G)*S). We can find out if G contains S by attempting to delete S from G. If we attempt to delete an arrow which is not contained in G we get zero, so the magnitude of the graph which results from deleting S from G gives the probability that S is contained in G.
Assuming (G|G) = (S|S) = 1, the probability that S is a subgraph of G is ( S'G | S'G ) = ( G | SS' | G ) = ( LC(G)*S | LC(G)*S )where SS' is the number operator for S.
There is an operator which counts the number of arrows in a graph. This operator is N = Sum(i) N_A_i where the sum is over a basis for the arrow space and N_A_i is the number operator for the arrow A_i. The expected number of arrows in a graph G is
(G|N|G) = Sum(i) ( LC(G)*A_i | LC(G)*A_i )
This operator and its expectation value are invariant under unitary
transformations of the point basis. Let me demonstrate this for a
space with two arrows A and B:
E = cA - s'B F = sA + c B where c = cos(t) and s = sin(t) exp(ip) Number of arrows operator = AA' + BB' = EE' + FF' EE' + FF' = [cA - s'B][cA' - sB'] + [sA + cB][s'A' + cB'] = cc AA' - csAB' - cs'BA' + ss'BB' + ss'AA' + csAB' + cs'BA' + cc BB' = AA' + BB'
Similarly, we can count the number of any type of subgraph appearing in a graph. However, the great majority of these operators are not basis independent. Of great concern to physical models using quantum graph theory is what basis independent quantities characterize a quantum graph.
Another basis independent quantity which can be defined is the number of arrows beginning at a specified point in the graph. Rather than summing over all basis arrows, we sum over all arrows beginning at the specified point. In a similar way we can count the number of arrows in a graph converging on a specific point.
In classical graph theory we can define a distance between two graphs as the number of edges that one contains that the other does not. This is known as the Hamming distance.
dist(G,H) = cardinality( edges(G) XOR edges(H) )
We would like to extend this measure to quantum graphs. A distance
function on quantum graphs should have the following properties:
dist(G,H) = 1/2 Sum(i,j) |g_i h_j - g_j h_i|^2 dist(G_i,G_j)where dist(G_i,G_j) is defined to be the Hamming distance between these basis elements. One can define a distance operator D which operates in the space Graph@Graph (@ = tensor product) such that dist(G,H) = (G@H|D|G@H).
A vertex coloring of a classical graph is a map from the vertices of a graph to a set of colors such that adjacent vertices have different colors. The chromaticity of a graph is the fewest number of colors which can result in a valid coloring.
A coloring of a quantum graph is a linear map from the space of points to a Hilbert space of "colors": |C) = M |P). The mapping M can be represented as an m by n complex matrix where m is the dimension of the color space and n is the dimension of the point space. This map must satisfy the following constraint:
|(Q|M'M|P)|^2 (G| N[|Q)(P|] |G) ------------- + ----------------- <= 1 (Q|Q) (P|P) (G|G) for all points P and Q and is an equality for P=Q. where N[|Q)(P|] is the number operator for the arrow from P to Q. Translated into words, if the arrow from P to Q is contained in the graph G then M|P) is orthogonal to M|Q), i.e. P and Q map to different colors.The dimension of the smallest color space satisfying this constraint is the chromaticity of the graph G.
Let M be a linear map from the space of quantum arrows to elements of a Lie algebra L. M:A->L The transport from point P to point Q is defined as:
Transport[Q,P] = exp[ i M[|Q)(P|] ]which is an element of the Lie group associated with the algebra L. The transport around a plaquette PQRS is:
Transport[PQRS] = Transport[P,R]' Transport[R,S]'
Transport[S,Q] Transport[Q,P]
This forms a sort of "curvature" for the quantum graph.
Finkelstein and I have conjectured that the transport
might be defined solely in the connections of the graph
without invoking an external field.
Action[G] = Sum(PQRS) [ (G|N[PQRS]|G) |Transport[PQRS]|^2 ]
Back to Michael Gibbs' home page.