Quantum search with advice

DOI10.1007/978-3-642-18073-6_7MaRDI QIDQ3070978zbMATH OpenOpenAlexWikidataFDO

Authors Ashley Montanaro

Publication date 28 January 2011

Published in Theory of Quantum Computation, Communication, and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0908.3066

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: 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. We also give an efficient quantum algorithm for a variant of this task where the distribution is not known in advance, but must be queried at an additional cost. The algorithms are based on the use of Grover's quantum search algorithm and amplitude amplification as subroutines.

Recommendations

• Unconventional Computation
• scientific article; zbMATH DE number 2020426
• Quantum search with variable times
• A panoply of quantum algorithms
• scientific article; zbMATH DE number 1406118

Cited in

(6)

• Quantum key search with side channel advice
• Information weighted sampling for detecting rare items in finite populations with a focus on security
• A full characterization of quantum advice
• Further improvements of the estimation of key enumeration with applications to solving LWE
• Super-quadratic quantum speed-ups and guessing many likely keys
• Tighter bit-security bounds in quantum key search via the Chebyshev distance

This page was built for publication: Quantum search with advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3070978)