Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"

Quantum algorithm for search of largest square on two dimensional map

Kamil Ravilevich Khadiev, Vladislav Remidovskii

Published Jan 1, 2022• 0 citations
Publisher

Abstract

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).

DOI
10.20948/dms-2022-25

Related papers

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

Kamil Khadiev, Vladislav Remidovskii, Timur Bikmullin +1 more

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.

quant-pharXiv:2512.03788•Dec 4, 2025•0 citations

An O(N 3/4 log 2 N) Quantum Algorithm for the 1-dimensional Closest-Pair Problem

NILTON VOLPATO, Arnaldo Moura

Abstract. We present an algorithm for solving the closest pair problem using O(N 3/4 log 2 N) queries. This improves the simple approach using Dürr and Høyer’s minimum algorithm which would result in O(N) queries. The classical deterministic and probabilistic complexity is, respectively, of O(N log N) and O(N) queries. We also show a quantum lower bound of Ω(N 2/3) queries for the problem, and we discuss some open issues. 1.

•Feb 3, 2009•1 citation

Fastest Quantum Search for Extreme Point

Yuri Ozhigov

Let F be some integer function on words of length n and some oracle gives the value F(x) for a given x. It is shown how quantum algorithm can find a point of maximum of F with the probability of error 2/3 applying this oracle 32\\sqrt{2^n} times. This algorithm is optimal in within constant factor in the following sense. Any other algorithm acting in substantially shorter time gives incorrect answer for the functions F with the single point of maximum chosen randomly with probability 1. The lower bound as Ømega (\\sqrt{2^n /b}) is established for the quantum search for solution of equations f(x)=1 where f is a Boolean function with b such solutions chosen at random with probability 1, which is a partial amplification of the result of M. Boyer, G. Brassard, P. Hoyer and A. Tapp.

•May 31, 1998•0 citations

Quantum algorithms for finding extrema with unary predicates

Man Hon Chan

We study the problem of finding the maximum or the minimum of a given set S = {x₀, X₁, ... X n₋₁}, each element X i drawn from some finite universe [Unary] of real numbers. We assume that the inputs are abstracted within an oracle O where we can only gain information through unary comparisons in the form "Is Xi greater than, equal to, or less than some constant k?" Classically, this problem is solved optimally with a runtime of Θ(n +lg|U|). In the setting of Quantum Computing, we show that at least Ω(√n+lg|U|) queries are required to solve the problem even with bounded error. Combining variants of the Grover's search [1, 2] algorithm and the optimal classical unary extrema finding algorithm, we have derived a series of new quantum algorithms, some running in time as fast as O(√n lg*n+lg|U|). This shows that quantum computers can accelerate the speed in the unary comparison model asymptotically. Inspecting our tools, we find convincing arguments that our lower bound is most probably tight, but we may need an entirely new approach to solve the problem optimally. The technique used in our algorithm can also be extended to solve variations of quantum statistics problems. For instance, our result can be directly extended to approximation of extrema of real numbers, similar to that of [3]. Moreover, we can also solve the quantum k-select problem optimally in time O(√kn) with constant success probability. We hope that our ideas and tools will prove to be useful in other areas.

•Jan 1, 2011•0 citations

On the Quantum Query Complexity of Local Search in Two and Three Dimensions

Xiaoming Sun, Andrew Chi-Chih Yao

The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality

Annual Symposium on Foundations of Computer Science•Oct 1, 2006•10 citations

Quantum Search for a Given Substring in the Text Using a Hashing Technique

Marat Ablayev, Nailya Salikhova

The problem of searching for a given substring in the text was considered. It is known that classical algorithms solve this problem in a linear time depending on the length of the text and the specified template. Quantum algorithms speed up the search by “square root times”. In this paper, we proposed a quantum algorithm that solves the search problem a) with a high probability of getting the correct result and b) with the same acceleration (by “square root times”) as compared with the classical one, but it c) requires much less memory (based on the number of qubits used) than the previously known quantum algorithms.

Učenye zapiski Kazanskogo gosudarstvennogo universiteta. Seriâ Fiziko-matematičeskie nauki/Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki•Jan 1, 2020•3 citations
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).
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 ddd for n×nn\times nn×n-rectangular map. Query complexity of the algorithm is O~(n1.5)\tilde{O}(n^{1.5})O~(n1.5) for the square case, and O~(nd)\tilde{O}(n\sqrt{d})O~(nd​) for the rectangle with a fixed width ddd case, respectively. At the same time, the lower bounds for the classical case are Ω(n2)Ω(n^2)Ω(n2), and Ω(nd)Ω(nd)Ω(nd), respectively. The Quantum algorithm for the one-dimensional version of the problem has O(nlog⁡nlog⁡log⁡n)O(\sqrt{n}\log n\log\log n)O(n​lognloglogn) query complexity. The quantum lower bound for the problem is Ω(n)Ω(\sqrt{n})Ω(n​) which is almost equal to the upper bound up to a log factor. The classical lower bound is Ω(n)Ω(n)Ω(n). So, we obtain the quadratic speed-up for the problem.
Let F be some integer function on words of length n and some oracle gives the value F(x) for a given x. It is shown how quantum algorithm can find a point of maximum of F with the probability of error 2/3 applying this oracle 32\\sqrt{2^n} times. This algorithm is optimal in within constant factor in the following sense. Any other algorithm acting in substantially shorter time gives incorrect answer for the functions F with the single point of maximum chosen randomly with probability 1. The lower bound as Ømega (\\sqrt{2^n /b}) is established for the quantum search for solution of equations f(x)=1 where f is a Boolean function with b such solutions chosen at random with probability 1, which is a partial amplification of the result of M. Boyer, G. Brassard, P. Hoyer and A. Tapp.
We study the problem of finding the maximum or the minimum of a given set S = {x₀, X₁, ... X n₋₁}, each element X i drawn from some finite universe [Unary] of real numbers. We assume that the inputs are abstracted within an oracle O where we can only gain information through unary comparisons in the form "Is Xi greater than, equal to, or less than some constant k?" Classically, this problem is solved optimally with a runtime of Θ(n +lg|U|). In the setting of Quantum Computing, we show that at least Ω(√n+lg|U|) queries are required to solve the problem even with bounded error. Combining variants of the Grover's search [1, 2] algorithm and the optimal classical unary extrema finding algorithm, we have derived a series of new quantum algorithms, some running in time as fast as O(√n lg*n+lg|U|). This shows that quantum computers can accelerate the speed in the unary comparison model asymptotically. Inspecting our tools, we find convincing arguments that our lower bound is most probably tight, but we may need an entirely new approach to solve the problem optimally. The technique used in our algorithm can also be extended to solve variations of quantum statistics problems. For instance, our result can be directly extended to approximation of extrema of real numbers, similar to that of [3]. Moreover, we can also solve the quantum k-select problem optimally in time O(√kn) with constant success probability. We hope that our ideas and tools will prove to be useful in other areas.
The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality
The problem of searching for a given substring in the text was considered. It is known that classical algorithms solve this problem in a linear time depending on the length of the text and the specified template. Quantum algorithms speed up the search by “square root times”. In this paper, we proposed a quantum algorithm that solves the search problem a) with a high probability of getting the correct result and b) with the same acceleration (by “square root times”) as compared with the classical one, but it c) requires much less memory (based on the number of qubits used) than the previously known quantum algorithms.