Research map / Architectures and efficiency / RNNs and normalization
Scalable Quantum-Inspired Optimization Through Dynamic Qubit Compression
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.
Proposes GRANITE, a GNN-based method that iteratively merges or flip-merges spins predicted to be aligned or anti-aligned in ground states, compressing Ising models to fit D-Wave annealers while keeping high solution optimality.
Problem
Ising models for NP-hard combinatorial optimization often exceed the qubit capacity of near-term quantum annealers, and existing exact reduction methods (roof duality, graph heuristics) compress only a small fraction of instances.
Approach
Train a message-passing GNN with a logistic-regression edge head and a hybrid confidence-weighted BCE loss to predict ground-state alignment/anti-alignment of spin pairs, then iteratively merge or flip-merge the most confident edge, giving a tunable compression ratio.
Key results
- With 75% edge reduction at n=200, GRANITE keeps optimality of 91.07% (ER), 92.30% (BA), and 92.23% (WS) on D-Wave Advantage.
- Random merge/flip-merge baselines reach under 40% optimality across topologies, per the paper.
- Physical qubit counts drop to 5.3% (ER), 7.4% (BA), and 16.5% (WS) of original at 75% edge reduction for n=400.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Compress the original Ising model by 75% | GRANITE · Erdős-Rényi, n=200 | optimality: 96.77 ± 0.45 -> 91.07 ± 0.82 | Hurt |
| Compress the original Ising model by 75% | GRANITE · Barabási-Albert, n=200 | optimality: 97.25 ± 0.25 -> 92.30 ± 0.87 | Hurt |
| Compress the original Ising model by 75% | GRANITE · Watts-Strogatz, n=200 | optimality: 99.14 ± 0.14 -> 92.23 ± 0.53 | Hurt |
| Replace hybrid loss with BCE (ablation) | GRANITE · Erdős-Rényi, n=200, 75% edge reduction | optimality: 91.07 ± 0.82 -> 86.90 ± 1.08 | Hurt |
| Replace hybrid loss with MSE (ablation) | GRANITE · Erdős-Rényi, n=200, 75% edge reduction | optimality: 91.07 ± 0.82 -> 75.68 ± 3.85 | Hurt |
| Replace hybrid loss with softmax weighting (ablation) | GRANITE · Erdős-Rényi, n=200, 75% edge reduction | optimality: 91.07 ± 0.82 -> 89.68 ± 1.07 | Hurt |
| Replace hybrid loss with BCE (ablation) | GRANITE · Barabási-Albert, n=200, 75% edge reduction | optimality: 92.30 ± 0.87 -> 89.05 ± 1.35 | Hurt |
| Replace hybrid loss with MSE (ablation) | GRANITE · Barabási-Albert, n=200, 75% edge reduction | optimality: 92.30 ± 0.87 -> 92.07 ± 0.69 | No clear effect |
| Replace hybrid loss with softmax weighting (ablation) | GRANITE · Barabási-Albert, n=200, 75% edge reduction | optimality: 92.30 ± 0.87 -> 78.89 ± 2.44 | Hurt |
| Replace hybrid loss with BCE (ablation) | GRANITE · Watts-Strogatz, n=200, 75% edge reduction | optimality: 92.23 ± 0.53 -> 92.58 ± 0.30 | No clear effect |
| Replace hybrid loss with MSE (ablation) | GRANITE · Watts-Strogatz, n=200, 75% edge reduction | optimality: 92.23 ± 0.53 -> 94.02 ± 0.60 | Helped |
| Replace hybrid loss with softmax weighting (ablation) | GRANITE · Watts-Strogatz, n=200, 75% edge reduction | optimality: 92.23 ± 0.53 -> 92.60 ± 0.51 | No clear effect |
Surprising findings
- Deeper GNNs (4 and 5 layers) degrade performance relative to three layers, which the authors attribute to overfitting.
Limitations
- Evaluated only on random synthetic graphs, not real-world instances.
- Predicting edge alignment is shown to be co-NP-hard, so the learned predictor is heuristic with no guarantees.
- Solution quality degrades as graph size and compression ratio increase.
Experimental setup
Datasets: synthetic random Ising graphs (Erdős-Rényi, Barabási-Albert, Watts-Strogatz)
Benchmarks: synthetic Ising instances (ER, BA, WS) with n=25 to 400
Metrics: optimality (%) qubit reduction (%)
Baselines: random merge/flip-merge BCE loss MSE loss softmax weighting
Builds on: roof duality minorminer
Closest papers by meaning
- TensorRL-QAS: Reinforcement learning with tensor networks for improved quantum architecture search (NeurIPS 2025 · similarity 0.87)
- MG-Net: Learn to Customize QAOA with Circuit Depth Awareness (NeurIPS 2024 · similarity 0.86)
- PALQO: Physics-informed model for Accelerating Large-scale Quantum Optimization (NeurIPS 2025 · similarity 0.86)
- QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design (NeurIPS 2025 · similarity 0.86)
- AI-Powered Algorithm-Centric Quantum Processor Topology Design (AAAI 2025 · similarity 0.85)
- TITAN: A Trajectory-Informed Technique for Adaptive Parameter Freezing in Large-Scale VQE (NeurIPS 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.