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

arXiv:quant-ph/9806001 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Lower bounds of a quantum search for an extreme point

Yuri Ozhigov

Published Jun 8, 1999• 4 citations
arXivHTMLPDF

Abstract

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

DOI
10.1098/rspa.1999.0397

Related papers

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

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

An Optimized Quantum Maximum or Minimum Searching Algorithm and its Circuits

Yanhu Chen, Shijie Wei, Xiong Gao +3 more

Finding a maximum or minimum is a fundamental building block in many mathematical models. Compared with classical algorithms, Durr, Hoyer's quantum algorithm (DHA) achieves quadratic speed. However, its key step, the quantum exponential searching algorithm (QESA), which is based on Grover algorithm, is not a sure-success algorithm. Meanwhile, quantum circuits encounter the gate decomposition problem due to variation of the scale of data. In this paper, we propose an optimized quantum algorithm for searching maximum and minimum, based on DHA and the optimal quantum exact search algorithm. Furthermore, we provide the corresponding quantum circuits, together with three equivalent simplifications. In circumstances when we can exactly estimate the ratio of the number of solutions M and the searched space N, our method can improve the successful probability close to 100%. Furthermore, compared with DHA, our algorithm shows an advantage in complexity with large databases and in the gate complexity of constructing oracles. Experiments have been executed on an IBM superconducting processor with two qubits, and a practical problem of finding the minimum from Titanic passengers' age was numerically simulated. Both showed that our optimized maximum or minimum performs more efficiently compared with DHA. Our algorithm can serve as an important subroutine in various quantum algorithms which involves searching maximum or minimum.

arXiv:1908.07943•Aug 21, 2019•4 citations

On the Complexity of Searching Maximum of a Function on a Quantum Computer

Maciej Goćwin

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

arXiv:quant-ph/0507060•Jul 6, 2005•1 citation

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

Lower Bounds for Quantum Search and Derandomization

Harry Buhrman, Ronald de Wolf

We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.

arXiv:quant-ph/9811046•Nov 18, 1998•12 citations
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→α).
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.
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.
Finding a maximum or minimum is a fundamental building block in many mathematical models. Compared with classical algorithms, Durr, Hoyer's quantum algorithm (DHA) achieves quadratic speed. However, its key step, the quantum exponential searching algorithm (QESA), which is based on Grover algorithm, is not a sure-success algorithm. Meanwhile, quantum circuits encounter the gate decomposition problem due to variation of the scale of data. In this paper, we propose an optimized quantum algorithm for searching maximum and minimum, based on DHA and the optimal quantum exact search algorithm. Furthermore, we provide the corresponding quantum circuits, together with three equivalent simplifications. In circumstances when we can exactly estimate the ratio of the number of solutions M and the searched space N, our method can improve the successful probability close to 100%. Furthermore, compared with DHA, our algorithm shows an advantage in complexity with large databases and in the gate complexity of constructing oracles. Experiments have been executed on an IBM superconducting processor with two qubits, and a practical problem of finding the minimum from Titanic passengers' age was numerically simulated. Both showed that our optimized maximum or minimum performs more efficiently compared with DHA. Our algorithm can serve as an important subroutine in various quantum algorithms which involves searching maximum or minimum.
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 prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.