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

Fastest Quantum Search for Extreme Point

Yuri Ozhigov

Published May 31, 1998• 0 citations
OpenAlex

Abstract

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.

Related papers

Lower bounds of a quantum search for an extreme point

Yuri Ozhigov

We show that Durr and Hoyer's quantum algorithm of searching for an extreme point of an integer function cannot be sped up for functions that are chosen randomly. Any other algorithm acting in a substantially shorter time o(√2n) (n →α) gives an incorrect answer for the functions phi with the single point of maximum chosen randomly with probability Perr →1. The lower bound as Ω(√2n /b) is established for the quantum search for solution of the equation f (x) = 1, where f is a Boolean function with b such solutions chosen at random with asymptotic probability 1 (n→α).

arXiv:quant-ph/9806001•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Jun 8, 1999•4 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

Asymptotic Quantum Search and a Quantum Algorithm for Calculation of a Lower Bound of the Probability of Finding a Diophantine Equation That Accepts Integer Solutions

Rubens Viana Ramos, Juliana Loureiro de Oliveira

Several mathematical problems can be modeled as a search in a database. An example is the problem of finding the minimum of a function. Quantum algorithms for solving this problem have been proposed and all of them use the quantum search algorithm as a subroutine and several intermediate measurements are realized. In this work, it is proposed a new quantum algorithm for finding the minimum of a function in which quantum search is not used as a subroutine and only one measurement is needed. This is also named asymptotic quantum search. As an example, we propose a quantum algorithm based on asymptotic quantum search and quantum counting able to calculate a lower bound of the probability of finding a Diophantine equation with integer solution.

arXiv:0809.1538•Sep 9, 2008•0 citations

Robust Quantum Algorithms with $\eps$-Biased Oracles

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

This paper considers the quantum query complexity of {\it $\eps$-biased oracles} that return the correct value with probability only $1/2 + \eps$. In particular, we show a quantum algorithm to compute $N$-bit OR functions with $O(\sqrt{N}/{\eps})$ queries to $\eps$-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\eps}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper by Iwama et al. affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of $\eps$. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of $\eps$.

arXiv:quant-ph/0605077•May 8, 2006•3 citations

Is partial quantum search of a database any easier?

Lov K. Grover, Jaikumar Radhakrishnan

We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).

arXiv:quant-ph/0407122•ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)•Jul 18, 2005•48 citations

Upper bounds for quantum biased oracles with explicit bias rate(New Trends in Theory of Computation and Algorithm)

Tomoya Suzuki, Shigeru Yamashita, Masaki Nakanishi +1 more

We investigate the query complexity of quantum biased oracles.$\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{o}\mathrm{s}\epsilon$ that the biased oracles answer queries correctly with probability at least $1/2+\epsilon$ .Given such an oracle, we present an algorithm to simulate a single query to an oracle that answers queries $\mathrm{C}\mathrm{O}\alpha \mathrm{e}\mathrm{c}\mathrm{u}_{\mathrm{y}}$ with probability at least 2/3, using $0(1/\epsilon)$ queries to the given oracle.For searching problems, combining the algorithm with a known result.we can obtain an optimal algorithm.The simulating algorithm works effectively when we know the value of $\epsilon$ .We also consider the situation where no knowledge about $\epsilon$ is given.

数理解析研究所講究録•May 1, 2006•0 citations
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 show that Durr and Hoyer's quantum algorithm of searching for an extreme point of an integer function cannot be sped up for functions that are chosen randomly. Any other algorithm acting in a substantially shorter time o(√2n) (n →α) gives an incorrect answer for the functions phi with the single point of maximum chosen randomly with probability Perr →1. The lower bound as Ω(√2n /b) is established for the quantum search for solution of the equation f (x) = 1, where f is a Boolean function with b such solutions chosen at random with asymptotic probability 1 (n→α).
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.
Several mathematical problems can be modeled as a search in a database. An example is the problem of finding the minimum of a function. Quantum algorithms for solving this problem have been proposed and all of them use the quantum search algorithm as a subroutine and several intermediate measurements are realized. In this work, it is proposed a new quantum algorithm for finding the minimum of a function in which quantum search is not used as a subroutine and only one measurement is needed. This is also named asymptotic quantum search. As an example, we propose a quantum algorithm based on asymptotic quantum search and quantum counting able to calculate a lower bound of the probability of finding a Diophantine equation with integer solution.
This paper considers the quantum query complexity of {\it $\eps$-biased oracles} that return the correct value with probability only $1/2 + \eps$. In particular, we show a quantum algorithm to compute NNN-bit OR functions with $O(\sqrt{N}/{\eps})$ queries to $\eps$-biased oracles. This improves the known upper bound of $O(\sqrt{N}/{\eps}^2)$ and matches the known lower bound; we answer the conjecture raised by the paper by Iwama et al. affirmatively. We also show a quantum algorithm to cope with the situation in which we have no knowledge about the value of $\eps$. This contrasts with the corresponding classical situation, where it is almost hopeless to achieve more than a constant success probability without knowing the value of $\eps$.
We consider the partial database search problem where given a quantum database f : {0,1}n→{0,1} such that f(x) =1 for a unique x ∈ {0,1}n, we are required to determine only the first k bits of the address x. We present an algorithm and derive a lower bound for this problem. Let q(k,n) be the minimum number of queries needed to find the first k bits of the required address x with certainty (or with very high probability, say 1--O(N--¼)). We show that there exist constants ck (corresponding to the algorithm) and dk (corresponding to the lower bound) such that πover4 (1--dkover√K) √N ≤ q(k,n) ≤ πover4 (1--ckover√K) √N, where K=2k and N=2n. Our algorithm returns the correct answer with probability 1--O(N--½), and can be easily modified to give the correct answer with certainty. The lower bound for algorithms that return the correct answer with certainty is proved by reducing the usual database search problem to this partial search problem, and invoking Zalka's lower bound showing that Grovers algorithm is optimal for the usual database search problem. We then derive a lower bound that is applicable for database search algorithms that err with small probability, and use it to show that our lower bound also applies to partial search algorithms that return the correct answer with probability at least 1--O(N--¼).
We investigate the query complexity of quantum biased oracles.Supposϵ\mathrm{S}\mathrm{u}\mathrm{p}\mathrm{p}\mathrm{o}\mathrm{s}\epsilonSupposϵ that the biased oracles answer queries correctly with probability at least 1/2+ϵ1/2+\epsilon1/2+ϵ .Given such an oracle, we present an algorithm to simulate a single query to an oracle that answers queries COαecuy\mathrm{C}\mathrm{O}\alpha \mathrm{e}\mathrm{c}\mathrm{u}_{\mathrm{y}}COαecuy​ with probability at least 2/3, using 0(1/ϵ)0(1/\epsilon)0(1/ϵ) queries to the given oracle.For searching problems, combining the algorithm with a known result.we can obtain an optimal algorithm.The simulating algorithm works effectively when we know the value of ϵ\epsilonϵ .We also consider the situation where no knowledge about ϵ\epsilonϵ is given.