Authors
Martin J.A. Schuetz*, Romina Yalovetzky*, Ruben S. Andrist, Grant Salton, Yue Sun, Rudy Raymond, Shouvanik Chakrabarti, Atithi Acharya, Ruslan Shaydulin, Marco Pistoia, Helmut G. Katzgraber. *equal contributions
Published
Hybrid qReduMIS workflow: a quantum co-processor guides classical reductions to solve large optimization problems. Our approach tackles the three layers: application with the proposal of tackling the portfolio diversification problem, algorithm with the novel qReduMIS solver, and the hardware where it can be use different quantum architectures scuh as Rydberg atom arrays and quantum circuits on universal quantum computers.
Many important problems in science, logistics, and finance, can be framed as selecting the best subset of elements that do not conflict with each other—known as the maximum independent set problem. These problems are extremely difficult for classical computers as the number of possible combinations increases exponentially.
This work introduces qReduMIS, a hybrid quantum-classical framework that uses a quantum computer as a co-processor to help simplify large optimization problems. Instead of solving the entire problem on a quantum device, the quantum processor identifies key elements of the graph that are likely to belong to the optimal solution. This information is then used by classical algorithms to reduce the problem size and search more efficiently. Experiments using up to 231 qubits on Rydberg-atom quantum hardware show that this quantum-guided approach can help overcome limitations of current quantum devices.
