Research map / Optimization / Distributed and compressed
Exponential Quantum Communication Advantage in Distributed Inference and Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that distributed inference and gradient estimation for a class of quantum-encoded (pipelined) models, including a quadratic graph neural network variant, admit exponential quantum communication advantage over classical randomized communication, and reports SIGN-based experiments on node and graph classification.
Problem
Reducing communication cost of distributed inference and gradient-based training for large models split across devices, by using quantum communication instead of classical bits.
Approach
Encodes data into quantum states passed between parties in a pipelined parameterized quantum circuit; gradient estimation reduces to shadow tomography with threshold search, giving polylogarithmic qubit communication, while classical lower bounds from communication complexity (Hidden Matching-type and boolean hidden partition problems) show an exponential gap for quadratic graph networks.
Key results
- x
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace PReLU with a degree-2 polynomial (ablation) | SIGN · ogbn-products node classification | accuracy: 79.48 $\pm$ 0.07 -> 78.51 $\pm$ 0.05 | Hurt |
| replace PReLU with a degree-2 polynomial (ablation) | SIGN · Reddit node classification | accuracy: 96.55 $\pm$ 0.02 -> 96.31 $\pm$ 0.03 | Hurt |
| replace PReLU with a degree-2 polynomial (ablation) | SIGN · Cora node classification | accuracy: 78.84 $\pm$ 0.37 -> 78.69 $\pm$ 0.26 | Hurt |
| replace PReLU with a degree-2 polynomial (ablation) | SIGN · ogbn-products decision problem | accuracy: 84.39 $\pm$ 1.73 -> 83.70 $\pm$ 1.48 | Hurt |
| replace PReLU with a degree-2 polynomial (ablation) | SIGN · Reddit decision problem | accuracy: 90.33 $\pm$ 0.33 -> 89.37 $\pm$ 0.60 | Hurt |
| replace PReLU with a degree-2 polynomial (ablation) | SIGN · Cora decision problem | accuracy: 88.10 $\pm$ 5.61 -> 87.14 $\pm$ 3.92 | Hurt |
Surprising findings
- Exponential quantum communication advantage does not hold for distributed linear classification, so amplitude encoding alone does not guarantee the advantage
- Models that work well on REDDIT-style datasets without node features seem to need at least two message-passing layers, as the shallow architecture underperforms there
Limitations
- Advantages require deep poly(N)-depth fault-tolerant quantum circuits, with unclear practical overhead
- Unclear to what extent powerful neural networks can be approximated by quantum circuits; the GNN evidence is for a shallow SIGN-like model
- Exponential advantage depends on the model output not decaying polynomially with N, and the paper's bounds for the classical side are for specific parameter regimes
Experimental setup
Datasets: ogbn-products Reddit Cora MUTAG PTC NCI1 PROTEINS COLLAB IMDB-BINARY IMDB-MULTI REDDIT-BINARY REDDIT-MULTI
Benchmarks: ogbn-products Reddit Cora MUTAG PTC NCI1 PROTEINS COLLAB IMDB-M REDDIT-M
Metrics: test accuracy validation accuracy
Baselines: GIN DropGIN DGCNN U2GNN HGP-SL WKPI SIGN (PReLU)
Builds on: SIGN shadow tomography parameter shift rule pipelining
Closest papers by meaning
- Exponential Hardness of Optimization from the Locality in Quantum Neural Networks (AAAI 2024 · similarity 0.87)
- Exploring channel distinguishability in local neighborhoods of the model space in quantum neural networks (ICLR 2025 · similarity 0.87)
- Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm (NeurIPS 2026 · similarity 0.86)
- Limitations of measure-first protocols in quantum machine learning (ICML 2025 · similarity 0.85)
- ATP: Adaptive Threshold Pruning for Efficient Data Encoding in Quantum Neural Networks (CVPR 2025 · similarity 0.85)
- eQMARL: Entangled Quantum Multi-Agent Reinforcement Learning for Distributed Cooperation over Quantum Channels (ICLR 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.