Scalable Quantum-Inspired Optimization Through Dynamic Qubit Compression

Co Tran, Quoc-Bao Tran, Truong-Son Hy, Thang N Dinh

TL;DR

This paper introduces GRANITE, a novel quantum-inspired framework that uses Graph Neural Networks (GNNs) to dynamically compress large Ising models. This compression allows complex optimization problems, typically too large for current quantum hardware, to be solved by fitting them onto available qubits while preserving solution quality.

What Problem Does This Paper Address?

Many challenging real-world problems, such as portfolio optimization and scheduling, can be framed as Ising models. While quantum computers, particularly quantum annealers, hold promise for solving these problems more efficiently than classical computers, a major bottleneck is the limited number of qubits available on current hardware. Furthermore, the connectivity between qubits on these devices often requires complex "minor embedding" techniques, further increasing the effective qubit count needed. Existing methods for reducing the size of Ising models are often heuristic, lack flexibility in compression levels, and can lead to significant losses in solution quality. This paper addresses the critical need for a scalable and flexible method to compress Ising models to match the constraints of near-term quantum hardware, thereby bridging the gap between problem complexity and computational capacity.

Methods

The core of the proposed solution is a framework called GRANITE (Graph Neural Ising Transformer for Efficient Quantum Optimization). GRANITE leverages Graph Neural Networks (GNNs) to learn how to compress Ising models. Here's a breakdown of the approach:

  • Graph Representation: The Ising model is represented as a weighted graph where nodes are spins and edges represent interactions.
  • GNN for Feature Learning: A GNN is employed to learn representations of nodes (spins) and edges (interactions). This GNN captures the complex relationships and dependencies within the Ising model.
  • Predicting Spin Alignment: The GNN's output is fed into a prediction layer that uses logistic regression to predict the alignment (or anti-alignment) of connected spins in the ground state. This prediction is crucial for determining how to merge or "contract" qubits.
  • Dynamic Compression: Based on the GNN's predictions, GRANITE iteratively performs "merge" or "flip-merge" operations. A merge operation combines two spins that are always aligned in the ground state, effectively reducing the number of qubits. A flip-merge handles spins that are always anti-aligned.
  • Hybrid Loss Function: A novel hybrid loss function is used to train the GNN. This function combines a standard binary cross-entropy loss for edge classification with a confidence-based weighting mechanism. This allows the model to prioritize more certain predictions and balance the trade-off between compression and solution accuracy.
  • Iterative Refinement: The compression process is iterative. After each merge or flip-merge operation, the resulting smaller Ising model is fed back into the GNN until the desired reduction ratio is achieved.

What's new here is the use of GNNs to learn the compression rules dynamically, rather than relying on pre-defined heuristics. This allows GRANITE to adapt to different Ising model structures and achieve a tunable trade-off between compression and solution quality.

Datasets

The paper uses a synthetically generated dataset of random Ising Hamiltonians. These Hamiltonians are generated following three common graph topologies:

  • Erdős-Rényi (ER): Randomly connected graphs.
  • Barabási-Albert (BA): Scale-free networks with preferential attachment.
  • Watts-Strogatz (WS): Small-world networks with high clustering and short path lengths.

The dataset consists of 97,500 graphs, split into 80% for training and 20% for validation. An additional 20,000 graphs are used for evaluation. The ground state labels (alignment, anti-alignment, or neutral) for each edge were computed using an exhaustive search, which is feasible for the relatively small graph sizes used in the dataset (up to 400 nodes).

Key Insights and Ideas

  • GNNs as Compression Rule Discoverers: The most significant insight is that GNNs can learn complex, physics-informed rules for compressing Ising models. Instead of relying on human-designed heuristics, the GNN discovers optimal ways to merge qubits based on their predicted ground-state behavior.
  • Tunable Trade-off: GRANITE offers a flexible approach, allowing users to specify a desired compression ratio. This is a crucial advantage over existing methods that offer limited or fixed compression.
  • Preserving Solution Quality: The framework is designed to minimize the loss of solution quality during compression. The hybrid loss function and iterative merging process are key to achieving this.
  • Bridging the Quantum Gap: By effectively reducing the size of Ising models, GRANITE makes larger, more complex optimization problems tractable for current and near-term quantum annealers, accelerating the path towards practical quantum advantage.
  • Co-NP Hardness of Alignment Prediction: The paper highlights that predicting qubit alignment for exact ground states is a Co-NP-hard problem. This theoretical hardness justifies the need for machine learning approaches like GRANITE.

Key Results

  • High Solution Quality: GRANITE consistently achieves high solution optimality across various graph topologies and sizes, even at aggressive compression levels. For example, with 75% edge reduction on graphs with 200 nodes, optimality remained above 91% for all topologies.
  • Significant Qubit Reduction: The method demonstrates substantial qubit reduction. For large Ising instances (n=400) that would exceed hardware constraints, GRANITE can reduce the required physical qubits to as low as 5.3% (ER), 7.4% (BA), and 16.5% (WS) of the original number after 75% edge reduction.
  • Superior to Random Compression: GRANITE significantly outperforms random compression strategies, maintaining optimality above 91% compared to random methods achieving less than 40%.
  • Optimal GNN Architecture: Ablation studies indicated that a three-layer GNN architecture with the proposed hybrid loss function provides the best performance.

Limitations and Future Work

  • Dataset Size: While the dataset is substantial (97,500 graphs), it consists of synthetically generated random graphs. The performance on real-world, structured optimization problems may differ.
  • Exhaustive Search for Labels: The ground state labels for training were obtained via exhaustive search, which is computationally expensive and limits the size of graphs that can be used for training.
  • Hardware Specificity: The experiments were conducted on D-Wave's Advantage QPU. Further investigation is needed to assess GRANITE's effectiveness on other quantum hardware platforms and architectures.

Future work suggested by the authors includes:

  • Real-World Problem Application: Testing GRANITE on larger, real-world optimization problems to assess its practical utility.
  • Adaptation to Other Quantum Technologies: Adapting the framework for other quantum computing paradigms, such as gate-based quantum computers (e.g., for QAOA).
  • Addressing Hardware Noise: Investigating how to account for and mitigate hardware-specific noise in quantum annealers.

Summary updated

Abstract

Hard combinatorial optimization problems, often mapped to Ising models, promise potential solutions with quantum advantage but are constrained by limited qubit counts in near-term devices. We present an innovative quantum-inspired framework that dynamically compresses large Ising models to fit available quantum hardware of different sizes. Thus, we aim to bridge the gap between large-scale optimization and current hardware capabilities. Our method leverages a physics-inspired GNN architecture to capture complex interactions in Ising models and accurately predict alignments among neighboring spins (aka qubits) at ground states. By progressively merging such aligned spins, we can reduce the model size while preserving the underlying optimization structure. It also provides a natural trade-off between the solution quality and size reduction, meeting different hardware constraints of quantum computing devices. Extensive numerical studies on Ising instances of diverse topologies show that our method can reduce instance size at multiple levels with virtually no losses in solution quality on the latest D-Wave quantum annealers.
BibTeX
@misc{tran2024scalable,
  author = {Co Tran and Quoc-Bao Tran and Truong-Son Hy and Thang N Dinh},
  title = {{Scalable Quantum-Inspired Optimization Through Dynamic Qubit Compression}},
  year = {2024},
  eprint = {2412.18571},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2412.18571},
}
Figure