Regensburg 2022 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
QI: Fachverband Quanteninformation
QI 12: Quantum Computing and Algorithms
QI 12.1: Talk
Thursday, September 8, 2022, 15:00–15:15, H8
Partitioning methods for solving optimization problems on NISQ-devices — •Federico Dominguez1, Kaonan Campos Micadei1, Christian Ertler1, and Wolfgang Lechner1,2 — 1Parity QC Germany GmbH, Munich, Germany — 2Institute for Theoretical Physics, LFUI, and Parity QC GmbH, Innsbruck, Austria
Partitioning methods are hybrid quantum-classical algorithms aimed at overcoming the memory limitations of current quantum devices. These methods decompose large problems into smaller pieces suitable for running on small quantum devices. The partial solutions to the problem are recombined using classical algorithms that can deal with both the error from the partition approximation and the intrinsic errors of the NISQ devices.
In this work, we solve optimization problems by developing partitioning methods based on the Parity encoding [1,2] and we benchmark the results using simulated quantum annealing. The Parity transformation is capable of encoding all-to-all graphs, hypergraphs, and side conditions of optimization problems using only local qubit interactions and allowing for a high gate parallelizability and hence scalability [3,4]. The resulting locality property is especially suited for the partitioning approach. The performance of our method shows that large optimization problems can be efficiently run on small quantum devices. [1] Lechner, W. et al. (2015). Science advances,1(9), e1500838. [2] Ender, K. et al. (2021).arXiv preprint arXiv:2105.06233. [3] Lechner, W. (2020). IEEE Transactions on Quantum Engineering,1, 1-6. [4] Drieb-Schön, M. et al. (2021). arXiv preprint arXiv:2105.06235.