We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. We show that OSCM can be viewed as a set problem amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in O∗(1.728n) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in O∗(2n) time and polynomial space.
Caroppo, S., DA LOZZO, G., DI BATTISTA, G. (2024). Quantum Algorithms for One-Sided Crossing Minimization. In Leibniz International Proceedings in Informatics, LIPIcs. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/lipics.gd.2024.20].
Quantum Algorithms for One-Sided Crossing Minimization
Susanna Caroppo;Giordano Da Lozzo;Giuseppe Di Battista
2024-01-01
Abstract
We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. We show that OSCM can be viewed as a set problem amenable for exact algorithms with a quantum speedup with respect to their classical counterparts. First, we exploit the quantum dynamic programming framework of Ambainis et al. [Quantum Speedups for Exponential-Time Dynamic Programming Algorithms. SODA 2019] to devise a QRAM-based algorithm that solves OSCM in O∗(1.728n) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in O∗(2n) time and polynomial space.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
