Grid-partitioned Quantum Computing Solves 50-Asset QUBO Problems Via Neutral Atom MWIS Mapping

Quadratic Unconstrained Binary Optimisation (QUBO) problems underpin many real-world applications, from financial portfolio optimisation to machine learning, yet solving them becomes increasingly difficult as problem size grows. Soumyadip Das, Suman Kumar Roy, Rahul Rana, and M Girish Chandra, all from Tata Consultancy Services, present a new hybrid approach that combines classical computation with the emerging power of neutral atom quantum computing. Their method cleverly transforms QUBO problems into a related challenge, the Maximum Weighted Independent Set problem, and then divides it into smaller, more manageable parts using a spatial grid. By solving these sub-problems with analog quantum simulation and combining the results, the team demonstrates a scalable and competitive solution, offering a promising pathway towards tackling complex optimisation challenges in the current era of noisy quantum devices.

The approach employs spatial grid partitioning to decompose the problem into manageable subgraphs, solves each subgraph using Analog Hamiltonian Simulation (AHS), and merges solutions greedily to approximate the global optimum. The core idea is to harness the natural connectivity of neutral atom arrays to tackle optimization challenges that are difficult for classical algorithms. This allows the problem to be solved using a combination of analog quantum simulation, performed using neutral atom arrays, and classical optimization techniques.

To address the limitations of current neutral atom hardware, such as limited qubit count and connectivity, the problem is partitioned into smaller subgraphs. This enables the quantum computation to be performed on manageable portions of the overall problem. Researchers then solve these subgraphs using Analog Hamiltonian Simulation on the neutral atom array, exploiting Rydberg interactions between atoms to represent the optimization problem. Finally, the solutions to the subproblems are merged using a classical greedy algorithm to obtain an approximate solution to the original QUBO problem. The framework’s efficacy is demonstrated on a portfolio optimization problem using historical stock data, proving its ability to find good solutions.

Results reveal that this hybrid quantum-classical approach consistently achieves lower energy values, indicating better solutions, compared to classical simulated annealing, particularly for larger problem instances. The grid partitioning strategy enables the framework to scale to larger problem sizes, overcoming the limitations of current hardware. The framework also demonstrates robustness against noise and resource constraints typical of near-term quantum hardware. In essence, the paper presents a promising pathway for utilizing neutral atom quantum computers to solve real-world optimization problems by cleverly combining quantum computation with classical algorithms and addressing hardware limitations through problem decomposition. Key takeaways from this work include the viability of neutral atom arrays as a platform for quantum optimization, the crucial role of hybrid quantum-classical algorithms for near-term quantum computing, and the importance of problem decomposition as a technique for scaling quantum algorithms. This approach utilizes spatial grid partitioning to decompose complex problems into manageable subgraphs, enabling scalable solutions. The team successfully demonstrated the framework’s efficacy by evaluating it on a 50-asset portfolio optimization problem, utilizing historical S and P 500 data.

The system encodes problem variables as spins within a simulated Ising Hamiltonian, employing Rydberg excitations and van der Waals interactions to define couplings between atoms. Researchers engineered the analog evolution to carefully mitigate noise and maintain adiabaticity, crucial for accurate problem solving. Experiments reveal that the GP-NAQC framework effectively addresses the limitations of current neutral atom hardware, particularly the mismatch between native hardware Hamiltonians and the requirements of complex optimization problems. The study details how the system utilizes embedding strategies to reduce higher-order cost terms into quadratic interactions, mapping logical couplings onto available physical interactions. While embedding introduces overhead, the spatial partitioning strategy minimizes resource consumption and enhances scalability. By combining analog Hamiltonian simulation with a classical greedy merging strategy, the framework overcomes current limitations in qubit count and hardware connectivity, demonstrating a practical approach to optimization tasks. Experiments conducted on a 50-asset portfolio optimization problem reveal that this hybrid method achieves competitive performance when compared to purely classical techniques.

The results highlight the potential of integrating quantum subroutines into optimization workflows, even within the constraints of near-term quantum hardware. While acknowledging that the greedy merging step introduces approximation errors, particularly in dense graphs, the team demonstrated robustness against noise and resource limitations. Future research will focus on refining the partitioning strategy, incorporating advanced error mitigation techniques, and developing adaptive solution-merging schemes to further enhance performance and expand the framework’s applicability to a wider range of combinatorial optimization problems, including scheduling, clustering, and network design.