Distributed QAOA solves 1000-bit optimization in 276 seconds
A hybrid quantum-classical algorithm breaks scalability barriers with a 1000-bit demonstration.
Quantum Approximate Optimization Algorithm (QAOA) has long promised speedups for combinatorial optimization, but real-world problems demand hundreds of qubits and deep circuits—beyond near-term hardware. A team led by Seongmin Kim at Korea Institute of Science and Technology Information (KISTI) and collaborators now presents Distributed QAOA (DQAOA), which partitions a large optimization task into many smaller sub-problems. Each sub-problem is solved on a combination of high-performance classical computers and quantum processors, then the partial solutions are iteratively aggregated to converge to the global optimum.
In benchmarks, DQAOA handled a 1000-bit optimization problem in roughly 276 seconds—a drastic improvement over direct QAOA approaches that would require hundreds of logical qubits and impractically deep circuits. The team also extended the framework with an active learning loop (AL-DQAOA), integrating machine learning and data production to optimize photonic structures. This dual demonstration proves that gate-based quantum computers can tackle industrially relevant tasks today, not just toy examples. The work, published in npj Quantum Information, outlines a practical path to quantum utility in logistics, finance, and materials science.
- DQAOA decomposes large problems into smaller sub-tasks, reducing qubit count and circuit depth.
- Solved a 1000-bit optimization in ~276 seconds on a quantum-centric supercomputing architecture.
- AL-DQAOA variant successfully optimized photonic structures using active learning and quantum computing.
Why It Matters
Quantum optimization becomes practical for large-scale logistics, materials design, and finance, not just academic benchmarks.