Skip to content
DSML.KZ
Publications

Preprint · arXiv · December 3, 2025

Quantum Algorithm for Searching for the Longest Segment and the Largest Empty Rectangle

Kamil Ravilevich Khadiev, Vladislav Remidovskii, Timur Evgenievich Bikmullin, Aliya Khadieva

Kamil Khadiev
Read on arXivPDFDOI 10.48550/arxiv.2512.03788

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.

Quantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsQuantum Information and Cryptographyquantum algorithmsquery complexityquantum lower bounds

More by Kamil Khadiev