Quantum Circuits Now Tackle Complex Problems Beyond Classical Computers
Summarize this article with:
A new quantum approach solves complex, real-world optimisation problems. Seongmin Kim and colleagues from National Centre for Computational Sciences, IBM T.J.
Watson Research Centre, Quantum Science Centre, Kyung Hee University, University of Notre Dame, and Oak Ridge National Laboratory have developed a distributed quantum optimisation framework that directly addresses higher-order interactions within dense, large-scale problems. The framework finds high-quality solutions for problems involving up to 500 variables in just 170 seconds, exceeding the performance of conventional methods and establishing a scalable paradigm for scientific optimisation, as evidenced by its successful application to optical metamaterial design. Distributed quantum optimisation solves complex binary problems rapidly Solutions for higher-order unconstrained binary optimisation (HUBO) problems involving up to 500 variables were found in 170 seconds, representing a substantial improvement over existing methods. Previously, solving HUBOs of this scale with comparable solution quality was impossible due to limitations in both classical algorithms and the ability of quantum systems to handle complex interactions. The computational complexity of HUBO problems grows rapidly with the number of variables and the order of interactions, making them intractable for classical solvers as problem size increases. The breakthrough stems from the development of a distributed quantum optimisation framework, or DQOF, which utilises quantum circuits to directly represent higher-order relationships between variables, unlike earlier approaches that simplified these interactions. These simplifications often introduce inaccuracies and prevent the discovery of optimal solutions. DQOF consistently delivered superior solution quality when benchmarked against existing methods, with improvements of up to 15% observed in certain test cases involving 500 variables. This improvement is particularly significant in problems where higher-order interactions play a crucial role in determining the optimal solution. A key component, the clustering strategy, enabled the creation of wider quantum circuits, reaching 28 qubits on IBM’s Heron r2 processor, without increasing circuit depth. Circuit depth refers to the number of sequential quantum operations, and minimising it is critical for mitigating the effects of decoherence, the loss of quantum information due to environmental noise. This improves hardware efficiency and allows for results that outperform classical simulations. The clustering strategy works by grouping variables that are strongly correlated, allowing their interactions to be represented more efficiently within the quantum circuit. Despite these advances, the 170-second solution time for 500 variables does not yet demonstrate a clear advantage over highly optimised classical algorithms for all problem types, and significant scaling challenges remain before tackling problems with thousands of variables. Further research is needed to improve the scalability and robustness of the DQOF framework