Posted on 7th July 2023
Continuing from the last post I want to now consider the Quantum Chromatic Number of a graph. These ideas arose from Quantum Information Theory, which explore how quantum entanglement can be used in certain two-person "games", which are very similar to Interactive proof systems. While the motivation can be a little hard to explain, the resulting mathematical formalism is straightforward.
Definition: A quantum \( c \)-colouring of \( G \) is a collection of orthogonal projections \( \{P_{v,k} : v\in V_G, k\in [c] \} \) on some Hilbert space \( H \) (usually assumed finite-dimensional) such that:
- \( \sum_{k=1}^c P_{v,k} = 1_H \) for each \( v \);
- \( P_{v,k} P_{w,k} = 0 \) for each \( k \) and each edge \( v\sim w \) in \( G \).
There is a more complicated (but motivated) definition in [Cameron et al.] (see references below) where the reduction to this definition is essentially shown Proposition 1 and the later observations. It is also shown there that, when \( H \) is finite dimensional, we can always assume that each projection has the same rank (though this is sometimes not natural.) The following is the same spectral bound which we discussed before, but now for the quantum chromatic number \( \chi_q(G) \), the least \( c \) for which \( G \) has a quantum \( c \)-colouring.
Theorem: [Elphick-Wocjan] \( \chi_q(G) \geq 1+\frac{\lambda_1}{-\lambda_n} \).
Given a classical colouring \( f:V\rightarrow [c] \) we take \( H=\mathbb C \), so projections on \( H \) are just the numbers \( 0,1 \), and then set \( P_{v,k}=1 \) if and only if \( k=f(v) \). Condition (1) is obvious, and (2) holds if and only if \( f(v)\not=f(w) \) for \( v\sim w \), that is, we really do have a vertex-colouring.
Of course, here each \( P_{v,k} \) does not have the same rank. To fix this, we consider the "Fourier matrix" \( F_c \) which has \( (j,k) \) entry \( e^{2\pi ijk/c} \). Given \( f:V\rightarrow [c] \) define a map \( \phi': V\rightarrow\mathbb C^c \) by setting \( \xi'(v) \) to be the \( f(v) \) row of \( F_c \). That is, \[ \phi'(v) = \sum_{k=1}^c e^{2\pi i f(v)k/c} e_k. \] Notice that \( (\phi'(v)|\phi'(w))=0 \) when \( v\sim w \), and that if all \( c \) colours are used then the span of \( \{ \phi'(v) : v\in V_G \} \) is all of \( \mathbb C^c \). This final point follows because the rows of \( F_c \) form an orthogonal basis of \( \mathbb C^c \).
Definition: An orthogonal representation of \( G \) is a map \( \phi:V_G\rightarrow H \) for some (finite-dimensional) Hilbert space \( H \) such that \( \phi(v)\not=0 \) for each \( v \), and \( \phi(v) \perp \phi(w) \) for each edge \( v\sim w \). Let \( \xi(G) \) be the smallest dimension of \( H \) supporting such a map.
Let \( \xi'(G) \) be the smallest dimension of \( H \) for which there exists a map \( \phi':V_G\rightarrow H \) with the additional property that the modulus of each entry of \( \phi'(v) \) is constant (which could then be normalised to be \( 1 \) if we wished).
Clearly \( \xi(G) \leq \xi'(G) \) and we've just shown that \( \xi'(G) \leq \chi(G) \). Given such a \( \phi':V\rightarrow\mathbb C^c \), say with each entry having \( |\phi'(v)_l|=1 \), we defined a quantum \( c \)-colouring via setting \[ \phi'_{v,k} = \sum_{l=1}^c \phi'(v)_l e^{2\pi ilk/c} e_l \in \mathbb C^c, \] and then defining \( P_{v,k} \) to be the orthogonal projection onto the (one-dimensional) span of \( \phi'_{v,k} \). As \[ (\phi'_{v,k}|\phi'_{v,k'}) = \sum_{l=1}^c e^{-2\pi ilk/c} |\phi'(v)_l|^2 e^{2\pi ilk'/c} = \sum_{l=1}^c e^{2\pi il(k'-k)/c} = c\delta_{k,k'} \] it follows that \( (\phi'_{v,k})_{k=1}^c \) is a family of \( c \) orthogonal vectors in \( \mathbb C^c \), and hence a basis. So \( \sum_k P_{v,k} = 1 \). Given \( v\sim w \), we similarly compute that \[ (\phi'_{v,k}|\phi'_{w,k}) = \sum_{l=1}^c e^{-2\pi ilk/c} \overline{\phi'(v)_l} \phi'(w)_l e^{2\pi ilk/c} = (\phi'(v)|\phi'(w)) = 0, \] and so \( P_{v,k} P_{w,k} = 0 \). Hence \( (P_{v,k}) \) is a quantum \( c \)-colouring, with the additional property that each projection has rank one.
Definition: Let \( \chi_q^{(r)}(G) \) be the smallest \( c \) for which there exists a quantum \( c \)-colouring of \( G \), with the additional property that each projection has rank equal to \( r \).
We have just shown that \( \chi_q^{(1)}(G) \leq \xi'(G) \), and obviously \( \chi_q(G) \leq \chi_q^{(1)}(G) \). Given a quantum \( c \)-colouring \( (P_{v,k}) \) such that each projection has rank one, notice that as \( \sum_k P_{v,k} = 1_H \), the Hilbert space must have dimensional \( c \) and so be (isomorphic to) \( \mathbb C^c \). Let \( P_{v,k} \) have range spanned by the unit vector \( \phi_{v,k} \in \mathbb C^c \). Define \( \phi:V\rightarrow\mathbb C^c \) by \( \phi(v) = \phi_{v,1} \). Then, given \( v\sim w \), we have that \[ ( \phi(v) | \phi(w) ) = ( \phi_{v,1} | \phi_{w,1} ) = 0 \] as \( P_{v,1} P_{w,1} = 0 \). So \( \phi \) is an orthogonal representation, and we see that \( \xi(G) \leq \chi_q^{(1)}(G) \).
We have just summarised some arguments from [Cameron et al]. Now let's look at spectral bounds.
The previous post discussed Pinchings and Twirlings. Given a quantum \( c \)-colouring \( (P_{v,k}) \) on a Hilbert space \( H \), for each \( k \) define \[ P_k = \sum_{v\in V} e_v e_v^* \otimes P_{v,k} \in \mathbb M_n \otimes \mathcal B(H), \] were \( e_v e_v^* \) is the rank-one projection onto the span of the \( v^{\text{th}} \) coordinate, that is, the diagonal matrix with a \( 1 \) in the \( (v,v) \) position. Recall that \( A=A_G \) is the adjacency matrix of \( G \).
Lemma: The \( (P_k) \) are mutually orthogonal projections which sum to \( 1 \). The associated pinching \( \mathcal C \) satisfies that \( \mathcal C(A\otimes 1_H) = 0 \) and \( \mathcal C(D\otimes 1_H) = D\otimes 1_H \) for any diagonal matrix \( D \).
Proof: We simply calculate that \[ \sum_k P_k = \sum_v e_ve_v^* \otimes \sum_k P_{v,k} = \sum_v e_ve_v^* \otimes 1_H = 1, \] which implies that the \( (P_k) \) are orthogonal. For any matrix \( M \) the pinching is \[ \mathcal C(M\otimes 1_H) = \sum_k P_k (M\otimes 1_H) P_k = \sum_{u,v\in V} e_u e_u^* M e_v e_v^* \otimes \sum_{k} P_{v,k} P_{u,k}, \] where \( e_u^* M e_v = M_{u,v} \). As \( A_{u,v}=1 \implies u\sim v \implies P_{u,k} P_{v,k}=0 \) it follows that \( \mathcal C(A\otimes 1_H)=0 \). If \( M \) is diagonal, then \[ \mathcal C(M\otimes 1_H) = \sum_u M_{u,u} e_u e_u^* \otimes \sum_k P_{u,k}^2 = M\otimes 1_H. \]
We now simply copy the proof from before: let \( \mathcal D(\cdot) = c^{-1} \sum_k U^k (\cdot) (U^*)^k \) be the twirling associated to this pinching, so that \( \mathcal D(A\otimes 1_H)=0 \) and so \[ A\otimes 1_H = \sum_{k=1}^{c-1} U^k (-A\otimes 1_H) (U^*)^k. \] For example, to show the Hoffman bound for the quantum chromatic number, let \( \xi \) be a unit vector associated to the maximal eigenvalue \( \lambda_1 \), and let \( \xi_0\in H \) be any unit vector. As \( (U^*)^k(\xi\otimes\xi_0) \) is a unit vector, and \( (\xi\otimes\xi_0| (A\otimes 1_H)\xi\otimes\xi_0) = \lambda_1 \), we see that \( \lambda_1 \leq (c-1) \sigma(-A\otimes 1_H) \) where \( \sigma(\cdot) \) denotes the spectral radius of the self-adjoint operator \( -A\otimes 1_H \). As the spectrum of \( -A\otimes 1_H \) agrees with the spectrum of \( -A \), we again conclude that \( \lambda_1 \leq (c-1)(-\lambda_n) \) and hence \( \chi_q(G) \geq 1 + \frac{\lambda_1}{-\lambda_n} \).
I want to finish with a conjecture of Elphick. Let \( s^+(G) = \sum \{ \lambda_i^2 : \lambda_i > 0 \} \) and \( s^-(G) = \sum \{ \lambda_i^2 : \lambda_i < 0 \} \). Notice that \( s^+(G) + s^-(G) = \sum_i \lambda_i^2 = \operatorname{Tr}(A^2) = 2|E_G| \) because the \( (v,v) \) entry of \( A^2 \) counts the number of \( u \) with \( A_{u,v}=1 \), that is, the number of neighbours of \( v \).
Conjecture (Elphick, Farber, Goldberg, Wocjan): Let \( G \) be connected. Then \( |V_G|-1 \leq \min(s^+(G), s^-(G) ) \).
To my in-expert eye, this seems of a different character to the bounds on the chromatic number which we have been discussing. There is no real property of \( G \) occuring in this conjecture: we could fix \( n = |V| \) and then to verify the conjecture, we essentially need to find the minimal value of \( \min(s^+(G), s^-(G) ) \) for all graphs on \( n \) vertices.
Liu, Lele Liu; Ning, Bo "Unsolved Problems in Spectral Graph Theory" arXiv:2305.10290 [math.CO]
Elphick, Clive; Wocjan, Pawel Spectral lower bounds for the quantum chromatic number of a graph. J. Comb. Theory, Ser. A 168, 338-347 (2019). Zbl 1421.05042
Elphick, Clive; Farber, Miriam; Goldberg, Felix; Wocjan, Pawel "Conjectured bounds for the sum of squares of positive eigenvalues of a graph." Discrete Math. 339, No. 9, 2215-2223 (2016). Zbl 1339.05228
Cameron, Peter J.; Montanaro, Ashley; Newman, Michael W.; Severini, Simone; Winter, Andreas On the quantum chromatic number of a graph. Electron. J. Comb. 14, No. 1, Research Paper R81, 15 p. (2007). Zbl 1182.05054