Quantum Circuits Now Tackle Complex Problems Beyond Classical Computers

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</a

Direct Quantum Representation of Higher-Order Unconstrained Binary Optimisation problems

DQOF’s core innovation lies in its ability to directly represent complex relationships between variables, achieved through the strategic deployment of quantum circuits. These circuits process information using quantum bits, or qubits, functioning similarly to electrical circuits manipulating signals. However, unlike classical bits which can only represent 0 or 1, qubits can exist in a superposition of both states simultaneously, enabling them to explore a much larger solution space. It embraces higher-order interactions from the outset, which is important for accurately modelling real-world scenarios, unlike many existing methods that simplify problems. Traditional quantum algorithms for optimisation, such as the Quantum Approximate Optimisation Algorithm (QAOA), often struggle with higher-order terms, requiring significant circuit depth to represent them accurately. This increased depth exacerbates the effects of decoherence and limits the size of problems that can be solved. DQOF overcomes this limitation by directly encoding these interactions into the quantum circuit’s structure. This is enabled by a clustering strategy constructing wider quantum circuits without increasing their depth, allowing efficient execution on available quantum hardware and offering a pathway to better designs for materials science and energy engineering. The framework leverages the principles of distributed computing, dividing the problem into smaller subproblems that can be solved concurrently on multiple quantum processors, further enhancing its scalability.

Distributed quantum optimisation efficiently designs complex optical materials

A new approach to optimisation has been unlocked, with importance for designing everything from novel materials to efficient energy systems. The framework tackles problems where numerous interacting components must be balanced to achieve the best outcome, a scenario common in complex scientific and engineering challenges. These challenges often involve a vast number of parameters and constraints, making it difficult to find optimal solutions using traditional methods. Successfully applied to optical metamaterial design, a field requiring precise control of light manipulation, the framework demonstrates its practical value in discovering high-performance structures. Optical metamaterials are artificial materials engineered to exhibit properties not found in nature, such as negative refractive index. Designing these materials requires optimising the shape, size, and arrangement of nanoscale structures to achieve desired optical properties.

Although currently handling up to 500 variables, these advances are vital as classical computers struggle with increasingly complex optimisation tasks, offering a pathway to better designs. The ability to efficiently explore a vast design space is crucial for discovering novel metamaterial structures with enhanced performance. IBM scientists have demonstrated that it surpasses current methods in both solution quality and scalability, efficiently designing high-performance optical materials. By directly incorporating higher-order interactions and combining quantum circuits with conventional high-performance computing, it surpasses limitations of earlier approaches reliant on simplified models. The hybrid approach allows the DQOF to leverage the strengths of both quantum and classical computing, achieving superior results compared to either approach alone. Future work will focus on extending the framework to handle even larger and more complex problems, as well as exploring its application to other areas of scientific and engineering optimisation, such as drug discovery and financial modelling.

The researchers developed a distributed quantum optimisation framework capable of finding high-quality solutions for higher-order optimisation problems with up to 500 variables in 170 seconds. This matters because many real-world challenges, like designing complex materials, involve numerous interacting components that are difficult for traditional computers to optimise effectively. Applied to optical metamaterial design, the framework efficiently discovered high-performance structures and confirmed the importance of considering higher-order interactions. The authors intend to extend this work to even larger problems and explore applications in fields such as drug discovery and financial modelling.