HackerPapers

arXiv:quant-ph/9706005quant-ph

Quantum computers can search arbitrarily large databases by a single query

Lov K. Grover

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

This paper shows that a quantum mechanical algorithm that can query information relating to multiple items of the database, can search a database in a single query (a query is defined as any question to the database to which the database has to return a (YES/NO) answer). 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).

arXiv comments
Several enhancements to the original paper
Journal reference
DOI
doi:10.1103/PhysRevLett.79.4709
Subjects
quant-phQuantum Physics

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Dec 2017 to Dec 2017.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. New silicon structure opens the gate to quantum computers 1 comment

    • > The answer I hear is that it helps solve the traveling salesman in record time, and that's all great and everything, but how will quantum computing be able to do things such as decrease the time it takes to train a RNN, or look up data in a database? "Quantum computers can…

      naaskingView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.