Speaker
Description
Graph Neural Networks (GNNs) have shown promise in solving complex graph-based optimization problems, with implementations on both classical and quantum computers. Whilst promising better scalability with the problem size thanks to the complex structure of Hilbert spaces, quantum GNNs are prone to untrainability; in particular, the barren plateau problem.
In this work, we provide a gradient analysis for a specific type of quantum GNN. As such, the approximate bounds and expected trend of the gradient variance indicate efficient trainability for problems concerned with classical graph size scalability. This comes at the cost of a barren plateau in the subsystem encoding the nodes’ features. Our results are validated by simulated experiments on two benchmarks.
Furthermore, we comment on possible regimes of advantage of the model. At the circuit level, there is a trade-off; advantage can be exponential in either space or time, or polynomial in both. This trade-off is significantly impacted by the classical compilation time of the circuit (the input problem). Therefore, a low-rank dequantization analysis adds constraints to the types of graphs the quantum GNN can provide an advantage for.
| Topic | Quantum variational circuits and their applications |
|---|