© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

Quantum algorithms for finding extrema with unary predicates

Man Hon Chan

Published Jan 1, 2011• 0 citations

Abstract

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.

DOI: 10.14288/1.0052063

Related papers

Robust quantum minimum finding with an application to hypothesis selection

Yihui Quek, Clément L. Canonne, Patrick Rebentrost

We consider the problem of finding the minimum element in a list of length $N$ using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least $α$ by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than $α$, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time $\tilde O(\sqrt{N (1+Δ)})$, where $Δ$ is an upper-bound on the number of elements within the interval $α$, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of $N$ known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution $O(\varepsilon)$-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from $O(N^2)$ to $O(N)$, in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is $\tilde O( \sqrt{N(1+Δ)})$, with the same $O(\log N)$ sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.

arXiv:2003.11777•Mar 26, 2020•4 citations

Convex optimization using quantum oracles

Joran van Apeldoorn, András Gilyén, Sander Gribling +1 more

We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.

arXiv:1809.00643•Quantum•Jan 13, 2020•35 citations

Optimal quantum searching to find a common element of two sets

Avatar Tulsi

Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.

arXiv:1210.4648•Oct 17, 2012•1 citation

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

Quantum Information and Computation•May 1, 2009•7 citations

Exact quantum lower bound for Grover's problem

Catalin Dohotaru, Peter Høyer

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

arXiv:0810.3647•Quantum Information and Computation•May 1, 2009•4 citations

Grover’s quantum search algorithm and Diophantine approximation

Shahar Dolev, Itamar Pitowsky, Boaz Tamir

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size $N$ by using only $O(\sqrt{N})$ queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either $M$ or $K$, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let $m$ be the required number of iterations; we prove that under certain restrictions on the sizes of $M$ and $K$ the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.

arXiv:quant-ph/0507234•Physical Review A•Feb 3, 2006•3 citations

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.

We consider the problem of finding the minimum element in a list of length

N

using a noisy comparator. The noise is modelled as follows: given two elements to compare, if the values of the elements differ by at least

α

by some metric defined on the elements, then the comparison will be made correctly; if the values of the elements are closer than

α

, the outcome of the comparison is not subject to any guarantees. We demonstrate a quantum algorithm for noisy quantum minimum-finding that preserves the quadratic speedup of the noiseless case: our algorithm runs in time

\tilde O(\sqrt{N (1+Δ)})

, where

Δ

is an upper-bound on the number of elements within the interval

α

, and outputs a good approximation of the true minimum with high probability. Our noisy comparator model is motivated by the problem of hypothesis selection, where given a set of

N

known candidate probability distributions and samples from an unknown target distribution, one seeks to output some candidate distribution

O(\varepsilon)

-close to the unknown target. Much work on the classical front has been devoted to speeding up the run time of classical hypothesis selection from

O(N^2)

to

O(N)

, in part by using statistical primitives such as the Scheffé test. Assuming a quantum oracle generalization of the classical data access and applying our noisy quantum minimum-finding algorithm, we take this run time into the sublinear regime. The final expected run time is

\tilde O( \sqrt{N(1+Δ)})

, with the same

O(\log N)

sample complexity from the unknown distribution as the classical algorithm. We expect robust quantum minimum-finding to be a useful building block for algorithms in situations where the comparator (which may be another quantum or classical algorithm) is resolution-limited or subject to some uncertainty.

We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.

Given two sets A and B and two oracles O(A) and O(B) that can identify the elements of these sets respectively, the goal is to find an element common to both sets using minimum number of oracle queries. Each application of either O(A) or O(B) is taken as a single oracle query. This is basically a search problem and a straightforward application of Grover algorithm can solve this problem but its performance is slow compared to the optimal one by a constant factor of 1.57. Here we present a variant of Grover algorithm which achieves the optimal performance in not too restrictive cases.

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

One of the most important quantum algorithms ever discovered is Grover's algorithm for searching an unordered set. We give a new lower bound in the query model which proves that Grover's algorithm is exactly optimal. Similar to existing methods for proving lower bounds, we bound the amount of information we can gain from a single oracle query, but we bound this information in terms of angles. This allows our proof to be simple, self-contained, based on only elementary mathematics, capturing our intuition, while obtaining at the same time an exact bound.

In a fundamental paper [Phys. Rev. Lett. 78, 325 (1997)] Grover showed how a quantum computer can find a single marked object in a database of size

N

by using only

O(\sqrt{N})

queries of the oracle that identifies the object. His result was generalized to the case of finding one object in a subset of marked elements. We consider the following computational problem: A subset of marked elements is given whose number of elements is either

M

or

K

, our task is to determine which is the case. We show how to solve this problem with a high probability of success using iterations of Grover's basic step only, and no other algorithm. Let

m

be the required number of iterations; we prove that under certain restrictions on the sizes of

M

and

K

the estimation $m<2\sqrt{N}∕(\sqrt{K}\ensuremath{-}\sqrt{M})$ obtains. This bound reproduces previous results based on more elaborate algorithms, and is known to be optimal up to a constant factor. Our method involves simultaneous Diophantine approximations, so that Grover's algorithm is conceptualized as an orbit of an ergodic automorphism of the torus. We comment on situations where the algorithm may be slow, and note the similarity between these cases and the problem of small divisors in classical mechanics.