Quantum Graph Neural Networks
Guillaume Verdon Trevor McCourt Enxhell Luzhnica Vikash Singh Stefan Leichenauer Jack Hidary


Unitary vs pseudo-unitary time evolution and statistical effects in the dynamical Sauter-Schwinger process
    J. Z. Kamiński
    December 30, 2023
==========================================================================================================




We introduce Quantum Graph Neural Networks (qgnn), a new class of quantum neural network ansatze which are tailored to represent quantum processes which have a graph structure, and are particularly suitable to be executed on distributed quantum systems over a quantum network. Along with this general class of ansatze, we introduce further specialized architectures, namely, Quantum Graph Recurrent Neural Networks (qgrnn) and Quantum Graph Convolutional Neural Networks (qgcnn). We provide four example applications of qgnns: learning Hamiltonian dynamics of quantum systems, learning how to create multipartite entanglement in a quantum network, unsupervised learning for spectral clustering, and supervised learning for graph isomorphism classification. 



 


§ INTRODUCTION
 


Variational Quantum Algorithms are a promising class of algorithms that are rapidly emerging as a central subfield of Quantum Computing <cit.>. Similar to parameterized transformations encountered in deep learning, these parameterized quantum circuits are often referred to as Quantum Neural Networks (QNNs). Recently, it was shown that QNNs that have no prior on their structure suffer from a quantum version of the no-free lunch theorem <cit.> and are exponentially difficult to train via gradient descent. Thus, there is a need for better QNN ansatze. One popular class of QNNs has been Trotter-based ansatze <cit.>. The optimization of these ansatze has been extensively studied in recent works, and efficient optimization methods have been found <cit.>. On the classical side, graph-based neural networks leveraging data geometry have seen some recent successes in deep learning, finding applications in biophysics and chemistry <cit.>. Inspired from this success, we propose a new class of Quantum Neural Network ansatz which allows for both quantum inference and classical probabilistic inference for data with a graph-geometric structure. In the sections below, we introduce the general framework of the qgnn ansatz as well as several more specialized variants and showcase four potential applications via numerical implementation.




  - Many quantum processing chips have restricted or non-grid topologies

   - Need for quantum neural network ansatz which takes into account the communication overhead and fits directly on the topology of the network or chip

  - In the case of quantum chips, two-qubit gates remain the fidelity bottleneck, while in the case of quantum networks, two-node operations require rounds of inter-node communication.

  - Graph neural networks have seen a large growth in the number of areas of application on the classical side.

  - Generally these have degrees of freedom on both the nodes and edges of the network

  - In our case, the restriction to networks with quantum degrees of freedom on the nodes only reduces the overall volume of quantum memory needed. 

  - By having the edges be classsical and the nodes quantum, we open up the possibilty of extracting insights about various quantum systems of interest without having to simulate an entire volume of space as a grid.









§ BACKGROUND



 §.§ Classical Graph Neural Networks

Graph Neural Networks (gnns) date back to <cit.> who applied neural networks to acyclic graphs. <cit.> and <cit.> developed methods that learned node representations by propagating the information of neighbouring nodes. Recently, gnns have seen great breakthroughs by adapting the convolution operator from cnns to graphs <cit.>. Many of these methods can be expressed under the message-passing framework <cit.>.

Let graph =(,) where ∈^n × n is the adjacency matrix, and ∈^n × d is the node feature matrix where each node has d features. 


    ^(k) = P(, ^(k-1), ^(k))


where ^(k)∈^n × d are the node representations computed at layer k, P is the message propagation function and is dependent on the adjacency matrix, the previous node encodings and some learnable parameters ^(k). The initial embedding, ^(0), is naturally . One popular implementation of this framework is the gcn <cit.> which implements it as follows: 


    ^(k) = P(,^(k-1), ^(k)) = (^-1/2^-1/2^(k-1)^(k-1))


