Extending graph transformers with quantum computed aggregation
Authors: Slimane Thabet
Romain Fouilland
Loic Henriet
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph neural networks
graph representation learning
quantum computing
graph transformers

Abstract: Recently, efforts have been made in the community to design new Graph Neural Networks (GNN), as limitations of Message Passing Neural Networks became more apparent. This led to the appearance of Graph Transformers using global graph features such as Laplacian Eigenmaps. In our paper, we introduce a GNN architecture where the aggregation weights are computed using the long-range correlations of a quantum system. These correlations are generated by translating the graph topology into the interactions of a set of qubits in a quantum computer. The recent development of quantum processing units enables the computation of a new family of global graph features that would be otherwise out of reach for classical hardware. We give some theoretical insights about the potential benefits of this approach, and benchmark our algorithm on standard datasets. Although not being adapted to all datasets, our model performs similarly to standard GNN architectures, and paves a promising future for quantum enhanced GNNs.

Under review as a conference paper at ICLR 2023
EXTENDING GRAPH TRANSFORMERS WITH QUANTUM COMPUTED AGGREGATION
Anonymous authors Paper under double-blind review
ABSTRACT
Recently, efforts have been made in the community design new Graph Neural Networks (GNN), as limitations of Message Passing Neural Networks became more apparent. This led the appearance of Graph Transformers using global graph features such as Laplacian Eigenmaps. In our paper, we introduce a GNN architecture where the aggregation weights are computed using the long-range correlations of a quantum system. These correlations are generated by translating the graph topology into the interactions of a of qubits quantum computer. The recent development of quantum processing units enables the computation of a new family of global graph features that would be otherwise out of reach for classical hardware. We give some theoretical insights about the potential benefits this approach, and benchmark our algorithm on standard datasets. Although not being adapted to all datasets, our model performs similarly to standard GNN architectures, and paves a promising future for quantum enhanced GNNs.
INTRODUCTION
Graph machine learning is an expanding field of research with applications in chemistry (Gilmer
cet al. 2017), biology (Zitnik et al. 2018). drug design (Konaklieva 2014), social networks (Scott
22011. computer vision (Harchaoui & Bach 2007). science Saachezz-Gnzzlle et al. 2020). In
the past few years, much effort has been put into the design of Graph Neural Networks (GNN)
(Hamilton). The goal learn vector representation of the nodes while incorporating information
about the graph. The learned information is then processed according to the original problem.
The dominating approach for designing GNNs have been Message Passing Neural Networks (MPNN) (Gilmer et al.] 2017). At each layer of MPNNs, linear layer is applied to the node features, then for each node, the feature vectors of the direct neighbors are aggregated and the result is added to the node feature vector. The way the aggregation is performed differentiates variety of architectures among which GCN (Kipf & Welling 2016), SAGE (Hamilton et al. 2018). GAT VVeličkovié et al. 2018), GIN (Xu al. 2018).
Despite some successes, it has been shown that MPNNs suffer several flaws. First and foremost, their theoretical expressivity is related to the Weisfeiler-Lehmme (WL.) test. It means that two graphs who are indistinguishable via the WL. test (example in Ta) will lead to the same MPNN output (Morris al.) 2019). This can cause several problems because two different substructures will not be differentiated. This is especially true in chemistry where the graphs represent different molecules (graphs in la could represent two molecules). MPNNs also perform best with homophilic data and seem to fail on heterophilic graphs (Zhu et al. 2020). Homophilic graphs mean that two nodes have the same labels if they are close to each other in the graph, which is not necessarily the case. Finally, MPNNs suffer from oversmoothing (Chen et al., 2020) and oversquashing (Topping et al.) 2021] Oversmoothing means that the output features of all nodes will converge to the same value as the number of layers increases. Oversquashing occurs when few links on the graph separates two dense clusters of nodes. The information that circulates through these links is then an aggregation of many nodes and is much poorer compared to the information initially present.
Solutions to circumvent those issues are currently investigated by the community. The main idea is not to limit the aggregation to the neighbors, but to include the whole graph, or larger part of it. Graph Transformers were created in this spirit with success on standard benchmarks (Ying et al. 2021 Rampášek et al. 2022). Similarly to the famous transformer architecture, aggregation

---

