Our collaboration with NASA/USRA, Rigetti and Purdue

We have another accepted paper which is the result of our collaboration with amazing colleagues at NASA/USRA, Rigetti and Purdue.

Filip B. Maciejewski, Bao Gia Bach, Maxime Dupont, P. Aaron Lott, Bhuvanesh Sundar, David E. Bernal Neira, Ilya Safro, Davide Venturelli "A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization" is accepted in IEEE High-Performance Extreme Computing (HPEC) 2024

https://arxiv.org/abs/2408.07793

This work is a practical demonstration of our hybrid quantum-classical multilevel solver for the maxcut. Here we experimentally test how existing quantum processors perform as a sub-solver within the  multilevel strategy. We combine and extend (via additional classical processing) the recent Noise-Directed Adaptive Remapping (NDAR) and Quantum Relax & Round algorithms. We first demonstrate the effectiveness of our heuristic extensions on Rigetti's transmon device Ankaa-2 and then we find approximate solutions to 10 instances of fully connected Sherrington-Kirkpatrick graphs with random integer-valued coefficients obtaining normalized approximation ratios in the range ∼0.98−1.0. Then, we implement the extended NDAR and QRR algorithms as subsolvers in the multilevel algorithm for 6 large-scale graphs with at most ∼27,000 variables. The QPU (with classical post-processing steps) is used to find approximate solutions to dozens of problems, at most 82-qubit, which are iteratively used to construct the global solution.