Scaling Quantum Optimization with Divi: Automating Parallelization for QAOA
QAOA is a promising approach for solving combinatorial optimization problems, but scaling it to large problem instances remains a challenge. QAOA isn't the only quantum program that faces these issues, and at Qoro, the goal is to automate the process of breaking down problems to sizes that can be simulated or executed on today's quantum hardware. To address this, we developed Divi, a software package that automates problem partitioning and parallel execution, enabling the efficient use of distributed quantum and classical computing resources.
The Challenge of Large-Scale QAOA
To QAOA to optimize a problem - scheduling, routing, etc. - one firstly has to map the problem to a constraint graph. This graph contains nodes and edges, where each node represents one qubit when executed. For practical problems one requires many nodes, 100s or 1000s, but current quantum computers are generally fewer than 100 qubits. In addition, simulating more than 50 qubits perfectly is out of reach. For problems of 1000s of nodes, it is necessary to break the problems down to run on current infrastructure.
One of the fundamental questions in distributed optimization is whether partitioning a problem impacts the quality of the solution. Our approach to solving large instances problem highlights how partitioning and parallelization can enhance scalability while maintaining accuracy. By integrating these techniques into Divi, we provide a generalized workflow that automates problem partitioning and efficiently aggregates results, removing these complexities from the end-user's programming tasks.
Graph Partitioning for QAOA
To leverage QAOA on near-term quantum devices with limited qubit capacity, we use graph partitioning methods. This enables us to distribute workloads across multiple quantum processing units (QPUs) or simulators, each handling a subset of the problem. To improve partition balance, we further integrate community detection clustering to ensure even distribution, minimizing information loss and improving computational efficiency.
Partitioning can also reduce the number of SWAP gates, addressing quantum processors' connectivity constraints and optimizing circuit execution. This is particularly valuable for quantum hardware with restricted entanglement capabilities, allowing us to execute large problem instances effectively.
Evaluating Partitioned Optimization
We benchmark partitioned QAOA against classical algorithms, particularly the Goemans-Williamson (GW) approximation algorithm, which provides a 0.878-optimal solution for the MaxCut problem. Our results demonstrate that for small-scale graphs (~500 nodes), partitioned QAOA achieves comparable results to GW, but as problem size increases, an optimality gap emerges. However, increasing subproblem sizes within QAOA narrows this gap, suggesting a trade-off between partition size and solution quality. Increasing the subproblem size though, requires more qubits to execute.
Introducing Divi: Automating Parallelized Quantum Algorithms
To simplify the execution of large-scale QAOA and other quantum algorithms, we developed Divi, a Python-based software package that automates parallelization and batching.
Key Features of Divi:
One of Divi’s key optimizations is symbolic parameter substitution, which significantly speeds up QAOA circuit generation. Instead of re-creating entire circuits for each optimization step, especially time consuming with parallelized optimization methods, Divi pre-generates a circuit "scaffold" and substitutes parameter values dynamically, reducing redundant computations. Benchmarks show that this optimization reduces QAOA batch job generation time by a factor of 13 on standard computing hardware.
Future of Scalable Quantum Optimization
As quantum computing advances, the need for scalable and automated workflows will grow. Divi represents a crucial step in making quantum algorithms more accessible and practical by handling partitioning, parallelization, and cloud execution seamlessly. Our work demonstrates that hybrid quantum-classical architectures can be efficiently utilized for large-scale combinatorial optimization, paving the way for real-world applications quantum computing.
We look forward to further refining Divi, integrating advanced partitioning techniques, and expanding support for additional quantum programs. Get in touch if you're interested in collaborating or exploring how Divi can accelerate your quantum computing projects.