2017/10/30 by Daniel Z. Zanger, Zanger, Daniel Z.
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph
paper · pdf · doi:10.48550/arxiv.1710.10790
arxiv created 2017/10/30 · openalex publication_date 2017/10/30 · arxiv updated 2017/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the SEARCH WITH ADVICE problem, a single entry of interest within a database of N entries is to be found assuming that an ordering of the entries, from that with the highest probability of being the entry of interest (as determined by a so-called advice distribution) to that with the lowest, is provided. We present a quantum algorithm that, in the presence of significant levels of quantum noise, solves SEARCH WITH ADVICE for a power law advice distribution with average-case query complexity O(1) as N tends to infinity. Since as we also show the best classical algorithms for this problem exhibit average-case query complexity of order no better than log(N), our quantum algorithm provides a super-exponential reduction in query complexity.