where =  + is the adjacency matrix with inserted self-loops and = ∑_j_ij is the renormalization factor (degree matrix).



 §.§ Networked Quantum Systems
 Consider a graph 𝒢 = {𝒱,ℰ}, where 𝒱 is the set of vertices (or nodes) and ℰ the set of edges. We can assign a quantum subsystem with Hilbert space ℋ_v to each vertex in the graph, forming a global Hilbert space ℋ_𝒱≡⊗_v∈𝒱ℋ_v. Each of the vertex subsystems could be one or several qubits, a qudit, a qumode <cit.>, or even an entire quantum computer. One may also define a Hilbert space for each edge and form ℋ_ℰ≡⊗_e∈ℰℋ_e. The total Hilbert space for the graph would then be ℋ_ℰ⊗ℋ_𝒱. For the sake of simplicity and feasibility of numerical implementation, we consider this to be beyond the scope of the present work, so for us the total Hilbert space consists only of ℋ_𝒱. The edges of the graph dictate the communication between the vertex subspaces: couplings between degrees of freedom on two different vertices are allowed if there is an edge connecting them. This setup is called a quantum network <cit.> with topology given by the graph 𝒢.





§ QUANTUM GRAPH NEURAL NETWORKS




 §.§ General Quantum Graph Neural Network Ansatz
 The most general Quantum Graph Neural Network ansatz is a parameterized quantum circuit on a network which consists of a sequence of Q different Hamiltonian evolutions, with the whole sequence repeated P times:

    Û_qgnn(η, θ) = ∏_p=1^P [ ∏_q=1^Q e^-iη_pqĤ_q(θ)],

where the product is time-ordered <cit.>, the η and θ are variational (trainable) parameters, and the Hamiltonians Ĥ_q(θ) can generally be any parameterized Hamiltonians whose topology of interactions is that of the problem graph:

    Ĥ_q(θ) ≡∑_{j,k}∈ℰ∑_r∈ℐ_jk W_qrjkÔ^(qr)_j⊗P̂^(qr)_k+ ∑_v∈𝒱∑_r∈𝒥_v B_qrvR̂^(qv)_j.

Here the W_qrjk and B_qrv are real-valued coefficients which can generally be independent trainable parameters, forming a collection θ≡∪_q,j,k,r{W_qrjk}∪_q,v,r{B_qrjk}. The operators R̂^(qv)_j, Ô^(qr)_j, P̂^(qr)_j are Hermitian operators which act on the Hilbert space of the j^th node of the graph. The sets ℐ_jk and 𝒥_v are index sets for the terms corresponding to the edges and nodes, respectively. To make compilation easier, we enforce that the terms of a given Hamiltonian Ĥ_q commute with one another, but different Ĥ_q's need not commute.




In order to make the ansatz more amenable to training and avoid the barren plateaus (quantum parametric circuit no free lunch) problem <cit.>, we need to add some constraints and specificity. To that end, we now propose more specialized architectures where parameters are tied spatially (convolutional) or tied over the sequential iterations of the exponential mapping (recurrent).















 §.§ Quantum Graph Recurrent Neural Networks (qgrnn)
 We define quantum graph recurrent neural networks as ansatze of the form of (<ref>) where the temporal parameters are tied between iterations, η_pq↦η_q. In other words, we have tied the parameters between iterations of the outer sequence index (over p=1,…, P). This is akin to classical recurrent neural networks where parameters are shared over sequential applications of the recurrent neural network map. As η_q acts as a time parameter for Hamiltonian evolution under Ĥ_q, we can view the qgrnn ansatz as a Trotter-based <cit.> quantum simulation of an evolution e^-iΔĤ_eff under the Hamiltionian 
Ĥ_eff = Δ^-1∑_q η_qĤ_q for a time step of size Δ =‖η‖_1 = ∑_q |η_q|. This ansatz is thus specialized to learn effective quantum Hamiltonian dynamics for systems living on a graph. In Section <ref> we demonstrate this by learning the effective real-time dynamics of an Ising model on a graph using a qgrnn ansatz.


























 §.§ Quantum Graph Convolutional Neural Networks (qgcnn)


Classical Graph Convolutional neural networks rely on a key feature: that of permutation invariance. In other words, the ansatz should be invariant under permutation of the nodes. This is analogous to translational invariance for ordinary convolutional transformations. In our case, permutation invariance manifests itself as a constraint on the Hamiltonian, which now should be devoid of local trainable parameters, and should only have global trainable parameters. The θ parameters thus become tied over indices of the graph: W_qrjk↦ W_qr and B_qrv↦ B_qr. A broad class of graph convolutional neural networks we will focus on is the set of so-called Quantum Alternating Operator Ansatze <cit.>, the generalized form of the Quantum Approximate Optimization Algorithm ansatz <cit.>. 







 §.§ Quantum Spectral Graph Convolutional Neural Networks (qsgcnn)


