Please post topics for discussion in the comments section below.
Focused research group on noncommutative mathematics and quantum information
University of Bristol, August 8-10 2019
Focused research group on noncommutative mathematics and quantum information
University of Bristol, August 8-10 2019
Please post topics for discussion in the comments section below.
Some suggestions from David Roberson:
1) We now know that graphs $G$ and $H$ are quantum isomorphic (in the commuting operator framework) if and only if they admit the same number of homomorphisms from any planar graph $K$. But the notion of quantum isomorphism also extends to quantum/non-commutative graphs. For example, it is known that the Petersen graph is quantum isomorphic to two different quantum graphs, but not to any classical graphs (other than itself). Can the above mentioned result be extended to the case where one or both of $G$ and $H$ are quantum graphs. If so, how? There are notions of homomorphism for quantum graphs, but it is not clear how to “count” these. Similarly, can the above result be extended to include the case where $K$ is a quantum graph? For this one would need a definition of what it means for a quantum graph to be planar. Could this be accomplished by establishing a notion of minors of quantum graphs? Or could we make use of the Colin de Verdiere graph parameter which gives an algebraic characterization of planarity?
2) Is there a homomorphism counting characterization of the tensor product framework version of quantum isomorphism? We can show that for any finite non-planar connected graph $K$, there are quantum isomorphic (in the tensor product framework) graphs $G$ and $H$ that have a different number of homomorphisms from $K$. But since we know that the tensor product and commuting operator frameworks give rise to distinct notions of quantum isomorphism, any such characterization of the former must involve something outside the class of finite classical graphs. Perhaps infinite planar graphs could be considered? Or could quantum graphs be useful here?
2) Is there a homomorphism counting characterization for approximate quantum isomorphism?
3) Is it possible/worthwhile to determine the smallest pair of non-isomorphic graphs that are quantum isomorphic?
4) Let $U = (u_{ij})_{i,j = 1, \ldots, n}$ be a magic unitary whose entries $u_{ij}$ are elements of a $C^*$-algebra that admits a tracial state $t$. Corresponding to this magic unitary and tracial state there is a correlation (joint conditional probability distribution) $p : [n]^4 \to \mathbb{R}_{\ge 0}$ defined as $p(\ell,k | i,j) = t(u_{i\ell}u_{jk})$. Such a correlation is said to exhibit non-locality if it cannot be produced by separated classical parties. Equivalently, $p$ exhibits non-locality if it is not a convex combination of correlations
\[
q_f(\ell,k | i,j) := \begin{cases} 1 & \text{if } f(i) = \ell \ \& \ f(j) = k \\ 0 & \text{o.w.}
\end{cases}
\]
where $f : [n] \to [n]$ is a bijection.
If the entries of the magic unitary $U$ commute, then it is not possible for the resulting correlation (regardless of the choice of tracial state) to exhibit non-locality. Thus for $n \le 3$ no $n \times n$ magic unitary exhibits non-locality. However, it is not the case that non-commutativity of the entries of $U$ is sufficient to exhibit non-locality. There are $5 \times 5$ magic unitaries (with finite dimensional entries) that exhibit non-locality. The question that remains is whether there are any $4 \times 4$ magic unitaries that exhibit non-locality. If we restrict the entries of the magic unitary to be finite dimensional, then I believe I have a proof that non-locality never occurs. Moreover, to prove that non-locality never occurs in general, it is necessary and sufficient to show that t(u_{11}u_{22}u_{33}) + t(u_{12)u_{23}u_{34}) \ge 0 for any $4 \times 4$ magic unitary $U = (u_{ij})$ and tracial state $t$.
5) What graphs $G$ exhibit non-locality? By this I mean for what graphs $G$ (with adjacency matrix $A_G$) do there exist magic unitaries $U$ such that $A_G U = U A_G$ and $U$ exhibits non-locality. This is related to the question of which graphs have “quantum symmetry” which is equivalent to the existence of a magic unitary $U$ with non-commutative entries satisfying $A_G U = U A_G$. However, admitting quantum symmetry is not enough. For example, the 4-cycle has quantum symmetry but does not exhibit non-locality. The smallest possible graph is the complete (or empty) graph on 4 vertices, which exhibits non-locality if and only if there is a $4 \times 4$ magic unitary exhibiting non-locality. More generally, can we understand the difference between the properties of having quantum symmetry and exhibiting non-locality? Is exhibiting non-locality a much stronger condition? Or does quantum symmetry almost always imply non-locality?
A few topics off the top of my head. Here ‘quantum set’=’f.d. C*-algebra’:
1) What is the relationship between quantum functions (Soltan, Musto et al.) and CPTP maps? Leading on from this, what is the relationship between entanglement-assisted homomorphisms in the sense of Stahlke and the stricter ‘projective’ quantum homomorphisms (Mancinska & Roberson/ Musto et al.)? It seems that for every entanglement-assisted homomorphism in the sense of Stahlke between classical graphs
there is a quantum homomorphism in the stricter sense; is this true for noncommutative quantum graphs also?
2) Can the notion of quantum bijection be generalised to the case of an infinite-dimensional auxiliary Hilbert space (e.g. by considering infinite-dimensional representations of the quantum permutation group?) If so, do these have a physical interpretation in terms of entanglement-invertible channels and no-signalling games?
3) While quantum functions are strategies for synchronous games, it seems that quantum bijections A->B are strategies for synchronous games with input set A, output set B, where the verifier may send an element of either the input or the output set. There is another characterisation of quantum bijections A->B in terms of entanglement-invertible channels: that is, quantum channels F: A \otimes B(H) \to B and G: B \otimes B(H) \to A such that, for a maximally entangled state \phi: \mathbb{C} \to B(H) \otimes B(H), the following two equations hold: G \circ (F otimes id_{B(H)}) \circ (id_{A} \otimes \phi) = id_A, F \circ (G \otimes id_{B(H)}) \circ (id_B \otimes \phi) = id_B. What is the conceptual relationship between these two characterisations?
3) What can be said about the quantum automorphism group of a general (i.e. nonclassical) quantum graph, such as the confusability graph of a quantum channel?
4) What new entanglement-assisted communication schemes can be obtained from quantum symmetries of channels? To start with, are there any interesting classical or quantum channels whose entanglement-assisted capacities are unknown and which are covariant for a coaction of some compact quantum group or classical group of central type?
5) Can we demonstrate that quantum isomorphism of quantum confusability graphs preserves all entanglement-assisted capacities of the associated channel? Sufficient to show that, given a coaction of some compact quantum group G on a quantum confusability graph (A, \Gamma), we can construct a quantum set B, a channel N: A \to B inducing the confusability graph, and a coaction of G on B such that N is covariant.
6) Given a quantum graph (A,Gamma) with a coaction by a f.d. compact quantum group G, and a twist \omega of G, we can construct a quantum isomorphic quantum graph (A’,Gamma’) – the adjacency matrix Gamma is the same, but the quantum set A’ is the \omega-twist of the comodule algebra A. Can we say anything about the new quantum graph when e.g. (A,Gamma) is a classical graph, based on properties of the action and twist? E.g. given a classical graph with a coaction of G and some choice of twist, what is the condition on the coaction and twist for the twisted comodule algebra to be simple? (This would give a noncommutative graph on a matrix C*-algebra.)
Here are some questions around the Schurity problem for graphs and its quantum analogue.
A graph X is called Schurian if its coherent algebra COH(X) (i.e. the smallest coherent algebra containing its adjacency matrix) equals the centralizer CENT(X) of its automorphism group. It is known (Lupini-Mancinska-Roberson) that the centralizer QCENT(X) of the quantum automorphism group sits between COH(X) and CENT(X) and we say that a graph is quantum Schurian if COH(X) = QCENT(X). Note that Schurian implies uantum Schurian.
1) What are examples of quantum Schurian graphs which are not Schurian ?
2) What are examples of graphs which are not quantum Schurian ?
3) One can give a pictorial description of the elements of QCENT(X) : these are linear combinations of noncrossing partitions with the adjacency matrix A possibly inserted along the strings. Can we describe which elements among these belong to COH(X) ?
4) Less directly related : are there graphs with trivial automorphism group but non-trivial quantum automorphism group ?
1) There is a pair of non-isomorphic graphs on 24 vertices, let’s call them G and H, that are quantum isomorphic. Both are Schurian and thus quantum Schurian. I am fairly sure the statement “the disjoint union of quantum isomorphic quantum Schurian graphs is quantum Schurian” is true, and in any case for G and H it is not so hard to see that their disjoint union will be quantum Schurian. However, since they are not isomorphic, their disjoint union will not be Schurian. Probably lots of examples can be constructed like this, but maybe such examples are not super interesting.
2) Simon Schmidt has shown that the Shrikhande graph is not quantum Schurian. See Remark 6.3 here: https://arxiv.org/abs/1906.06537. The Shrikhande graph has 16 vertices which is the smallest possible for a non-Schurian graph (but I am not sure if there are others on 16 vertices or not).
3) In such a noncrossing partition take each occurrence of the adjacency matrix A along a string and draw it as two vertices with an edge between them (so one of the vertices has a string coming into it and the other has a string coming out), making sure to distinguish these edges from strings. Now contract every string (not edge) that goes between two vertices (some will only be incident to a single vertex) so that these two vertices become one. Now you have a graph H with some strings hanging off of it. If you draw your diagrams vertically then some strings will be hanging off of the top and some off of the bottom of the graph. Let a_i be the vertex of H that the i^th top string is incident to, and b_j the vertex the j^th bottom string is incident to (note that some vertices can be incident to many top and/or bottom strings. This “graph H with strings” corresponds to an intertwiner T of the quantum automorphism group of G, qut(G), as follows: the (u_1…u_\ell, v_1…v_k)-entry of T is the number of homomorphisms (adjacency-preserving maps) \phi from H to G such that \phi(a_i) = u_i and \phi(b_j) = v_j for all i,j. This is an informal description of all of the intertwiners of qut(G). More formally, the graph H can be any planar graph, and the vertices a_1,…,a_\ell and b_1,…,b_k must satisfy some technical condition (also having to do with planarity). The elements of QCENT(G) are the linear span of such matrices where \ell = k = 1. In this case, where \ell=k=1, the technical condition on a_1 and b_1 is equivalent to requiring that the graph obtained by adding an edge between a_1 and b_1 is still planar. In contrast, COH(G) consists of all matrices that can be obtained from the identity, the all ones matrix, the adjacency matrix of G, and the operations of matrix product, entrywise multipilication, transposition, and linear combinations. In terms of “graphs with strings hanging off of them” as described above, the identity matrix is a single vertex with a string hanging off in each direction, the all ones matrix is two isolated vertices each with a string hanging off of them but in different directions, and the adjacency matrix is the same but with an edge between those vertices. We can describe matrix product by “concatenating” the graphs with strings in the natural way (the same as with parititions). The entrywise product corresponds to merging the vertex with the incoming string in one of the graphs with the vertex with the incoming string in the other graph and similarly for the vertices with the outgoing strings. Transposition is as usual, it just switches the incoming and outgoing string. Thus COH(G) is the linear span of the matrices corresponding to the graphs with one incoming and one outgoing string that can be obtained with these starting graphs and these operations. Based on the results of Dell, Grohe, and Rattan (https://arxiv.org/abs/1802.08876), I suspect that you obtain the graphs with treewidth at most two, but with some condition on which vertices the incoming and outgoing strings can be attached to. Such a condition is necessary since if H is the diamond graph (a 4-cycle plus one of its diagonals), then the matrix corresponding to putting the incoming and outgoing strings on distinct degree three vertices is always in COH(G) but the matrix corresponding to putting the strings on distinct degree two vertices is not in COH(G) for G being the Shrikhande graph. I suspect the technical condition for where the strings can be placed is related to the definition of series-parallel graphs.
4) Great question. I originally heard this question from Simon Schmidt for what it’s worth.