Under review as a conference paper at ICLR 2023
rule is provided to every pair of nodes in the graph with incorporation of global structural features. Examples of global structural features are Laplacian Eigenmaps (Kreuzer et al. 2021). eigenvectors of the Laplacian matrix.
The goal of this work to explore new types of global structural features emerging from quantum physics that can be added GNN. The rapid development of quantum computers during the previous years provides the opportunity to compute features that would be otherwise intractable. These features contain complex topological characteristies of the graph, and including them could improve the quality of the model, the training or inference time, or the energy consumption.
The paper is organized as follow. Section provides elements about quantum mechanics for the unfamiliar reader and details how to construct a quantum state from a graph. Section 3 provides theoretical insights on why quantum states can provide relevant information that hard compute with a classical computer. Section 4 details our main proposal, GNN architecture with quantum correlations. Section [5 provides a summary on how our work fits in the current literature. Section describes the numerical experiments.
2 THE GRAPH AS QUANTUM SYSTEM
2.1 QUANTUM INFORMATION PROCESSING
We provide in this subsection the basics of quantum information processing and quantum dynamics for the unfamiliar reader. More details can be found in (Nielsen & Chuang 2002; Henriet et al., 2020
A quantum state of a system is unitary complex vector whose module square of individual entries represent the probability of the system to be in each of these individual entries states. The systems that are often considered are sets of individual two levels systems called qubits whose states are
denoted (0) and [1}. The state of an individual qubit is represented by the complex vector
with |a 1 1|112 1, also noted a (0) + B [1). system of N qubits is vector from C² noted
2 (1b) = (1). i being associated to a bitstring of size N. { ( } is referred as the computational
1=0
basis of the system. The conjugate transpose of (ι)) is noted (w²
A quantum state can be modified by operator U which is a complex unitary matrix of size
2 x 2% Quantum dynamics follow the Schrödinger equation
d dlb) dt
Hi(() (v))
where H((t) the hamiltonian the dynamic, a complex hermitian matrix of size 2 x 2 The solution the equation for some time T is (VT)) U(T) (x(()) where U(T)
exp -1 H(())l is the time evolution operator.
Classical information can be extracted from a quantum state by measuring the expectation value of an observable. An observable Ô is complex hermitian matrix size 2 x 2 and its expectation value on the quantum state |ı>) is the scalar (ub Ô (t)).
We introduce some notations that will be used along the paper. The Pauli matrices the following
111 x = 11 Y 0
0 0 -1
I = 1012
2
A Pauli string of size N is a hermitian complex matrix of size N x 2 equal to the tensor product, or Kronecker product of N Pauli matrices. In the rest of this paper, will note Pauli strings by their non-trivial Pauli operations and the qubit they act on, with indexing going from right to left. For instance, in system of qubits, X2Y, T 60 I X 80 6
2

---

Under review as a conference paper at ICLR 2023
2.2 GRAPH HAMILTONIANS
Given graph G(V, E), we associate quantum state of [ qubits. A hamiltonian of interactions acting on [v] qubits with the same topology can be constructed with the form
Hg =
Σ Hij
(2)
(iJ)EE
where Hij is hermitian matrix depending on the vertices i and
We give below several examples of graph hamiltonians respectively the Ising hamiltonian, the XY hamiltonian, and the Heisenberg hamiltonian.
Σ (WJ)EE
ZiZ,
HXY = Σ
X,X, + Y,Y,
(4)
(HJ)EE
xxx2
Σ
X,X, + Y,Y + J2,2,
(5)
(i,))E
with / > 0 a constant.
In the examples presented above, the interactions share the topology of the input graph. As such, an evolution with Hg generates entanglement following the graph connectivity.
2.3 PARAMETERIZED GRAPHI QUANTUM STATE
With the graph hamiltonians Hgg, one can create parameterized quantum states of |V] qubits con-
[
taining information about the considered graph. Let H.M
Σ
X₁ be a 'mixing' hamiltonian. We
then consider quantum states evolving through the Schrödinger equation with hamiltonian Hi(t) = ((t)HHs + I(t)Hg
(6)
where (t()) and I(t) are bounded real functions arbitrarily chosen.
We will call these states quantum graph states or graph states, not to be confused with the usual def- inition of graph states in quantum computing (Clark et al. 2005). We consider specifically alternate layered quantum states which can be written
(+)
II (G-i iHots) A=1
iR (2b)
where 0 = (fo. to. t1. 0p) is real vector of parameters. The choice of these states is moti- vated by their wide use for quantum algorithms for combinatorial optimization like Quantum Ap- proximate Optimization Algorithm (Farhi et (014)) but our procedure can be generalized to other parameterized states depending on graph Hamiltonian.
PROPERTIES OF QUANTUM GRAPH STATES
Graph quantum states may be able to access topological structures in the graph that would otherwise be very difficult to detect with classical methods. We detail here several examples of graph features that are difficult to compute or learn with classical methods and easy to do with quantum computer.
3.1 ANTIFERROMMAGNETEE STATES ON WL INDISTIGUISHABLA GRAPHS
In figure J we provide two graphs and their ground state with respect to the Ising Hamiltonian defined in Eq. (3) the state (ı)) minimizing ( Hz (&).. This state will be called the antiferro- magnetic state, re the state where maximum number of neighboring nodes are in opposite states. The two graphs are non distinguishable by the WL test and yet have very different antiferromannetic states.

---

Under review as a conference paper at ICLR 2023
3.2 XY GRAPH STATES AND CONNECTION TO RANDOM WALKS
We describe here the properties of the XY hamiltonian HXY described in equation 4 that already have been highlighted in (Henry al. 2021). This hamiltonian has the property to preserve the subspaces with a total occupation number n, or the Hamming weight of the bitsring associated to a computational basis state. Let us note H, span (t) j with Hamming weight of n). H
then block-diagond diagonl,,, each block acting on one of the Hn, The restriction of HXY to H1 is the adjacency matrix of the graph, and performing evolution starting in H1 is equivalent to make random walk of single particle on the graph.
Similarly, an evolution on higher order H, is equivalent to particle random walk with hard- core interactions (i.e. there can at most one walker per site). Let us define the graph Gn of size (*), each vertex representing the computational basis states of Hn and ((), (5) being connected (i) x [8) = 1. An evolution under 7 XY is equivalent to random walk on G..
(a)
(b)
Figure 1: A pair of graph distinguishable by the WL test (a) and associated states minimizing their Ising energy (Tb). One of the graph has only ground states with three excited qubits and the other has ground states with two excited qubits (there are also ground states with excited qubits that are not shown here).
3.3 NODE CLASSIFICATION ON LATTICE MODELS
In this subsection, we will look at the particular case of lattice graphs and the behavior of classical GNNs on them. A lattice graph is a fully connected subgraph of a regular lattice, containing full number of cells. In this configuration, several nodes will have identical outputs after going through MPNN with uniform input features without sampling of neighbors or pooling. Thus there are labelings of nodes that will impossible to learn with MPNN for node classification task.
The phenomenon is illustrated in figure 2 where we show for several lattices (square, triangular, honeycomb and kagome) the outputs of a Graph Convolution Network and an antiferromagnetic node labeling which will not be learnable by a MPNN. This is to be related to previous work showing the limitations of MPNN for heterophilic data, meaning that nodes with the same labels tend not to be neighbors. The proposed labeling be easily learned with quantum computer by preparing quantum graph state with antiferromagnetic correlations. Preparing this state has notably been done with neutral atoms platforms (Scholl al. 2021).
We also investigate the power of structural embeddings at the core of Graph Transformers like Laplacian Figenmaps (LE). On each lattice graph, train GCN with laplacian eigenmaps as input features and layers for different numbers of input features. The training is done with Adam optimizer for 600 epochs with a .01 learning rate. The results are shown in figure 2c For all lattices, too few parameters or too few input features results in the failure of the network to learn the labels. 20 input features and 20 hidden neurons enough to reach 100% training accuracy. The triangular lattice is the most difficult to learn on. Although the learning is possible with LE features, may need a substantial amount of parameters be performed.
GRAPH TRANSFORMER WITH QUANTUM CORRELATIONS
This section presents main proposal GTQC (Graph Transformer with Quantum Correlations), an architecture of Graph Neural Network based on Graph Transformers and incorporating global graph features computed with quantum dynamics. A global view of the algorithm is represented
4

---

Under review as a conference paper at ICLR 2023
(a)
(b)
1.00
triangular
honeycomb
10
kagome
100
035
035
Input features
090
input Teatures
8500
Inpuut features
Imput Teatures
030
-4
688
-08
015
6.00
089
0.00
0.65
7075
660
0.70
hidden neurons
neurons
hidden
hidden
Figure 2: A lattice graph with antiferromagnetic node labeling (2a not strictly antiferromagnetic for the triangular and kagome lattice but we will name it this way for simplicity) and the output of Graph Convolution Network (2b). Each color represents single value of the output of the GCN with uniform node features, 6 layers, 50 hidden neurons per layer. Two nodes with the same color have the same output. Such approach will fail correctly classify the nodes on the graph with the antiferromagnetic labeling. In 2clis shown the training accuracy of a GCN with laplacian eigenmaps as input features (average over runs).
figure Representation learning graphs using neural network has become the state of the of graph machine learning (Wu et al., 2020). Scaling deep learning models has brought lots of benefits as shown by the success large language models (Brown et al. 2020 Alayrac al., 2022). The goal was to bring the best of both worlds, meaning large overparameterized deep learning models, and structural graph features intractable with a classical computer. The architecture we propose only uses nodes features, but similar techniques could be implemented for edges features.
4.1 TRANSITION MATRIX FROM QUANTUM CORRELATIONS
Here we develop method to compute parameterized transition matrix or quantum attention matrix from the correlations of a quantum dynamic. It is done with quantum computer, or Quantum Processing Unit (QPU). This matrix will later be used in the update mechanism of architecture. Once the quantum attention matrix is computed, the rest of the architecture is purely classical, and all existing classical variations could be implemented. Finally, the quantum attention matrix is by construction equivariant permutation of the nodes.
We consider parameterized graph state as defined in equation parameterized by the trainable pa- rameter 0 (0o, to. 01, f.....0, .0p), and noted (²)).. 0 will be called the quantum parameters in tch rest of the paper. We then compute for every pair of nodes (i,j) the vector of 2-bodies observ- ables Cj (Z;Z,), (X,X)), (YY)), (X,Z,), (X,Y)), (Y,Z,) (X, (X,Y.). (Y, ZY)" where (0) = (0) (0)).
The quantum attention matrix is computed by taking linear combination of the previous correlation vector and optionally a softmax over the lines.
A(0); = - -CT
(8)
A(0), sof softman(1
(9)
5

---

Under review as a conference paper at ICLR 2023
Parameterized quantum graph state
Graph
(0 Spp.-pppp.... 0p)
Node features H*
1- Il-
Correlation
H
H
A(0)
A(O)H'
H'
A(O)H'
Figure 3: Overview model. The graph is translated into hamitonian that will drive quantum system. After parameterized evolution, the correlations are measured and aggregated into single attention matrix.
where y is trainable vector of size 9. Multiple correlators measured to enrich the number of features that can be extracted out of the quantum state. Limiting ourselves to egg (Z;2,) might be inefficient because ( Z, Z, ( could be written X where is matrix with row equal to (Z (b)))) The resulted weight matrix is therefore symmetric positive semi-definite matrix, and can be reduced by Choleski decomposition = LL" where a real matrix of shape N x N. The same model can then be constructed by learning the matrix L even though it is unclear if that would be efficient.
4.2 UPDATE MECHANISM
The quantum weight matrix previously computed is used as a transition matrix, or attention matrix, in the update mechanism of our model. Given H' the node features matrix at the layer the node features matrix at the next layer is computed with the following formula:
=
(10)
where is a non-linearity, H is of size (N x d) where each row represents a node feature of dimension d, W is learnable weight matrix of size (2d x da), A(0) is the attention matrix with parameters 0 computed in and is the concatenation on the columns.
4.3 MULTI HEAD LAYER
With the same approach as Transformers or Graph Attention Networks, one can use several attention heads per layer to improve the expressivity of the architectures. The update formula is given by:

---

Under review as a conference paper at ICLR 2023
H -"11=11 Nacada HEAD,(H))
(11)
where each head is computed with the formula 4.2 The total dimension of the feature vector is Nhends dh. Each head has a different quantum circuit attached, and can be computed parallel one possesses several QPUs.
4.4 EXECUTION ON A REAL QUANTUM DEVICE
We provide here some precisions on how our model would be implemented on real quantum devices. More details is provided in the supplementary material
Decoupling between quantum and classical parts
The parameters of the quantum states and the classical weight parameters are independent in our algorithm. One can then asynchronously measure all the quantum states of the model and run the classical part. This may be particularly important for NISQ implementation since the access of QPUs are quite restricted in time. Furthermore, the gradients of the classical parameters depend only the correlation matrices, they be easily computed with backpropagation without any supplementary circuit run.
Training the parameters of the quantum state
Computing the gradients of parameterized quantum circuits is a challenge source of numerous re- search in the quantum computing community (Kyriienoo & Elfving 2021 Wierichs et al.) 2022] Banchi & Crooks 2021). Fortunately some strategies exist and can be deployed, although not for all types hamiltonians
Random parameters
Optimizing over the quantum parameters can be costly and ineffective with current quantum hard- ware. Even with emulation, back-pre proo-propgggting the loss through a system of more than 20 qubits is very difficult. The idea we propose the spirit of (Rahimi Recht 2008) to evaluate the attention matrices on many random quantum parameters, and only training the classical weights.
5 RELATED WORKS
The use of global graph features has already been used, leading to improvements, in particular positional encoding of the nodes like Laplacian Figenmaps (L.F). It has been shown that GNN with LE is a universal approximator of the functions over the set of graphs (Kreuzer et al.) (021)) However, some functions may require an exponential number of parameters to be approximated.
recent years, Quantum Machine Learning has seen fast development with both theoretical and experimental udvances[Huang al. (2022); Cerezo al. (2022). Using quantum computing for Machine Learning on graphs has already been proposed in several works, as reviewed in (Tang al. 2022). The authors of (Verdon al. 2019) realized learning tasks by using parameterized quantum circuit depending on a Hamiltonian whose interactions share the topology of the input graph. Comparable ideas were used build graph kernels from the output of quantum procedure, for photonic (Schuld et al.) 2020) as well as neutral atom quantum processors (Henry et al. 2021). The architectures proposed in these papers were entirely quantum, and only relied classical computing for the optimization of variational parameters. By contrast, in our proposal the quantum dynamics only plays role in the aggregation phase of a larger entirely classical architecture. Such an hybrid model presents the advantage of gaining access to hard-to-access graph topological features through the quantum dynamics, while benefiting from the power of well-known existing classical architectures.
Importantly, the architecture proposed here could be readily implemented neutral-atom quantum processors (Henriet et al., 2020). In those platforms, the flexibility in the register's 's geometry enables the embedding of graph structurr data into the quantum dynamics (Henry al.) 2021). with recent experimental implementation. Experimental progress have illustrated the large scalability of those platforms (Schymik et al. 2022), with the realization of arrays comprising more than 300 qubits.

