Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.01942 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917767410614272 |
|---|---|
| author | Caroppo, Susanna Da Lozzo, Giordano Di Battista, Giuseppe |
| author_facet | Caroppo, Susanna Da Lozzo, Giordano Di Battista, Giuseppe |
| contents | We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an $n$-vertex bipartite graph $G=(U,V,E\subseteq U \times V)$, a $2$-level drawing $(π_U,π_V)$ of $G$ is described by a linear ordering $π_U: U \leftrightarrow \{1,\dots,|U|\}$ of $U$ and linear ordering $π_V: V \leftrightarrow \{1,\dots,|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^n)$ time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in $O^*(2^n)$ time and polynomial space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_01942 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum Algorithms for One-Sided Crossing Minimization Caroppo, Susanna Da Lozzo, Giordano Di Battista, Giuseppe Quantum Physics Data Structures and Algorithms We present singly-exponential quantum algorithms for the One-Sided Crossing Minimization (OSCM) problem. Given an $n$-vertex bipartite graph $G=(U,V,E\subseteq U \times V)$, a $2$-level drawing $(π_U,π_V)$ of $G$ is described by a linear ordering $π_U: U \leftrightarrow \{1,\dots,|U|\}$ of $U$ and linear ordering $π_V: V \leftrightarrow \{1,\dots,|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^n)$ time and space. Second, we use quantum divide and conquer to obtain an algorithm that solves OSCM without using QRAM in $O^*(2^n)$ time and polynomial space. |
| title | Quantum Algorithms for One-Sided Crossing Minimization |
| topic | Quantum Physics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.01942 |