© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2512.03788

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

Kamil Khadiev, Vladislav Remidovskii, Timur Bikmullin, Aliya Khadieva

quant-phcs.DSSubmitted Dec 3, 2025• Announced Dec 4, 2025• 0 citations

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.

Comments: accepted in SOFSEM2026 conference, In Proceedings LNCS vol.16448

Related papers

Quantum algorithm for search of largest square on two dimensional map

Kamil Ravilevich Khadiev, Vladislav Remidovskii

In the framework of this work, we consider the problem of finding the largest square in a 0-1 matrix consisting of ones. The task is considered with point of view of quantum algorithms. For the problem of finding a square of the largest size on a two-dimensional map, there is a quantum algorithm with running time O(n1.5log n) and error probability at most 0.1. At the same time, any classical algorithm (probabilistic or deterministic) has a lower bound on the running time Omega(n2).

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 citations

Complexity of Searching Maximum of a Function on Quantum Computer

Maciej Goćwin

In this paper we deal with a problem of finding maximum of a function from the Holder class on quantum computer. We present matching lower and upper bounds on the complexity of this problem in the quantum query model. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of discrete sequence. To prove lower bounds we use result for finding logical OR of sequence of bits. We show that quantum computer yields a quadratic speed-up over deterministic and randomized algorithms.

•Jul 6, 2005•1 citation

Quantum algorithm for search of longest segment of elements satisfying a predicate

Kamil Ravilevich Khadiev, Timur Evgenievich Bikmullin

In the framework of this work, we consider the problem of finding the longest segment of elements satisfying some predicate. For a task search for the longest segment that satisfies the predicate exists quantum algorithm with running time O(√n log n), where n - the length of the input set.

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"•Jan 1, 2022•0 citations

Quantum search of spatial regions

Scott Aaronson, Andris Ambainis

Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size /spl radic/n x /spl radic/n? The problem is that /spl radic/n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time 0(/spl radic/n) for d /spl ges/ 3, or 0(/spl radic/n log/sup 3/ n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of locality for unitary matrices acting on graphs. As an application of our results, we give an 0(/spl radic/n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Hoyer and de Wolf and matches a lower bound of Razborov.

arXiv:quant-ph/0303041•Annual Symposium on Foundations of Computer Science•Mar 2, 2004•128 citations

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/2})$ bound for finding a maximum-out-degree vertex in an $n$-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an $n$-vertex undirected graph requires $Θ(n^{3/2})$ quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum $(k,n-k)$-Cut, which asks for the largest cut with one side of size $k$. For every constant $k\geq 1$, we give an $O(n^{2-1/(k+1)})$-query quantum algorithm. 4) We establish a reduction to Maximum $(k,n-k)$-Cut involving $k$-Graph Collision, which asks whether the marked vertices of a known graph contain a $k$-clique. For $k\geq 3$, this yields unconditional lower bounds with exponents strictly larger than $3/2$, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for $k$-Graph Collision, the reduction yields a lower bound matching our upper bound above.

quant-pharXiv:2610.13906•Oct 12, 2026•0 citations

On the Quantum Complexity of Closest Pair and Related Problems

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin +2 more

The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a d-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(n log n) time in constant dimensions (i.e., when d = O(1)). This paper asks and answers the question of the problem’s quantum time complexity. Specifically, we give an Õ(n^(2/3)) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an n^o(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

Leibniz international proceedings in informatics•Jan 1, 2020•17 citations

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.

In this paper we deal with a problem of finding maximum of a function from the Holder class on quantum computer. We present matching lower and upper bounds on the complexity of this problem in the quantum query model. We prove upper bounds by constructing an algorithm that uses the algorithm for finding maximum of discrete sequence. To prove lower bounds we use result for finding logical OR of sequence of bits. We show that quantum computer yields a quadratic speed-up over deterministic and randomized algorithms.

Can Grover's quantum search algorithm speed up search of a physical region - for example a 2D grid of size /spl radic/n x /spl radic/n? The problem is that /spl radic/n time seems to be needed for each query, just to move amplitude across the grid. Here we show that this problem can be surmounted, refuting a claim to the contrary by Benioff. In particular, we show how to search a d-dimensional hypercube in time 0(/spl radic/n) for d /spl ges/ 3, or 0(/spl radic/n log/sup 3/ n) for d = 2. More generally, we introduce a model of quantum query complexity on graphs, motivated by fundamental physical limits on information storage, particularly the holographic principle from black hole thermodynamics. Our results in this model include almost-tight upper and lower bounds for many search tasks; a generalized algorithm that works for any graph with good expansion properties, not just hypercubes; and relationships among several notions of locality for unitary matrices acting on graphs. As an application of our results, we give an 0(/spl radic/n)-qubit communication protocol for the disjointness problem, which improves an upper bound of Hoyer and de Wolf and matches a lower bound of Razborov.

We study the quantum query complexity of several basic graph problems. 1) We prove a tight

Θ(n^{3/2})

bound for finding a maximum-out-degree vertex in an

n

-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an

n

-vertex undirected graph requires

Θ(n^{3/2})

quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum

(k,n-k)

-Cut, which asks for the largest cut with one side of size

k

. For every constant

k\geq 1

, we give an

n

-query quantum algorithm. 4) We establish a reduction to Maximum

(k,n-k)

-Cut involving

k

-Graph Collision, which asks whether the marked vertices of a known graph contain a

k

-clique. For

k\geq 3

, this yields unconditional lower bounds with exponents strictly larger than

3/2

, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for

k

-Graph Collision, the reduction yields a lower bound matching our upper bound above.

The closest pair problem is a fundamental problem of computational geometry: given a set of n points in a d-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in O(n log n) time in constant dimensions (i.e., when d = O(1)). This paper asks and answers the question of the problem’s quantum time complexity. Specifically, we give an Õ(n^(2/3)) algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In polylog(n) dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the Quantum Strong Exponential Time Hypothesis (QSETH), which is based on the assumption that Grover’s algorithm is optimal for CNF-SAT when the clause width is large. We show that the naïve Grover approach to closest pair in higher dimensions is optimal up to an n^o(1) factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.