---

Under review as a conference paper at ICLR 2023
6 EXPERIMENTS
6.1 TRAINING ON GRAPH COVERS DATASET
We test the performances of our model on dataset of non isomorphic graphs constructed to be indistinguishable by the WL test. We believe that this task will be especially difficult for classical GNNs and could constitute an interesting benchmark. The way construct such graphs has been investigated in (Bamberger 2022) and more details can be found in the supplementary material B We compare the training loss with one the most recent implementation of graph transformers (GraphGPS) by (Rampásek et al., 2022). The results in figure 5 We see that model able to reach much lower values the loss than GraphGPS, even both model acheive 100% accuracy after 20 epochs.
10
GTQC (ours)
Graph Transfomer GPS
10a
10-1
10 2
10-1
100
200
300
400
500
Epoch
Figure 4: Training loss for our model and recent graph transformer implementation (GraphGPS) RRampšskk et al. 2022). Both models achieve 100% accuracy after 20 epochs.
6.2 BENCHMARK ON GRAPH CLASSIFICATION AND REGRESSION TASKS
We benchmarked our model GTQC and its randomized version of it with different GNN architec- tures. We selected different datasets from various topics and with diverse tasks show the general capabilities of our approach. We limited the size of the graphs to 20 nodes in order to be able to simulate the quantum dynamic, and performing a backpropagation. We then chose datasets with the majority of graphs falling below this size limit. The details of each dataset and the protocol can be found in appendix
All metrics are such that the lower the better, for classification tasks we display the ratio of misclas- sified objects.For QM9 the loss is aggregated over all the targets. FigureBJshowe shows results as box plots accompanied by the underlying points. Though the variability of the results is bit higher, GTQC reaches similar results than usual classical well-known approaches on QM7 and DBLP v1 (even beating GCN this dataset) and seems relevant QM9 well. GTQC random usually outper- forms GTQC, illustrating the complexity of the optimisation of the quantum system. GTQČ random provides very promising results on DBLP_v _I and outperforms all other approaches on QM9. Letter- med seems to represent a difficult task for our quantum methods as they both perform very poorly and way worse than classical methods. QM7 also seems to be challenging for GTQC random. Table [ shows the results grouped by breadth, compared to the results for GTQC with the same breadth and averaged other various dataset splits. GTQC random has only been trained for breadth of 128 neurons and yields impressive results by clearly outperforming other methods on QM9 and being on par with the best method on DBLP_v1. The raw losses are displayed the appendix.
7 CONCLUSION
We investigated this paper the opportunity provided by the recent advances in quantum com- puting hardware to construct new families of graph neural networks. We proposed GTQC, new architecture of graph transformers that incorporates graph features coming from quantum physics. Specifically, measure the correlations of quantum system whose hamiltonian has the same topology as the graph of interest. We then use these correlations as an attention matrix for a graph transformer. Although not being adapted to all datasets, our model performs similarly to standard
8

---

Under review as a conference paper at ICLR 2023
Dataset-DBLF
Dataset-QM7
Model
90
GTQC
GTQC
Relevant error
SAGE
0.09
GAT
70
60
0.08
50
40
Detaset=QM9
Detaset-Letter-nee
0.8
Relevant emro
0.6
0.4
0.2
GTQC random GTQC
SAGE
GAT
GCN
GTQC random
GTQC
SAGE
GAT
GCN
Model
Model
Figure 5:
Summary graph of the results of the different models on the studied datasets. Each point an instance of the model with specific hyperparameters and specific seed for dataset splits.
Table 1: Relative best test error compared to GTQC, grouped by breadth the hidden layer. We
colored in blue the classical models for which at least one of GTQC GTQC random is better. The standard deviations are over different splits of the datasets.
dataset model
DBLP
Letter-med
QM7
QM9
breadth
GAT
-1.74 + 1.79%
-69.12 + 3.24%
-6.79 4.297%
-49.70 # 0.00%
GCN
6.10 9.51%
-70.55 # 7.77%
-2.12 6.82%
-47.26 # 0.00%
128
SAGE
-9.76 + 6.
-86.59 + 2.60%
-9.66 + 5.04%
-59.29 + 0.00%
GTQC random
-9.41 6.80%
-30.03 0.00%
34.32 4
-70.79 + 0.00%
GTQC
0.00
0.00
0.00 57.22%%
GAT
4.14 12.31
-70.58 4.61%
-13.80 7.93%
.4..00 0.00%
GCN
10.09 + 9.94%
-75.93 4 3,01%
9.69
-44.72 # 0.00%
512
SAGE
-10.45 + 4.44%
-86.34 4 2.73%
-61.33 + 0.00%
GTQC
0.00 5.77%
0.00
46.366%
0.00 = 41.08%
GAT
1.10 12.66%
+69.44
-17.38 + 4.08%
GCN
9.65 = 16.50%
-77.96
7.24
1024
SAGE
-13.51 + 3.20%
4
-9.65 4.53%
-57.73 # 0.00%
GTQC
0.00 8.21%
0.02%%
0..03%
0.00 + 2.80%
GAT
-1.28 $ 5.01%
74.00
-9,55 5.08%
GCN
14.60 = 9.63%
-80.13 + 2.65%
7..77
2048
SAGE
-3.13 + 13.44%
-88.07 + 2.13%
-16.96 # 9.80%
GTQC
0.00 3.80%
0.00 7.65%
0.00 3.78%
GNN architectures different benchmarks. While the exact capabilities of our approach not yet well understood, quantum enhanced GNNs are a promising family of models that could be fully exploited with near term quantum hardware.

---

Under review as a conference paper at ICLR 2023
8 REPRODUCIBILITY STATEMENT
The code to reproduce all the experiments is available in the supplementary material, with the de- scription of all seeds and hyperparameters.
REFERENCES
Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, lain Barr, Yana Hasson, Karel Lenc, Arthur Mensch. Katie Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning. arXiv preprint arXiv:2204. 14198, 2022.
Jacob Bamberger. topoloical characterisation of weisfeiler-leman equivalence classes, 2022.
URL wwwph:ttp/s..itti. org/ wtt.b////2...... 11876
Leonardo Banchi and Gavin E Crooks. Measuring analytic gradients of general quantum evolution with the stochastic parameter shift rule. Quantum, 5:386, 2021.
Lorenz C. Blum and Jean-Louis Reymond. 970 million druglike small molecules for virtual screen- ing in the chemical universe database gdb-13. Journal of the American Chemicul Society, 131(25))8732-8738) 2009. doi: 10. 1021//9900230. URL httph://tss/t /taas://do.../ .eriilorg//10 oorg/10.1021.
ja902302h PMID: 19505099.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
M. Cerezo, Guillaume Verdon, Hsin- Yuan Huang, Lukasz Cincio, and Patrick J. Coles. Challenges and opportunities quantum machine learning. Nature Computational Science, 2(9):567-576, Sep 2022. ISSN 2662-8457. doi: 10. 00188443588-022-0003 10. NO.1038//435588 022 00311-3
URL https: //coi. org/
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 3438-3445, 2020.
SR Clark, C Moura Alves, and D Jaksch. Efficient generation of graph states for quantum computa- tion. New Journal of Physics, 7(1):124, 2005.
Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algo- rithm. arXiv preprint 1eXiv:1411.4022, 2014.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. 2017.
William L. Hamilton. Graph representation learning Synthesis Lectures on Artificial Intelligence and Machine Learning, 14(3):1-159.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs, 2018.
Zaïd Harchaoui and Francis Bach. Image classification with segmentation graph kernels. In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2007.
Loic Henriet, Lucas Beguin, Adrien Signoles, Thierry Lahaye, Antoine Browaeys, Georges-Olivier Reymond, and Christophe Jurezak. Quantum computing with neutral atoms. Quantum, 4:327, 2020.
Louis-Paul Henry, Slimane Thabet, Constantin Dalyac, and Loic Henriet. Quantum evolution kernel: Machine learning graphs with programmable arrays of qubits. Phys. Rev. A, 104:032416, Sep 2021. doi: 10. 1a.1100/hysscc..10...22.... 11 0.03/ 1103/hyyseev. 1 04. 632416
URL htt.httts://// //linkk aps wwtp:///oo//oo////o/o/////////o/
10