We can take inspiration from the continuous-variable quantum approximate optimization ansatz introduced in <cit.> to create a variant of the qgcnn: the Quantum Spectral Graph Convolutional Neural Network (qsgcnn). We show here how it recovers the mapping of Laplacian-based graph convolutional networks <cit.> in the Heisenberg picture, consisting of alternating layers of message passing, node update, and nonlinearities.

Consider an ansatz of the form from (<ref>) with four different Hamiltonians (Q=4) for a given graph. First, for a weighted graph 𝒢 with edge weights Λ_jk, we define the coupling Hamiltonian as 
    Ĥ_C  ≡12∑_{j,k}∈ℰΛ_jk(x̂_j - x̂_k)^2.
 The Λ_jk here are the weights of the graph 𝒢, and are not trainable parameters. The operators denoted here by x̂_j are quantum continuous-variable position operators, which can be implemented via continuous-variable (analog) quantum computers <cit.> or emulated using multiple qubits on digital quantum computers <cit.>. After evolving by Ĥ_C, which we consider to be the message passing step, one applies an exponential of the kinetic Hamiltonian, Ĥ_K ≡12∑_j∈𝒱p̂_j^2. Here p̂_j denotes the continuous-variable momentum (Fourier conjugate) of the position, obeying the canonical commutation relation [x̂_j,p̂_j]=iδ_jk. We consider this step as a node update step.  In the Heisenberg picture, the evolution generated by these two steps maps the position operators of each node according to 
    e^-iγĤ_K e^-iαĤ_C :x̂_j↦x̂_j +γp̂_j -αγ∑_k∈𝒱 L_jkx̂_k,
  where 
    L_jk =δ_jk(∑_v∈𝒱Λ_jv) -Λ_jk
 is the Graph Laplacian matrix for the weighted graph 𝒢. We can recognize this step as analogous to classical spectral-based graph convolutions. One difference to note here is that momentum is free to accumulate between layers. 

Next, we must add some non-linearity in order to give the ansatz more capacity.[From a quantum complexity standpoint, adding a nonlinear operation (generated by a potential of degree superior to quadratic) creates states that are non-Gaussian and hence are non efficiently simulable on classical computers <cit.>, in general composing layers of Gaussian and non-Gaussian quantum transformations yields quantum computationally universal ansatz <cit.>. ]
The next evolution is thus generated by an anharmonic Hamiltonian Ĥ_A = ∑_j∈𝒱 f(x̂_j), where f is a nonlinear function of degree greater than 2, e.g., a quartic potential of the form f(x̂_j) =((x̂_j-μ)^2 - ω^2)^2 for some μ, ω hyperparameters. Finally, we apply another evolution according to the kinetic Hamiltonian. These last two steps yield an update 
    e^-iβĤ_K e^-iδĤ_A :x̂_j↦x̂_j +βp̂_j -δβ f'(x̂_j),
 which acts as a nonlinear mapping. By repeating the four evolution steps described above in a sequence of P layers, i.e., 

    Û_qsgcnn(α,β,γ, δ) = ∏_j=1^P e^-iβ_j Ĥ_K e^-iδ_j Ĥ_A e^-iγ_j Ĥ_K e^-iα_j Ĥ_C
with variational parameters θ = {α,β,γ, δ},
we then recover a quantum-coherent analogue of the node update prescription of  <cit.> in the original graph convolutional networks paper.[For further physical intuition about the behaviour of this ansatz, note that the sum of the coupling and kinetic Hamiltonians Ĥ_K+Ĥ_C is equivalent to the Hamiltonian of a network of quantum harmonic oscillators coupled according to the graph weights and network topology. By adding a quartic Ĥ_A, we are thus emulating parameterized dynamics on a harmonically coupled network of anharmonic oscillators.]






§ APPLICATIONS & EXPERIMENTS







 §.§ Learning Quantum Hamiltonian Dynamics with Quantum Graph Recurrent Neural Networks



Learning the dynamics of a closed quantum system is a task of interest for many applications <cit.>, including device characterization and validation. In this example, we demonstrate that a Quantum Graph Recurrent Neural Network can learn effective dynamics of an Ising spin system when given access to the output of quantum dynamics at various times.


Our target is an Ising Hamiltonian with transverse field on a particular graph, 
    Ĥ_target = ∑_{j,k}∈ℰ J_jkẐ_jẐ_k + ∑_v∈𝒱Q_vẐ_v + ∑_v∈𝒱X̂_j.
 We are given copies of a fixed low-energy state  |ψ_0⟩ as well as copies of the state |ψ_T⟩≡Û(T)|ψ_0⟩ = e^-i T Ĥ_target for some known but randomly chosen times T∈[0,T_max]. Our goal is to learn the target Hamiltonian parameters {J_jk, Q_v}_j,k,v∈𝒱 by comparing the state |ψ_T⟩ with the state obtained by evolving |ψ_0⟩ according to the qgrnn ansatz for a number of iterations P ≈ T/Δ (where Δ is a hyperparameter determining the Trotter step size). We achieve this by training the parameters via Adam <cit.> gradient descent on the average infidelity ℒ(θ) =  1-1B∑_j=1^B  |⟨ψ_T_j|U^j_qgrnn( Δ,θ)|ψ_0⟩||⟩^2 averaged over batch sizes of 15 different times T. Gradients were estimated via finite difference differentiation with step size ϵ =10^-4. The fidelities (quantum state overlap) between the output of our ansatz and the time-evolved data state were estimated via the quantum swap test <cit.>. The ansatz uses a Trotterization of a random densely-connected Ising Hamiltonian with transverse field as its initial guess, and successfully learns the Hamiltonian parameters within a high degree of accuracy as shown in Figure 1a. 













 §.§ Quantum Graph Convolutional Neural Networks for Quantum Sensor Networks



Quantum Sensor Networks are a promising area of application for the technologies of Quantum Sensing and Quantum Networking/Communication <cit.>. A common task considered where a quantum advantage can be demonstrated is the estimation of a parameter hidden in weak qubit phase rotation signals, such as those encountered when artificial atoms interact with a constant electric field of small amplitude <cit.>. A well-known method to achieve this advantange is via the use of a quantum state exhibiting multipartite entanglement of the Greenberger–Horne–Zeilinger kind, also known as a GHZ state <cit.>. Here we demonstrate that, without global knowledge of the quantum network structure, a qgcnn ansatz can learn to prepare a GHZ state. We use a qgcnn ansatz with Ĥ_1 = ∑_{j,k}∈ℰẐ_jẐ_k and Ĥ_2= ∑_j∈𝒱X̂_j. The loss function is the negative expectation of the sum of stabilizer group generators which stabilize the GHZ state <cit.>, i.e., 
    ℒ(η) = -⟨⊗_j=0^nX̂ +∑_j=1^n-1Ẑ_jẐ_j
    +1|_⟩η
 for a network of n qubits. Results are presented in Figure 1b. Note that the advantage of using a qgnn ansatz on the network is that the number of quantum communication rounds is simply proportional to P, and that the local dynamics of each node are independent of the global network structure. 

In order to further validate that we have obtained an accurate GHZ state on the network after training, we perform the quantum phase kickback test on the network's prepared approximate GHZ state <cit.>.[For this test, one applies a phase rotation ⊗_j∈𝒱 e^-iφẐ_j on all the qubits in paralel, then one applies a sequence of CNOTs (quantum adder gates) to concentrate the phase shifts onto a single collector node, m∈𝒱. Given that one had a GHZ state initially, one should then observe a phase shift e^-inφẐ_m where n = |𝒱|. This boost in frequency of oscillation of the signal is what gives quantum multipartite entanglement its power to increase sensitivity to signals to super-classical levels <cit.>.] We observe the desired frequency boost effect for our trained network preparing an approximate GHZ state at test time, as displayed in Figure <ref>.



 §.§ Unsupervised Graph Clustering with Quantum Graph Convolutional Networks

As a third set of applications, we consider applying the qsgcnn from Section <ref> to the task of spectral clustering <cit.>. Spectral clustering involves finding low-frequency eigenvalues of the graph Laplacian and clustering the node values in order to identify graph clusters. In Figure <ref> we present the results for a qsgcnn for varying multi-qubit precision for the representation of the continuous values, where the loss function that was minimized was the expected value of the anharmonic potential ℒ(η) = ⟨Ĥ_C + Ĥ_A|_⟩η. Of particular interest to near-term quantum computing with low numbers if qubits is the single-qubit precision case, where we modify the qsgcnn construction as p̂^2_j↦X̂_j,  Ĥ_A↦ I and x̂_j↦|1⟩⟨1|_j which transforms the coupling Hamiltonian as 

    Ĥ_C ↦12∑_{j,k}∈ℰΛ_jk(|1⟩⟨1|_j - |1⟩⟨1|_k)^2 = ∑_jk L_jk|1⟩⟨1|_j⊗|1⟩⟨1|_k,

where |1⟩⟨1|_k = (Î-Ẑ_k)/2. We see that using a low-qubit precision yields sensible results, thus implying that spectral clustering could be a promising new application for near-term quantum devices. 









 §.§ Graph Isomorphism Classification via Quantum Graph Convolutional Networks


Recently, a benchmark of the representation power of classical graph neural networks has been proposed <cit.> where one uses classical gcns to identify whether two graphs are isomorphic. In this spirit, using the qsgcnn ansatz from the previous subsection, we benchmarked the performance of this Quantum Graph Convolutional Network for identifying isomorphic graphs. We used the single-qubit precision encoding in order to order to simulate the execution of the quantum algorithms on larger graphs. 

Our approach was the following, given two graphs 𝒢_1 and 𝒢_2, one applies the single-qubit precision qsgcnn ansatz ∏_j=1^P e^iη_j Ĥ_Ke^iγ_j Ĥ_C with Ĥ_K= ∑_j∈𝒱X̂_j and Ĥ_C from (<ref>) in parallel according to each graph's structure. One then samples eigenvalues of the coupling Hamiltonian Ĥ_C on both graphs via standard basis measurement of the qubits and computation of the eigenvalue at each sample of the wavefunction. One then obtains a set of samples of “energies” of this Hamiltonian. By comparing the energetic measurement statistics output by the  qsgcnn ansatz applied with identical parameters θ = {η,γ} for two different graphs, one can then infer whether the graphs are isomorphic.

We used the Kolmogorov-Smirnoff test <cit.> on the distribution of energies sampled at the output of the qsgcnn to determine whether two given graphs were isomorphic. In order to determine the binary classification label deterministically, we considered all KS statistic values above 0.4 to indicate that the graphs were non-isomorphic. For training and testing purposes, we set the loss function to be ℒ(y, ) = (1-y)(1-) + y, where y=1 if graphs are isomorphic, and y=0 otherwise.

For the dataset, graphs were sampled uniformly at random from the Erdos-Renyi distribution G(n,p) with p=0.5 at fixed n. In all of our experiments, we had 100 pairs of graphs for training, 50 for validation, and 50 for testing, always balanced between isomorphic and non-isomorphic pairs. Moreover, we only considered graphs that were connected. The networks were trained via a Nelder-Mead optimization algorithm.

Presented in Figure <ref> is the training and testing losses for various graph sizes and numbers of energetic samples. In Tables 1 and 2, we present the graph isomorphism classification accuracy for the training and testing sets using the trained qgcnn with the previously described thresholded KS statistic as the label. We see we get highly accurate performance even at low sample sizes. This seems to imply that the  qgcnn is fully capable of identifying graph isomorphism, as desired for graph convolutional network benchmarks.

 








§ CONCLUSION & OUTLOOK


Results featured in this paper should be viewed as a promising set of first explorations of the potential applications of qgnns. Through our numerical experiments, we have shown the use of these qgnn ansatze in the context of quantum dynamics learning, quantum sensor network optimization, unsupervised graph clustering, and supervised graph isomorphism classification. Given that there is a vast set of literature on the use of Graph Neural Networks and their variants to quantum chemistry, future works should explore hybrid methods where one can learn a graph-based hidden quantum representation (via a qgnn) of a quantum chemical process. As the true underlying process is quantum in nature and has a natural molecular graph geometry, the qgnn could serve as a more accurate model for the hidden processes which lead to perceived emergent chemical properties. We seek to explore this in future work. Other future work could include generalizing the qgnn to include quantum degrees of freedom on the edges, include quantum-optimization-based training of the graph parameters via quantum phase backpropagation <cit.>, and extending the qsgcnn to multiple features per node.





  §.§.§ Acknowledgments

Numerics in this paper were executed using a custom interface between Google's Cirq <cit.> and TensorFlow <cit.>. The authors would like to thank Edward Farhi, Jae Yoo, and Li Li for useful discussions. GV, EL, and VS would like to thank the team at X for the hospitality and support during their respective Quantum@X and AI@X residencies where this work was completed. X, formerly known as Google[x], is part of the Alphabet family of companies, which includes Google, Verily, Waymo, and others (www.x.company). GV acknowledges funding from NSERC. 


unsrt


































































































































































































































































































































