Fetching the paper…

Reading the bibliography…

Quantum search with advice · Around

2009

Quantum search with advice

Montanaro, Ashley

Original
PDF
Post on X

Understand

We consider the problem of search of an unstructured list for a marked element, when one is given advice as to where this element might be located, in the form of a probability distribution.

The goal is to minimise the expected number of queries to the list made to find the marked element, with respect to this distribution.
We present a quantum algorithm which solves this problem using an optimal number of queries, up to a constant factor.
For some distributions on the input, such as certain power law distributions, the algorithm can achieve exponential speed-ups over the best possible classical algorithm.

Built on

Randomized algorithms
R. Motwani and P. Raghavan · 1995
Earlier work this paper cites.
Quantum mechanics helps in searching for a needle in a haystack
L. Grover · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Grover’s quantum searching algorithm is optimal
C. Zalka · 1999
Earlier work this paper cites.

Similar

Arbitrary phases in quantum amplitude amplification
P. Høyer · 2000
Cited alongside, same era.
Quantum computation and quantum information
M. A. Nielsen and I. L. Chuang · 2000
Cited alongside, same era.
Average-case quantum query complexity
A. Ambainis and R. de Wolf · 2001
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.

Then

Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Later among the works it cites.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Later among the works it cites.
Creating superpositions that correspond to efficiently integrable probability distributions, 2002
L. Grover and T. Rudolph · 2002
Later among the works it cites.
Strong profiling is not mathematically optimal for discovering rare malfeasors
W. H. Press · 2009
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…