---

Under review as a conference paper at ICLR 2023
Hsin- Yuan Huang, Michael Broughton, Jordan Cotler, Sitan Chen, Jerry Li, Masoud Mohseni, Hart- mut Neven, Ryan Babbush, Richard Kueng, John Preskill, and Jarrod R. McClean. Quantum advantage in learning from experiments. Science, 376(6398): 1186 2022. doi: 10.1126/
ence. science.abn7295. URL /ttp://tttppp///ccaaaaaeeaee/rrr abn3
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 1609.02907 2016.
doi: 10.48550/ARXW..160.0222 URL
mittps://ate /ttss///axxvv.oo org/ abs 609. 02907
Monika I Konaklieva. Molecular targets of (-lactam-based antimicrobials: beyond the usual sus-
pects. Antibiotics, 3(2):128-142, 2014.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Re- thinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 14:21618-21629, 2021.
Oleksandr Kyriienko and Vincent Elfving. Generalized quantum circuit differentiation rules. Physical Review A, 104(5):052417, 2021.
Kosuke Mitarai, Makoto Negoro, Masahiro Kitagawa, and Keisuke Fujii. Quantum circuit learning. Physical Review A, 98(3):032309, 2018.
Gré goire Montavon, Matthias Rupp. Vivekanand Gobre, Alvaro Vazquez-Mayagoitaa, Katja Hansen, Alexandre Tkatchenko, Klaus-Robert Müller, and O Anatole von Lilienfeld. Ma-
chine learning of molecular electronic properties in chemical compound space. New Journal of Physics, 15(9):095003, sep 2013. doi:
URL https:
//doi. org/ 10. 10 108882011111 367 ---367-66 220--663002 O2F 0122222211229999900000
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp. 4602 4609, 2019.
Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
Shirui Pan, Xingquan Zhu, Chengqi Zhang, and Philip S. Yu. Graph stream classification using labeled and unlabeled graphs. In 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 398-4094 2013. doi: 10.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Ali Rahimi and Benjamin Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. Advances in neural information processing systems, 21, 2008
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. arXiv preprint arXiv:2205. 10.00.22445 12454, 2022.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Niels da Vitoria Lobo, Takis Kasparis, Fabio Roli, James T. Kwok, Michael Georgiopoulos, Georgios C. Anagnostopoulos, and Marco Loog (eds.), Structural, Syn- tactic, and Statistical Pattern Recognition, pp. 287-297, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg. ISBN 978-3-540-89688)
Alvaro Sanchez-Gonzabee Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovee, and Peter Battaglia. Learning to simulate complex physics with graph networks. In International Confer- ence on Machine Learning, pp. 8459-8468 PMLR, 2020.
Pascal Scholl, Michael Schuler, Hannah Williams, Alexander A Eberharter, Daniel Barredo, Kai- Niklas Schymik, Vincent Lienhard, Louis-Paul Henry, Thomas C Lang. Thienr Lahaye, et al. Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms. Nature, 595(7866): 233-238, 2021.
11

