Tight bounds on quantum searching
Explore this paper's citation graph
Summary
A lower bound on the efficiency of any possible quantum database searching algorithm is provided and it is shown that Grover''s algorithm nearly comes within a factor 2 of being optimal in terms of the number of probes required in the table.
- Type
- article
- Published
- 1996-05-23
- Cited by
- 1,403
- References
- 18
- Access
- Open access
- OpenAlex
- https://openalex.org/W2020918964
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:10032711
Keywords
Simple (philosophy), Element (criminal law), Quantum algorithm, Quantum, Quantum phase estimation algorithm
References
- Quantum Mechanics Helps in Searching for a Needle in a Haystack
- Strengths and Weaknesses of Quantum Computing
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- Rapid solution of problems by quantum computation
- Discrete Logarithms and Factoring
- Searching a Quantum Phone Book
- A fast quantum mechanical algorithm for database search
- Elementary gates for quantum computation.
- Quantum cryptanalysis of hash and claw-free functions
- Algorithms for quantum computation: discrete logarithms and factoring
- Data Encryption Standard
- Quantum measurements and the Abelian Stabilizer Problem
- Data encryption standard
- Johnson: computers and intractability: a guide to the theory of np- completeness (freeman
Cited by
- Quantum complexity of graph and algebraic problems
- Design of Reversible/Quantum Ternary Comparator Circuits
- Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?
- An Indexed Bibliography of Genetic Algorithms Theory and Comparisons
- Classical and Quantum Algorithms for Finding Cycles
- A Hybrid System ASVR/NGARCH Tuned by Quantum-Based Minimization to Improve Forecasting Accuracy
- Lower bounds for quantum computation and communication
- Robust String Matching in O(√N+M) Quantum Queries
- Quantum set intersection and its application to associative memory
- A quantum decoding algorithm of the simplex code
- THE HIDDEN SUBGROUP PROBLEM - REVIEW AND OPEN PROBLEMS
- On quantum one-way permutations
- Physical systems for the solution of hard computational problems
- Design of Regular Reversible Quantum Circuits
- Optimization of Grover's Search Algorithm
- Improved output-sensitive quantum algorithms for Boolean matrix multiplication
- Simulation de systèmes quantiques sur un ordinateur quantique réaliste
- The exponential complexity of satisfiability problems
- Realization of a Quantum Scheduling Algorithm Using Nuclear Magnetic Resonance
- Constant-Time Quantum Algorithm For The Unstructured Search Problem
Related papers
No related papers recorded.