Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA

Stein, Jonas ; Chamanian, Farbod ; Zorn, Maximilian ; Nüßlein, Jonas ; Zielinski, Sebastian und Linnhoff-Popien, Claudia (2023): Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA. GECCO '23 Companion: Companion Conference on Genetic and Evolutionary Computation, Lisbon, Portugal, 15. - 19. Juli 2023. Silva, Sara und Paquete, Luís (eds.) : In: Proceedings of the Companion Conference on Genetic and Evolutionary Computation, New York, NY, United States: Association for Computing Machinery. pp. 2254-2262

Abstract

Quantum computing provides powerful algorithmic tools that have been shown to outperform established classical solvers in specific optimization tasks. A core step in solving optimization problems with known quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) is the problem formulation. While quantum optimization has historically centered around Quadratic Unconstrained Optimization (QUBO) problems, recent studies show, that many combinatorial problems such as the TSP can be solved more efficiently in their native Polynomial Unconstrained Optimization (PUBO) forms. As many optimization problems in practice also contain continuous variables, our contribution investigates the performance of the QAOA in solving continuous optimization problems when using PUBO and QUBO formulations. Our extensive evaluation on suitable benchmark functions, shows that PUBO formulations generally yield better results, while requiring less qubits. As the multi-qubit interactions needed for the PUBO variant have to be decomposed using the hardware gates available, i.e., currently single- and two-qubit gates, the circuit depth of the PUBO approach outscales its QUBO alternative roughly linearly in the order of the objective function. However, incorporating the planned addition of native multi-qubit gates such as the global Mølmer-Sørenson gate, our experiments indicate that PUBO outperforms QUBO for higher order continuous optimization problems in general.

• Item Type: Conference or Workshop Item (Paper)
• Faculties: Medicine; Mathematics, Computer Science and Statistics > Computer Science > Artificial Intelligence and Machine Learning
• Subjects: 000 Computer science, information and general works > 004 Data processing computer science
• ISBN: 979-8-4007-0120-7
• Place of Publication: New York, NY, United States
• Language: English