---

Under review as a conference paper at ICLR 2023
Maria Schuld, Kamil Brádler, Robert Israel, Daiqin Su, and Brajesh Gupt. Measuring the similarity of graphs with a gaussian boson sampler. Phys. Rev. A, 101:032314. Mar 2020. doi: 10.1000Phyy.ee...110.0022 PhysRevA. 1 01. 032314.
URL
Kai-Niklas Schymik, Bruno Ximenez, Etienne Bloch, Davide Dreon, Adrien Signoles, Florence Nogrette, Daniel Barredo, Antoine Browaeys, and Thierry Lahaye. In situ equalization of single-atom loading in large-scale optical tweezer arrays. Phys. Rev. A, 106:022611, Aug 2022. doi: 10.1103/PhysRev..06... 106.02211..
URL https: /tts://link../ wtw.://n.a....//////.aaaoo wttp://///oooooooo/ htt.ss//L...........oo..........
PhysRevA. 106. 022611
John Scott. Social network analysis: developments, advances, and prospects. Social network anal- ysis and mining, 1(1):21-26, 2011.
Ychui Tang, Junchi Yan, and Hancock Edwin. From Quantum Graph Computing to Quantum Graph Learning: Survey. arXiv e-prints, art. arXiv:2202.0980 09506, February 2022.
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111. 14522, 2021.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018.
Guillaume Verdon, Trevor McCourt, Enxhell Luzhnica, Vikash Singh, Stefan Leichenauer, and Jack Hidary. Quantum Graph Neural Networks. arXiv e-prints, art. arXiv:1909.12244 12264, September 2019.
Minjie Wang. Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song. Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: A graph-centrie, perfy-tperormmnt package for graph neural networks. arXiv preprint 190vv01909.0/3 2019.
David Wierichs, Josh Izaac, Cody Wang, and Cedric Yen- Yu Lin. General parameter-shit rules for quantum gradients. Quantum, 6:677, 2022.
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinherg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: A benchmark for molecular machine learn- ing, 2017. http:/ttt:///atttt http://s////aivvo.o////////0... 00564
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: arXiv:1810.00826. 2018.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems, 34:28877-28886 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020.
Marinka Zitnik, Monica Agrawal, and Jure Leskovec. Modeling polypharmacy side effects with graph convolutional networks. Bioinformatics, 34(13):445-ii46, 2018.
12

