Quantum Algorithms for One-Sided Crossing Minimization

We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an n-vertex bipartite graph G=(U,V,E⊆ U × V), a $2$-level drawing (πU,πV) of G is described by a linear ordering πU: U ↔ \1,,|U|\ of U and linear ordering πV: V ↔ \1,,|V|\ of V. For a fixed linear ordering πU of U, the OSCM problem seeks to find a linear ordering πV of V that yields a $2$-level drawing (πU,πV) of G with the minimum number of edge crossings. We show that OSCM can be viewed as a set problem over V 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.728ⁿ) time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in O^*(2ⁿ) time and polynomial space.