Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data, but training and inference on large graphs are often bottlenecked by memory constraints and sparse linear-algebra workloads. Quantum computing offers an alternative set of primitives that may improve scalability for graph learning. Building on the quantum graph neural network (QGNN) framework of Liao \textit{et al.}, this work implements two representative architectures --- the Simplified Graph Convolution (SGC) and Linear Graph Convolution (LGC) models --- and evaluates them on open benchmark graph datasets and semi-supervised learning tasks using quantum simulation. We compare predictive performance and optimization behavior against classical baselines, showing that the quantum models achieve competitive performance with fewer parameters. Finally, we present a cost gradient analysis that identifies the tasks for which the models showcased are trainable. This is followed by a classical simulability study to find regimes in which the proposed circuits remain robust during training.
AI Summary
The paper studies implementations and trainability of quantum simplified and linear graph convolutional networks (QSGC and QLGC), building on an existing QGNN framework. Node features are amplitude-encoded; graph propagation uses block-encoded adjacency powers or polynomial filters, while a variational unitary replaces the classical weight matrix. Training minimizes a real-overlap surrogate rather than softmax cross-entropy. QLGC filters are constructed using QSVT and LCU.
Noiseless simulations compare these models with classical counterparts on five node-classification benchmarks, averaging over five initializations. QSGC reaches 91.2% accuracy on Karate Club, versus 88.2% for the best classical model. Classical models perform best on the other four datasets; on Cora, the best quantum accuracy is 67.8%, versus 78.8% classically. Quantum feature transformations use $3\ell\lceil\log_2 C\rceil$ parameters rather than $CF_K$. QLGC simulations evaluate effective filters, not compiled QSVT/LCU circuits.
Under regular-graph and independently sampled multihot-input/one-hot-target assumptions, the analysis gives expected gradient-variance bounds scaling as $\Omega((NC)^{-1})$ and $O(C^{-1})$, with the lower bound restricted to selected ansätze. A typical-ansatz estimate is $\Theta(C^{-2}+(NC)^{-1})$, motivating compact-feature regimes. The semi-supervised extension assumes a nonvanishing labeled fraction. Low-rank dequantization yields stated time and space costs $O(\log^2(N)r^{16.5}+Cr^{6.5})$ and $O(r^{11}+C^2)$.
The paper distinguishes variational parameter savings from end-to-end advantage: loading and compilation can eliminate computational gains, and favorable complexity comparisons assume efficient data access. Hardware execution, noise effects, nonlinear activations, and tighter trainability guarantees remain outside the demonstrated results.
Some signs of AI-generated textIncrementalStrong assumptionsMissing comparisonPossible error
Central claim may not hold: The selected Karate quantum models have more trainable parameters than their selected classical counterparts: 144 versus 136 for SGC and 290 versus 140 for LGC.
The reported Karate accuracies cannot be five-run means on the stated 20-node test set, and the text inconsistently describes the experimental supervision protocol.
The trainability results concern dataset-averaged variances under restrictive assumptions and do not establish the broader dataset-specific robustness claimed in the discussion.
The extension to all QGCNs incorrectly treats arbitrary polynomial filters as nonnegative normalized adjacency matrices and does not establish trainability of the LGC model's QSP-phase parameters.
The lemma asserting that commuting normalized adjacency matrices have proportional degree matrices is false without additional assumptions, as demonstrated by the identity and an irregular graph.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data, but training and inference on large graphs are often bottlenecked by memory constraints and sparse linear-algebra workloads. Quantum computing offers an alternative set of primitives that may improve scalability for graph learning. Building on the quantum graph neural network (QGNN) framework of Liao \textit{et al.}, this work implements two representative architectures --- the Simplified Graph Convolution (SGC) and Linear Graph Convolution (LGC) models --- and evaluates them on open benchmark graph datasets and semi-supervised learning tasks using quantum simulation. We compare predictive performance and optimization behavior against classical baselines, showing that the quantum models achieve competitive performance with fewer parameters. Finally, we present a cost gradient analysis that identifies the tasks for which the models showcased are trainable. This is followed by a classical simulability study to find regimes in which the proposed circuits remain robust during training.
The paper studies implementations and trainability of quantum simplified and linear graph convolutional networks (QSGC and QLGC), building on an existing QGNN framework. Node features are amplitude-encoded; graph propagation uses block-encoded adjacency powers or polynomial filters, while a variational unitary replaces the classical weight matrix. Training minimizes a real-overlap surrogate rather than softmax cross-entropy. QLGC filters are constructed using QSVT and LCU.
Noiseless simulations compare these models with classical counterparts on five node-classification benchmarks, averaging over five initializations. QSGC reaches 91.2% accuracy on Karate Club, versus 88.2% for the best classical model. Classical models perform best on the other four datasets; on Cora, the best quantum accuracy is 67.8%, versus 78.8% classically. Quantum feature transformations use 3ℓ⌈log2C⌉ parameters rather than CFK. QLGC simulations evaluate effective filters, not compiled QSVT/LCU circuits.
Under regular-graph and independently sampled multihot-input/one-hot-target assumptions, the analysis gives expected gradient-variance bounds scaling as Ω((NC)−1) and O(C−1), with the lower bound restricted to selected ansätze. A typical-ansatz estimate is Θ(C−2+(NC)−1), motivating compact-feature regimes. The semi-supervised extension assumes a nonvanishing labeled fraction. Low-rank dequantization yields stated time and space costs O(log2(N)r16.5+Cr6.5) and O(r11+C2).
The paper distinguishes variational parameter savings from end-to-end advantage: loading and compilation can eliminate computational gains, and favorable complexity comparisons assume efficient data access. Hardware execution, noise effects, nonlinear activations, and tighter trainability guarantees remain outside the demonstrated results.
Graph Neural Networks (GNNs) are powerful machine learning models that excel at analyzing structured data represented as graphs, demonstrating remarkable performance in applications like social network analysis and recommendation systems. However, classical GNNs face scalability challenges when dealing with large-scale graphs. This paper proposes frameworks for implementing GNNs on quantum computers to potentially address the challenges. We devise quantum algorithms corresponding to the three fundamental types of classical GNNs: Graph Convolutional Networks, Graph Attention Networks, and Message-Passing GNNs. A complexity analysis of our quantum implementation of the Simplified Graph Convolutional (SGC) Network shows potential quantum advantages over its classical counterpart, with significant improvements in time and space complexities. Our complexities can have trade-offs between the two: when optimizing for minimal circuit depth, our quantum SGC achieves logarithmic time complexity in the input sizes (albeit at the cost of linear space complexity). When optimizing for minimal qubit usage, the quantum SGC exhibits space complexity logarithmic in the input sizes, offering an exponential reduction compared to classical SGCs, while still maintaining better time complexity. These results suggest our Quantum GNN frameworks could efficiently process large-scale graphs. This work paves the way for implementing more advanced Graph Neural Network models on quantum computers, opening new possibilities in quantum machine learning for analyzing graph-structured data.
Graphs provide a natural language for relational data in chemistry, biology and optimisation. Graph neural networks (GNNs) have driven much of the recent progress in learning from such data through message passing, a single primitive that generalises convolution and attention. Quantum counterparts have been proposed, but with limited connection to message passing and few guarantees on performance or scalability. More broadly, the trainability of variational quantum circuits is a recognised bottleneck for their wide applicability, and pre-training has emerged as one way to address it. Yet for a quantum model to be useful, it must offer expressivity guarantees along with demonstrable scalability. Here we show how a quantum graph neural network can be built to perform message passing, to be permutation equivariant, and to sit at a chosen level of the Weisfeiler-Leman hierarchy, the standard measure of how finely a model can tell graphs apart. We show that, as for classical GNNs, the training can be done first on small graph instances, allowing for a pre-training that can mitigate usual training issues, and its output can be read out at a cost that stays low as the graph grows. We validate the framework in large-scale simulations of up to 56 qubits across three datasets, on synthetic graphs that ordinary message passing cannot separate, on molecular property prediction, and on the travelling salesperson problem. Our framework opens a path for near-term quantum algorithms with theoretical guarantees and practical scalability, bringing the principles of graph learning into quantum circuit design.
Graph Neural Networks (QGNNs) offer a promising approach to combining quantum computing with graph-structured data processing. While classical Graph Neural Networks (GNNs) are scalable and robust, existing QGNNs often lack flexibility due to graph-specific quantum circuit designs, limiting their applicability to diverse real-world problems. To address this, we propose a versatile QGNN framework inspired by GraphSAGE, using quantum models as aggregators to generate quantum-native node embeddings. We integrate inductive representation learning techniques with parameterized quantum convolutional and pooling layers, bridging classical and quantum paradigms. The convolutional layer is flexible, allowing tailored designs for specific tasks. Benchmarked on a node regression task with the QM9 dataset, our framework, using a single minimal circuit for all aggregation steps, handles molecules with varying numbers of atoms without changing qubits or circuit architecture. While classical GNNs achieve higher training performance, our quantum approach remains competitive and often shows enhanced generalization as molecular complexity increases. We also observe faster learning in early training epochs. To mitigate trainability limitations of a single-circuit setup, we extend the framework with multiple quantum aggregators on QM9. Assigning distinct circuits to each hop substantially improves training performance across all cases. Additionally, we numerically demonstrate the absence of barren plateaus as qubit numbers increase, suggesting that the proposed model remains trainable to larger, more complex graph-based problems.
Abstract Graph neural networks (GNNs) are effective for processing graph-structured data but face challenges with large graphs due to high memory requirements and inefficient sparse matrix operations on GPUs. Quantum computing offers a promising avenue to address these issues and inspires new algorithmic approaches. In particular, quantum GNNs (QGNNs) have been explored in recent literature. However, current quantum hardware limits the dimension of the data that can be effectively encoded. Existing approaches either simplify datasets manually or use artificial graph datasets. This work introduces the guided graph compression (GGC) framework, which uses a graph autoencoder to reduce both the number of nodes and the dimensionality of node features. The compression is guided to enhance the performance of a downstream classification task, which can be applied either with a quantum or a classical classifier. The framework is evaluated on the Jet Tagging task, a classification problem of fundamental importance in high energy physics that involves distinguishing particle jets initiated by quarks from those by gluons. We compare GGC to a model that uses the autoencoder as a preprocessing step and to a baseline classical GNN classifier. Our numerical results demonstrate that GGC outperforms both alternatives, while also facilitating the testing of novel QGNN ansatzes on realistic datasets.
Graph Neural Networks (GNNs) are effective for analyzing graph-structured data but face challenges with large graphs due to high memory requirements and inefficient sparse matrix operations on GPUs. Quantum Computing (QC) may be used to overcome these problems. For instance, Quantum Graph Neural Networks (QGNNs) have already been implemented in the literature. However, current quantum hardware limits the dimensionality of the datasets that can be encoded. For this reason, previous works simplify graph datasets manually or use small synthetic datasets. This work introduces the Guided Graph Compression (GGC) framework. It uses a graph autoencoder to reduce the size of graphs in terms of number of nodes and node feature dimensionality. The compression is guided towards enhancing the performance of a classification task by coupling the loss functions of the autoencoder and the classifier. The framework is applied to the Jet Tagging task that is relevant at CERN's LHC. It involves classifying jets as being originated from quarks or gluons. It is tested on three different training paradigms. First, a classical GNN is trained using the uncompressed data. Then, graph autoencoders are trained as a separate preprocessing step and used for classical and quantum classifiers. Lastly, the GGC framework is applied to both types of classifiers. Results show that the GGC framework outperforms the other two paradigms. Moreover, the classical and quantum classifiers achieve competitive performance in terms of ROC-AUC score.
The rapid growth in the size of Graph Convolutional Neural Networks (GCNs) encounters both computational- and memory-wall on classical computing platforms (e.g., CPU, GPU, FPGA, etc.). Quantum computing, on the other hand, provides extremely high parallelism for computation. Although quantum neural networks have been recently studied, the research on quantum graph neural networks is still in its infancy. The key challenge here is how to integrate both the graph topology information and the learning ability of GCNs into quantum circuits. In this work, we leverage the Givens rotations and its quantum implementation to encode graph information; in addition, we employ the widely used variational quantum circuit to bring the learnable parameters. On top of these, we present a full-quantum design of Graph Convolutional Neural Networks, namely "QuGCN", for semi-supervised learning on graph-structured data. Experiment results show our design is competitive with classical GCNs in terms of node classification accuracy on Cora sub-dataset. More importantly, we show the potential advantages that can be achieved by the proposed quantum GCN design when the number of features grows.