---

Under review as a conference paper at ICLR 2023
A EXECUTION ON A REAL QUANTUM DEVICE
Training the parameters of the quantum state
Computing the gradients of parameterized quantum circuits is challenge source of numerous search in the quantum computing community (Kyriienko & Eliving 2021 Wierichs et al. 2022 Banchi & Crooks 202T). Finite-difference methods fail because of the sampling noise of quantum measurements and the hardware noise. Some algorithms named parameter-shi -hiff rules were then cre- ated to circumvent this issue (Mitarai al. 2018). In some cases, the derivative of parameterized quantum state can be expressed as an exact difference between two other quantum states with the same architecture and other values of the parameters.
We detail here how we would compute the gradient in simple case of our architecture. Let H be hamiltonian, O an observable, (vo) an initial state. We introduce
lx(0) = (0) (wo) exp(-i0H) (bb)) (() (0) Ô (v))
(12)
(13)
is known (Wierichs et al. 2022) that f can be expressed as a trigonometric polynomial
f(0) au cos(wef bw cos(wif)
(14)
WEN
where Ω is a finite set of frequencies depending on the eigenvalues of H. In the case of H = Hm. the frequencies are the integers between and N. One can then evaluate f on 2NV + 1 points and solve the linear equations to determine {aw J. { and the derivative of f. This is the same for the He hamiltonian which associated frequencies are the integers between 0 and [g]-
For the other hamiltonians listed, there is no known analytical formula to compute the gradients like previously. The only method would be to finite difference schemes which are sensitive noise.
Alternate training
At the time of this work, quantum resources are very expensive, we want limit ourselves in the number of access to the QPU. One way to do so is not to update every parameter at each epoch. Typically the gradients of the quantum parameters are expensive compute so the update would be less frequent. Due to the decoupling between the quantum and classical parameters, one is able to compute the gradients of the weights matrix with only the quantum attention matrices stored in memory.
Random parameters
Optimizing over the quantum parameters can be costly and ineffective with current quantum hard- ware. Even with emulation, back-propagating the loss through a system of more than 20 qubits is very difficult. We encounter memory errors for more than 21 qubits our A A100 GPUs, even though our implementation is certainly not optimal. Therefore we propose an alternative scheme to model, to help with both actual hardware implementations and classical emulation.
The main idea in the spirit of (Rahimi & Recht 2008) is to evaluate the attention matrices on many random quantum parameters, and only training the classical weights. From model fa; W, 0) Nheade
( with one layer, we would normally find the parameters that minimize a loss between inputs æ and labels y
W 0" arg max
(15)
W.B
Instead, we create a model with more heads and fixed random values. O' expressed f(x W, 0')
Nheaus (((A and we minimize only on 0
M
W = arg max
Σ
(16)
13

---

Under review as a conference paper at ICLR 2023
B SUPPLEMENTARY INFORMATION ABOUT EXPERIMENTS
B.1 DETAILS ABOUT DATASETS USED
B.1.1
QM7 AND QM9 MOLECULES AND GRAPII REGRESSION
Context
QM7 dataset is a subset of the GDB-13 database (Blum & Reymond 2009). a database of nearly 1 billion stable and synthetically accessible organic molecules, containing up seven heavy atoms (C, N, O, S). Similarly QM9 is subset the GDB-17 1-7 database consisting of molecules with up to nine heavy atoms. Learning methods using QM7 and QM9 are predicting the molecules electronic properties given stable conformational coordinates.
QM7 figures
QM7 consists of 7165 molecule graphs. Each node is an atom with its 3D coordinates and atomic number Z. The only edge feature is the entry of the Coulomb matrix. Each graph thus fully connected and has one regression target corresponding to its atomization energy.
QM9 figures
QM9 consists of 130831 molecule graphs of between 1 and 29 nodes with an average of 18 nodes (see Figure 66. Each node an atom with its 3D coordinates and its atomic number 7. Edges are purely distance based and have feature. Each graph is thus fully connected and has 12 regression targets corresponding to diverse chemical electronic properties. In our implementation, all the targets recentered and rescaled by their standard deviation.
Number of nodes distribution
40000
30000
Count
20000
0
10
15
20
25
30
Number nodes
Figure 6: Distribution of the number of nodes graph for QM9 dataset.
Benchmarks On the QM7 dataset, Quantum Machine benchmark reached MAE of 3.5 and 9.9 (Montavon al. 2013).
The best models of the MoleculeNet benchmark (Wu al. 2017) reached a test MAE of 2.86 0.25 on QM7 and 2.4 + 1.1 on QM9.
1.1.2 DBLP.V1 AND NODE CLASSIHICATION
Context
DBLP_v1 is graph stream built out the DBLP dataset (Pan et al. 2013) consisting bibliogra- phy data in computer science. To build graph stream, list of conferences from DBDM (database and data mining) and CVPR (computer vision and pattern recognition) fields are selected (as shown then used (in chronological order) to
in Table 2p. The papers published in these conferences form a binary-class graph stream where the classification task is to predict whether a paper belongs to DBDM CVPR field by using the references and the title of each paper.
14

---

Under review as a conference paper at ICLR 2023
Conf. category DBDM
Conferences
Paperss
#Graphs 9530
SIGMOD, VLDB, ICDE, EDBT,
20601
PODS, DASFAA, SSDBM, CIKM,
DEXA, KDD, ICDM, SDM,
PKDD, PAKDD
CVPR
ICCV, CVPR, ECCV, ICPR, ICIP, 18366
9926
ACM Multimedia, ICME
Table 2: DBLP.v/ vl details.
Papers without references filtered out. Then, the top 1000 most frequent words (excluding stop words) in titles are used as keywords to construct the graph (see Figure 7).
Query
P.101
Data
Large
P.100
Mining
Stream
Batch
P.102
Figure 7: Graph representation for a paper (P.100) in the DBLP_vl dataset. The rectangles are paper ID nodes and circles are keyword nodes from titles. The paper P. P.100 cites (connects) paper P.101 and P.102, and P.100 has keywords Data, Stream, and Mining in its title. Paper P.101 has keyword Query its title, and P.10''s s title include keywords Large and Batch. For each paper, the keywords in the title are linked with each other
Figures
DBLP_vl v1 consists of 19456 graphs evenly split between the two groups conferences (the two classes) from 2 to 39 nodes with average of 10 nodes.
These graphs are actually local parts of a bigger graph. To perform node classification (on nodes representing paper), the local neighborhood of each graph is extracted and graph classification task is run.
There are types of edges:
0: paper - paper
1: keyword paper
2: keyword keyword
Node features only unique ID to be identified between multiple graphs (ef P.100 in Figure which will also appear in P.101 graph). There are 41325 unique IDs so keywords don't 't have a single keyword identifier among all graphs.
Benchmarks
DBLP.vi (Pan al. 2013 benchmarks show accuracy ranging between 0.55 and 0.80 in chunked graph stream classification setup.
Data augmentation
The map from IDs to topics and paper IDs also provided and has been used to perform data augmentation provide node features. USing Stanford GloVe word embedding pre-trained
15

---

Under review as a conference paper at ICLR 2023
Wikipedia 2014 and Gigaword 5 in a 50-dimension space, each topic node could be enriched with its embedding. boolean flag was also added to identify a node as a topic or not (a paper).
B.1.3 COMPUTER VISION: LETTERS GRAPH CLASSIFICATION
Context
Letters datasets (Riesen & Bunke 2008) are 3 datasets of distorted letter drawings with low, medium or high distorsion levels (see Figure ??). Only the 15 capital letters the Roman alphabet that consist of straight lines (A, E, F, H. K. L. M. N, T, V, W, X, Z, are represented. Distorted letter drawings are converted into graphs by representing lines by undirected edges and ending points of lines by nodes.
Figures
Node attributes their 2D positions and edges have attribute. The graphs uniformly dis- tributed over the 15 letters. We focused on the medium distorsion dataset consisting of 2250 graphs.
Benchmarks
Benchmark results from k-NN are given by (Riesen & Bunke 2008): 99.6% (low), 94.0% (medium), and 90.0% (high). The best classical algorithm we trained this dataset was GraphSAGE with results of 100% (low), 94.5% (medium), and 80% (high)).
B.1.4 GRAPHCOVERS AND THE WEISFEILER-LEEEE LEEMMAN ISOMORPHISM TEST
Context
As explained previously and illustrated in Section 3 and Figure 1 Graph Neural Networks expressiv- ity is related to the Weisfeiler-Lehman (WL) test. Recent work has been made to generate datasets of graphs undistinguishable by the WL test (Bamberger) 2022).
Figures
Using this work, generated small dataset of 6 non-isomorphic graphs of 21 nodes that can't be distinguished by GNNs. These 6 graphs are then split in 3 arbitrary classes. The task at hand consists being able to correctly distinguish. the classes on the train data.
Benchmarks
Even on the train data, as they can't distinguish between the graphs, usual GNNs are not able to leam as shown in (Bamberger 2022).
B.2 PROTOCOL
We implemented the models with a classical emulator of quantum circuits implemented pytorch (Paszke et al.) 2019) and with dgl (Wang et al. (2019), and ran them A100 GPUs. All experiments were done using one GPU, except QM9 which required 4. We used a Adam optimizer with learning rate .001, weight decay for 500 epochs. The quantum parameters were only updated every 10 epochs because of computation time. As an order of magnitude, one epoch of QM7 takes min with GPU, and one epoch of QM9 takes Ih with GPUs. Most of the time is allocated compute the quantum dynamic, the size of classical parameters has little effect on the compute time except for the 2048 hidden layers.
We compare our model to three architectures of message passing models GCN (Kipf & Welling, 2016). SAGE (Hamilton al.] 2018), GAT (Veličković et al., 2018). In order have fair com- parison between the models, employ similar hyperparameters for all of them. Each model has layers and head for multi-head ones like ours and GAT. We also report the results by compar- ing models that have the same number of hidden neurons per layer and therefore approximately the same number of parameters. Each dataset randomly split in train, validation, test with respective ratios of 8, .I, .I and the models are run on 5 seeds, except QM9 for which we have only one seed.
B.3 RAW LOSSES FOR RACH MODEL.
16

---

Under review as a conference paper at ICLR 2023
Table Raw losses for each model
dataset breadth
DBLP
Letter-med
QM7
QM9
model
128
0.08 0.00
0.22 0.02
6..27
0.00
512
0.08 # 0.01
0.20
6..52
3.00
GAT
1024
0.08 0.01
0.21
2.70
0.00
2048
0.08 # 0.00
0.19
59.27
0.00
128
0.00
0.20
4.750
4.22
512
0.01
0.06
63.30
3.00
GCN
1024
0.01
0.15
2.99
0.00
2048
0.01
0.14
60.70
0.00
128
0.08
0.00
6.50
512
0.08 0.00
0.04
70.09
6.23
GTQC
1024
0.08 + 0.01
0.67 0.06
16.78
5.27 4.15
2048
0.08 0.00
0.06
2.488
5.30
32
0.00
0.00
$0.00
0.00
GTQC random
0.00
0.00
0.00
0.00
128
0.08 0.01
0.00
92.2
2.04
0.01
0.09
62.30
3.26
512
0.07
0.09
63.47
2.00
SAGE
1024
0.07
0.09
61.00
2.20
2048
0.08 0.01
0.09
5..41
0.00
17


Reviews:
[{"review_id": "zDjX86UvoX", "reviewer": "Reviewer_w3FW", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed a quantum computing-based Graph Transformer architecture. The authors illustrate that their model outperforms the 1-WL test by finding the ground state energy of the Ising Hamiltonian. They also implement their algorithm on the classical computer and conduct experiments on some classical graph tasks. Experimental results show that their model is comparable to other GNN architectures.", "summary_of_the_review": "The way of improving graph transformers is interesing but the current quality of the work, especially the empirical results, are not ready to publish in the venue, and I recommend rejection.", "strength_and_weaknesses": "Pros: \n1.\tIt’s interesting to combine quantum computing with Graph Neural Networks.\n2.\tThe authors show another way to construct an attention map, which may bring some inspiration.\n\nCons:\n\n[Whether the requirements.are realizable] \n\nThe proposed algorithm requires a large reliable quantum computer. The authors claimed that their algorithm outperforms the 1-WL test, which is illustrated by finding the ground state for some particular physical system. However, finding the ground state of some strongly correlated systems is proven intractable for classical computers (i.e., NP-hard [1]). Thus, it is hard to say that their algorithm also works well on a classic computer in practical applications. \n\n[No theoretical guarantee on classic computer]. \n\nIt’s great to design an algorithm that only works well on a quantum computer and enjoys better expressiveness. However, in the current stage, using a reliable quantum system is not realistic. Given this, the authors need to justify that their model outperforms GNN state-of-the-art variants (e.g., ESAN[2]). Therefore, the significance of the algorithm is questionable.\n\n[1] F. Barahona, J. Phys. A 15, 3241 (1982)\n[2] Beatrice Bevilacqua et al. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022.\n\n[Experimental results]\n\nThe author compared their model with several out-of-date baseline methods but showed superior performance. The method needs improvement, and the authors should include strong baselines for comparisons, such as TorchMD-Net and ESAN.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "W46jQ3KwEo", "reviewer": "Reviewer_fcGg", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In this paper, a new quantum enhanced GNN is proposed from the perspective of quantum mechanics. The paper regards the graph as a quantum system, transforms the graph topology into the interaction of a group of qubits, and uses the long-range correlation of the quantum system to calculate the relationship between different vertex to form the aggregation weight of GNN. The author illustrates the advantages of graph quantum states compared with traditional methods to obtain graph structures from three aspects. By rewriting the update mechanism of traditional GNN, the proposed model can distinguish some graph structures that are difficult to distinguish by traditional GNN. The experimental results show that this new model performs similarly to standard GNN architectures on different benchmarks.", "summary_of_the_review": "The experiments in this paper fail to prove the possible advantages of quantum graph GNN mentioned in Section 3. At the same time, the author does not give other capabilities of the model, which leads to the ambiguity of the meaning of the designed model. From this point of view, this paper should be rejected.", "strength_and_weaknesses": "**Strengths：**\n- This paper extends graph transformers with quantum computed aggregation and introduce a GNN architecture where the aggregation weights are computed using the long-range correlations of a quantum system. The method this paper uses is novelty.\n- The goal of this paper is to explore new types of global structural features emerging from quantum physics that can be added to a GNN. And the author explains the reasons for adopting graph quantum state from three aspects. This makes the motivation clear.\n- The whole paper is clear in structure and content.\n\n**Weaknesses：**\n\nThe author mentioned that this method can easily detect some complex structures compared with traditional methods, and gave some special cases in Chapter 3, which is the motivation of the author to introduce the graph quantum states, but these special cases can not show that the graph structure detection ability of quantum graph GNN is greater than that of traditional methods. From the aspect of structure detection, this paper lacks the relevant experimental comparison with traditional methods in general situations, rather than the carefully constructed data in Section 6.1. If you want to show that the graph quantum state has better structure detection capability than traditional methods on some graphs, both two models in Section 6.1 have reached 100% accuracy, and the loss index based on this may not be convincing. At the same time, according to the results of comparative experiments on various tasks in Section 6.2, it is difficult to explain the advantages of this method compared with traditional methods, which is not enough to support the author's motivation. In addition, this paper does not prove other advantages of GTQC.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "65m7EWzDEpC", "reviewer": "Reviewer_FV73", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a new graph transformer architecture based on quantum computation. The main idea is to replace the typical attention matrix by a “quantum computable” attention matrix. The main motivation for such a proposal is easily getting access to graph features (such as maximum probability assignment from an antiferromagnetic Ising model) using quantum computation. The proposed algorithm is simulated under small scale experiments (graphs with up to 20 nodes) and shows comparable performance when compared to popular non-quantum coputation-based graph neural networks. ", "summary_of_the_review": "This paper proposes a new quantum computing-based architecture for graphs. Although I am a non-expert in quantum computing, I do not think this paper brings clear contribution to the machine learning community in current form. ", "strength_and_weaknesses": "Strength 1: Designing neural network architectures for quantum processing is an active & significant area of research.\n\nStrength 2: To my knowledge, this paper is the first to propose quantum computer-version of graph transformers.\n\nWeakness 1: While the paper mainly focuses on introducing new global graph features, the benefit of introducing additional feature, e.g., better expressive power or empirical performance, is not clear. \n\nWeakness 2: The motivating example is not very convincing since I think the example (samples from antiferromagnetic Ising model) can be obtained using existing graph neural network. Samples (or labels) from antiferromagnetic Ising model can be framed as samples from a probabilistic graphical model (PGM). Obtaining such a sample has been well-studied in the context of structured prediction, e.g., graph Markov neural network.\n\nWeakness 3: The paper does not empirically compare with the existing quantum graph neural network, hence the contribution of this paper as a “new quantum neural network for graphs” is not clear.\n\nWeakness 4: This paper only computes the attention matrix using quantum processing units and requires CPU or GPU for other operations. It is not clear how the whole architecture can be efficiently implemented in practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject