A fast quantum mechanical algorithm for database search

Lov K. Grover · Symposium on the Theory of Computing · 1996

Summary

In early 1994, it was demonstrated that a quantum mechanical computer could efficiently solve a well-known problem for which there was no known efficient algorithm using classical computers, i.e. testing whether or not a given integer, N, is prime, in a time which is a finite power of o (logN) .

Type: article
Published: 1996-05-29
Cited by: 10,283
References: 23
Access: Open access
DOI: https://doi.org/10.1145/237814.237866
arXiv: https://arxiv.org/abs/quant-ph/9605043
OpenAlex: https://openalex.org/W2084652510
Semantic Scholar: https://api.semanticscholar.org/CorpusID:207198067

Keywords

Citation, Computer science, Information retrieval, Database, Algorithm

References

A fast quantum mechanical algorithm for estimating the medianLov K. Grover — 1996
Oracle Quantum ComputingAndré Berthiaume, Gilles Brassard — 1992
Matching is as easy as matrix inversionKetan Mulmuley, Umesh Vazirani, Vijay V. Vazirani — 1987
Quantum complexity theoryEthan Bernstein, Umesh Vazirani — 1993
Scheme for reducing decoherence in quantum computer memory.Peter W. Shor — 1995
Strengths and Weaknesses of Quantum ComputingCharles H. Bennett, Ethan Bernstein, Gilles Brassard — 1997
NP is as easy as detecting unique solutionsLeslie G. Valiant, Vijay V. Vazirani — 1985
Tight bounds on quantum searchingMichel Boyer, Gilles Brassard, Peter Høyer — 1996
QUANTUM SEEING IN THE DARKPaul G. Kwiat, Harald Weinfurter, Anton Zeilinger — 1996
Rapid solution of problems by quantum computationDavid Deutsch, Richard Jozsa — 1992
The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machinesPaul Benioff — 1980
The Emperor's New MindRoger Penrose, Martin Gardner — 1989
Quantum mechanical interaction-free measurementsAvshalom C. Elitzur, Lev Vaidman — 1993
Efficient networks for quantum factoring.David Beckman, Amalavoyal N. Chari, Devabhaktuni Srikrishna — 1996
On the power of quantum computationDaniel Simón — 1994
Quantum theory, the Church–Turing principle and the universal quantum computerDavid Deutsch — 1985
A Quantum Algorithm for Finding the MinimumGaspers, Serge, Li, Jerry Zirui — 1996
The quantum challenge to structural complexity theoryAndré Berthiaume, Gilles Brassard — 1992
Quantum Circuit ComplexityAndrew Chi-Chih Yao — 1993
Algorithms for quantum computation: discrete logarithms and factoringPeter W. Shor — 1994

Cited by

Dynamics of bright solitary matter-wavesT. P. Wiles — 2013
Efficient Color Transformations on Quantum ImagesPhuc Q. Le, Abdullah M. Iliyasu, Fangyan Dong — 2011
Quantum Algorithms in Hilbert DatabaseMichail Zak — 2003
Quantum random walks on congested lattices and the effect of dephasingKeith R. Motes, Alexei Gilchrist, Peter P. Rohde — 2013
Discussing the explanation of the quantum speed upGiuseppe Castagnoli — 2009
Quantum Fourier transforms for extracting hidden linear structures in finite fieldsJ. Niel de Beaudrap, Richard Cleve, John Watrous — 2000
Characterization Of Single Defects In Zinc OxideY. Pai — 2014
Design of Reversible/Quantum Ternary Comparator CircuitsMozammel H. A. Khan — 2008
The vectorial λ-calculusPablo Arrighi, Alejandro Díaz-Caro, Benoît Valiron — 2017
White Noise in Quantum Random Walk Search AlgorithmЛей Ма, Du Jiang-Feng, Yun Li — 2006
Towards optical quantum information processing using Rydberg dark-state polaritonsDavid Paredes-Barato — 2014
Collapsing a Perfect Superposition to a Chosen Quantum State without MeasurementAhmed Younes, Mahmoud Abdel‐Aty — 2014
Adiabatic Quantum Simulation of Quantum ChemistryShara Lee Highgate — 2013
Extreme Quantum Advantage when Simulating Classical Systems with Long-Range Interaction敬治松村 — 2017
One-out-of-two Quantum Oblivious Transfer based on Nonorthogonal StatesYao–Hsin Chou, Guo-Jyun Zeng, Yu-Shan Yang — 2017
A Quantum-Inspired Similarity Measure for the Analysis of Complete Weighted GraphsArsenio Moreno Mendoza — 2019
Computational perspectives on Bell Inequalities and many-body quantum correlationsMatty J. Hoban — 2012
Cost analysis of hash collisions : will quantum computers make SHARCS obsolete?Daniel J. Bernstein — 2009
Investigation of Monolithic Erbium-Doped Resonators for Application in Cavity Quantum ElectrodynamicsMark Hogg — 2014
Grover's Algorithm applied to the Molecular Distance Geometry ProblemCarlile Lavor, Leo Liberti, Nelson Maculan — 2016

A fast quantum mechanical algorithm for database search

Summary

Keywords

References

Cited by

Related papers