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/9911082

A Quantum Algorithm for finding the Maximum

Ahuja, Ashish, Sanjiv Kapoor

Published Nov 18, 1999• 42 citations
arXivHTMLPDF

Abstract

This paper describes a quantum algorithm for finding the maximum among N items. The classical method for the same problem takes O(N) steps because we need to compare two numbers in one step. This algorithm takes O(sqrt(N)) steps by exploiting the property of quantum states to exist in a superposition of states and hence performing an operation on a number of elements in one go. A tight upper bound of 6.8(sqrt(N)) for the number of steps needed using this algorithm was found. These steps are the number of queries made to the oracle.

DOI
10.48550/arxiv.quant-ph/9911082

Related papers

Quantum Search Algorithm

Che‐Ming Li, Jin-Yuan Hsieh, Der-San Chuu

IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.

InTech eBooks•Apr 26, 2011•0 citations

Solving a problem in the quantum way

M.P. John

A general quantum algorithm for solving a problem is discussed. The number of steps required to solve a problem using this method is independent of the number of cases that has to be considered classically. Hence, it is more efficient than existing classical algorithms or quantum algorithm, which requires O(sqrt(N)) steps.

arXiv:quant-ph/0301153•Jan 28, 2003•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

Complex Quantum Queries

Lov K. Grover

A quantum mechanical computer can search a database consisting of N items in O(sqrt(N)) elementary quantum queries (a query is defined as any question to the database to which a binary (YES/NO) answer is required; an elementary query is a query pertaining to only one of the N possible states). A classical computer would take at least O(N) elementary queries. This paper shows that a quantum mechanical algorithm that can query information relating to multiple states, can search the database in a single query. A classical algorithm will be limited to the information theoretic bound of at least O(log N)queries (which it would achieve by using a binary search). A similar result was recently independently obtained by Terhal & Smolin by a different method.

•Jun 3, 1997•0 citations

How fast can a quantum computer search?

Lov K. Grover

This paper gives a simple proof of why a quantum computer, despite being in all possible states simultaneously, needs at least 0.707 sqrt(N) queries to retrieve a desired item from an unsorted list of items. The proof is refined to show that a quantum computer would need at least 0.785 sqrt(N) queries. The quantum search algorithm needs precisely this many queries.

arXiv:quant-ph/9809029•Sep 10, 1998•21 citations

Efficient Quantum State Synthesis with One Query

Gregory Rosenthal

We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state |ψ〉 there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of |ψ〉. Previous algorithms for this problem either used a linear number of queries and polynomial time, or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime. As corollaries we do the following:

arXiv:2306.01723•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2024•5 citations
This paper describes a quantum algorithm for finding the maximum among N items. The classical method for the same problem takes O(N) steps because we need to compare two numbers in one step. This algorithm takes O(sqrt(N)) steps by exploiting the property of quantum states to exist in a superposition of states and hence performing an operation on a number of elements in one go. A tight upper bound of 6.8(sqrt(N)) for the number of steps needed using this algorithm was found. These steps are the number of queries made to the oracle.
IntroductionFor a search problem associated with a unsorted database, the remarkable Grover's quantum algorithm (1) provides a quadratic speedup over its classical counterpart.The search problem can be described as follows: for a given function f , there exists one unknown element in the set {0, 1, ..., N -1} that satisfies f (x)=-1, say x = τ, whereas the other N -1o n e sg i v e f (x)=1.How many times of evaluations of f are required to determine the element τ for f (τ)=-1?Through a conventional algorithm, one needs O(N) trials to achieve this aim.How about the utility of quantum algorithm for the search?For the scenario in the quantum world, the search problem can be rephrased in the quantum mechanical language: for a given unitary operator I τ , that is sometimes called the oracle operator, and a set of state vectors (orthonormal basis): s = {|0 , |1 , ..., |N -1 }, I τ |x = |x for all states in the set except I τ |x = -|x for x = τ.H owma n yqueriesofI τ are required to determine |τ ?By Grover's algorithm, one needs only O( √ N) quantum mechanical steps to find the marked state |τ out.It has been shown that Grover's algorithm is optimal since it needs minimal oracle calls to perform a quantum search (2).The quantum searching process will be briefly reviewed as follows.The first step of Grover's algorithm is to prepare a superposition state of all elements with uniform probability amplitude:Then apply the Grover kernel G = -I η I τ to |s ,w h er eI η is a unitary operator and contains no bias against the marked state.For large N,a f t e ra b o u tm = π √ N/4 repetitions of G operations, the probability to observe |τ is close to one, i.e., G m |s ∼ |τ .( 2 ) Since every single G involves one query of I τ ,onlyO( √ N) searching steps are required for a quantum search task.In what follows, we will first investigate on the general SU(2) formulation for the kernel of Grover's searching operator G.The discussions of quantum searching certainty, robustness, and the analog analogue version of the Grover's algorithm will be given afterwards.
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.
A quantum mechanical computer can search a database consisting of N items in O(sqrt(N)) elementary quantum queries (a query is defined as any question to the database to which a binary (YES/NO) answer is required; an elementary query is a query pertaining to only one of the N possible states). A classical computer would take at least O(N) elementary queries. This paper shows that a quantum mechanical algorithm that can query information relating to multiple states, can search the database in a single query. A classical algorithm will be limited to the information theoretic bound of at least O(log N)queries (which it would achieve by using a binary search). A similar result was recently independently obtained by Terhal & Smolin by a different method.