{"ID":2833509,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.03788","arxiv_id":"2512.03788","title":"Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle","abstract":"In the paper, we consider the problem of searching for the Largest empty rectangle in a 2D map, and the one-dimensional version of the problem is the problem of searching for the largest empty segment. We present a quantum algorithm for the Largest Empty Square problem and the Largest Empty Rectangle of a fixed width $d$ for $n\\times n$-rectangular map. Query complexity of the algorithm is $\\tilde{O}(n^{1.5})$ for the square case, and $\\tilde{O}(n\\sqrt{d})$ for the rectangle with a fixed width $d$ case, respectively. At the same time, the lower bounds for the classical case are $Ω(n^2)$, and $Ω(nd)$, respectively. The Quantum algorithm for the one-dimensional version of the problem has $O(\\sqrt{n}\\log n\\log\\log n)$ query complexity. The quantum lower bound for the problem is $Ω(\\sqrt{n})$ which is almost equal to the upper bound up to a log factor. The classical lower bound is $Ω(n)$. So, we obtain the quadratic speed-up for the problem.","short_abstract":"In the paper, we consider the problem of searching for the Largest empty rectangle in a 2D map, and the one-dimensional version of the problem is the problem of searching for the largest empty segment. We present a quantum algorithm for the Largest Empty Square problem and the Largest Empty Rectangle of a fixed width $...","url_abs":"https://arxiv.org/abs/2512.03788","url_pdf":"https://arxiv.org/pdf/2512.03788v1","authors":"[\"Kamil Khadiev\",\"Vladislav Remidovskii\",\"Timur Bikmullin\",\"Aliya Khadieva\"]","published":"2025-12-03T13:37:50Z","proceeding":"quant-ph","tasks":"[\"quant-ph\",\"cs.DS\"]","methods":"[]","has_code":false}