Quantum Framework Finds Better Network Solutions and Accelerates Convergence

Cédrick Perron and colleagues at Université de Sherbrooke have developed a new hybrid quantum-classical framework, Lp-Quts, which combines a neutral atom quantum computer (NAQC) sampler with a classical cutting-plane algorithm to address the maximum weighted independent set (MWIS) problem. The approach overcomes limitations of existing analogue methods by integrating quantum computation with classical optimisation, offering both improved performance and key convergence guarantees for certain graph types. It achieves near-optimal solutions on instances with up to 300 vertices, exceeding the scale of current hardware, and represents a sharp step towards using quantum resources for practical optimisation tasks.

Hybrid quantum-classical approach extends maximum weighted independent set problem-solving to 300

A five to ten per cent improvement in solution optimality for maximum weighted independent set problems has been recorded, exceeding previous limitations of neutral atom quantum computer hardware. Solving instances with over a few dozen vertices was previously intractable, but this new hybrid quantum-classical framework, Lp-Quts, now successfully tackles graphs containing up to 300 vertices. This advance results from integrating a quantum sampler with a classical cutting-plane algorithm, systematically refining potential solutions by eliminating invalid options. The MWIS problem, a cornerstone of combinatorial optimisation, involves identifying a subset of vertices in a weighted graph such that no two vertices in the subset are adjacent, and the sum of their weights is maximised. This problem has significant implications for areas such as resource allocation, network design, and machine learning feature selection.

Lp-Quts outperformed both direct analogue quantum protocols and greedy algorithms with equivalent sampling resources, consistently finding better solutions. The neutral atom quantum computer operates by encoding the problem variables onto the internal states of individual, trapped neutral atoms, typically rubidium or caesium. These atoms are then manipulated using lasers to create and evolve a quantum state representing a potential solution. The quantum sampler generates probabilistic samples from this state, which are then fed into the classical cutting-plane algorithm. For t-perfect graphs, the framework guarantees convergence to a solution within a predictable timeframe, based on established mathematical principles. A t-perfect graph is one where every maximal independent set has the same size, simplifying the analysis and allowing for provable performance bounds. Although Lp-Quts delivers near-optimal results, it currently falls short of matching the performance of simulated annealing at this scale, indicating further development is needed to surpass established classical methods for larger, more complex problems. The system’s performance is particularly sensitive to the quality of the initial quantum sampling, and future work will focus on optimising this stage to enhance solution accuracy and speed. Specifically, researchers are investigating techniques to improve the fidelity of the quantum state preparation and reduce the impact of noise on the sampling process.

Quantum-classical hybridisation advances maximum weighted independent set problem-solving

Optimisation problems underpin countless real-world scenarios, spanning logistics, finance, materials discovery and machine learning; efficiently finding the best solution amongst many possibilities is therefore vital. Lp-Quts, a hybrid approach blending neutral atom quantum computers with established classical techniques, has now been shown to be effective in tackling the maximum weighted independent set problem. While classical simulated annealing currently surpasses it for problems of this size, this represents a strong step towards harnessing the potential of quantum computers for real-world optimisation. The cutting-plane algorithm employed is a classical iterative method for solving linear programs. It works by adding constraints, the ‘cutting planes’, to a relaxed version of the original problem, progressively tightening the feasible region until an optimal solution is found. The relaxation involves replacing integer variables with continuous variables, allowing the problem to be solved more easily, but potentially introducing inaccuracies.

Neutral atom quantum computers sample potential solutions, enabling the system to tackle complex maximum weighted independent set problems. The choice of neutral atom quantum computing is significant due to its inherent scalability and connectivity. Unlike superconducting qubits, neutral atoms can be arranged in arbitrary geometries, offering greater flexibility in mapping problem structures onto the quantum hardware. A classical ‘cutting-plane algorithm’ then refines the search for the best outcome by systematically eliminating invalid options. The integration of these two paradigms allows Lp-Quts to leverage the strengths of both: the quantum computer explores a vast solution space efficiently, while the classical algorithm ensures the final solution is accurate and feasible. The current implementation shows promise, and scientists are exploring ways to scale the quantum component and improve the efficiency of the classical refinement stage, aiming to achieve a demonstrable quantum advantage. This includes investigating more sophisticated quantum sampling techniques, such as variational quantum eigensolvers, and developing more efficient classical cutting-plane algorithms tailored to the specific characteristics of the MWIS problem. Furthermore, research is underway to explore the potential of Lp-Quts for solving other NP-hard optimisation problems beyond the MWIS, broadening its applicability and impact.

The ability to solve MWIS problems with up to 300 vertices represents a significant milestone, as many practical applications involve instances of this size. For example, in logistics, the MWIS problem can be used to optimise the placement of distribution centres, maximising coverage while minimising interference. In finance, it can be applied to portfolio optimisation, selecting a set of assets that provides the highest return with the lowest risk. The development of Lp-Quts paves the way for exploring more complex and realistic scenarios, potentially leading to substantial improvements in efficiency and performance across various industries. The framework’s reliance on a classical cutting-plane algorithm also provides a degree of robustness and interpretability, making it easier to understand and validate the results.

Lp-Quts successfully solved maximum weighted independent set problems involving up to 300 vertices, exceeding the capacity of current neutral atom quantum computer hardware. This hybrid quantum-classical framework combines a quantum sampler with a classical cutting-plane algorithm, achieving solutions within 5, 10% of optimality and outperforming existing methods under similar conditions. The research demonstrates how quantum computers can enhance classical optimisation techniques with reduced quantum resources while maintaining formal guarantees of solution quality. Scientists are currently working to scale the quantum component and refine the classical algorithm to further improve performance.