Basics of Quantum Graphs

Γεώργιος Κόλλιας, Vassilis Kalantzis, Theodoros Salonidis +1 more

We propose Quantum Graph Transformers (QGT), a novel approach for realizing the Transformer architecture for graph learning with quantum processors. QGT is built on top of the Graph Trans-former (GT) architecture and addresses the main challenge of mapping GT basic functions such as node encodings, graph structure, all-to-all connectivity, and message passing to quantum computing primitives and processors. We empirically demonstrate the training and inference efficacy of our proposed QGT architecture for the graph classification task on quantum devices over various graph datasets.

Peter Kuchment

Noson S. Yanofsky, Mirco A. Mannucci

Everyone has lost their marbles! Anonymous Before we formally present quantum mechanics in all its wonders, we shall spend time providing some basic intuitions behind its core methods and ideas. Realizing that computer scientists feel comfortable with graphs and matrices, we shall cast quantum mechanical ideas in graph-theoretic and matrix-theoretic terms. Everyone who has taken a class in discrete structures knows how to represent a (weighted) graph as an adjacency matrix. We shall take this basic idea and generalize it in several straightforward ways. While doing this, we shall present a few concepts that are at the very core of quantum mechanics. In Section 3.1, the graphs are without weights. This will model classical deterministic systems. In Section 3.2, the graphs are weighted with real numbers. This will model classical probabilistic systems. In Section 3.3, the graphs are weighted with complex numbers and will model quantum systems. We conclude Section 3.3 with a computer science/graph-theoretic version of the double-slit experiment. This is perhaps the most important experiment in quantum mechanics. Section 3.4 discusses ways of combining systems to yield larger systems. Throughout this chapter, we first present an idea in terms of a toy model, then generalize it to an abstract point, and finally discuss its connection with quantum mechanics, before moving on to the next idea.

Igor Chełstowski

We present a construction of quantum Kneser graphs, which yields classical Kneser graphs in the commutative case.We also generalize this construction to obtain quantum versions of generalized Kneser graphs, such as Johnson graphs.We discuss several basic properties of the constructed quantum graphs, such as their reflexivity and regularity.Then, we investigate their quantum chromatic numbers and establish upper bounds on them by constructing explicit colorings.We also investigate spectral lower bounds on quantum chromatic numbers for several examples and formulate a conjecture about their asymptotic behavior.Lastly, we present an alternate approach to quantization of Kneser graphs and a few results obtained for the quantum Mycielski construction.

Sooyeong Kim, David W. Kribs, Michael Nathanson +2 more

We consider the problem of distinguishing sets of quantum product states with local operations and classical communication (LOCC). Recent work has used graph theory to identify sets of product states distinguishable with one-way LOCC. We extend these efforts to full two-way LOCC, with the first significant analysis of the set of graphs corresponding to bipartite product states that can be distinguished with two-way protocols after finitely many steps. We derive basic closure properties of the set of distinguishable graphs and identify some classes of graphs that guarantee local distinguishability and some graphs that do not. We also include several examples and forward-looking comments.