Grover's algorithm
In quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.
- Comment
- enIn quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996.
- Depiction
- Has abstract
- enIn quantum computing, Grover's algorithm, also known as the quantum search algorithm, refers to a quantum algorithm for unstructured search that finds with high probability the unique input to a black box function that produces a particular output value, using just evaluations of the function, where is the size of the function's domain. It was devised by Lov Grover in 1996. The analogous problem in classical computation cannot be solved in fewer than evaluations (because, on average, one has to check half of the domain to get a 50% chance of finding the right input). Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that any quantum solution to the problem needs to evaluate the function times, so Grover's algorithm is asymptotically optimal. Since classical algorithms for NP-complete problems require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide polynomial-time solutions for NP-complete problems (as the square root of an exponential function is an exponential, not polynomial, function). Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when is large, and Grover's algorithm can be applied to speed up broad classes of algorithms. Grover's algorithm could brute-force a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. As a result, it is sometimes suggested that symmetric key lengths be doubled to protect against future quantum attacks.
- Hypernym
- Algorithm
- Id
- enp/q130020
- Is primary topic of
- Grover's algorithm
- Label
- enGrover's algorithm
- Link from a Wikipage to an external page
- davy.wtf/quantum/%3Fexample=Grover%27s%20Algorithm
- web.archive.org/web/20170116155032/http:/davy.wtf/quantum/%3Fexample=Grover%27s%20Algorithm
- arxiv.org/abs/quant-ph/0109116
- arxiv.org/abs/quant-ph/9605043
- demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/
- people.irisa.fr/Francois.Schwarzentruber/mit1_algo2_2013/grover_s_algorithm/
- web.archive.org/web/20140201230754/http:/www.bell-labs.com/user/feature/archives/lkgrover/
- twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm
- cryptome.org/qc-grover.htm
- tph.tuwien.ac.at/~oemer/qcl.html
- github.com/rmaestre/quantumSystem
- Link from a Wikipage to another Wikipage
- 3SAT
- Amplitude amplification
- Ancilla bit
- Asymptotically optimal algorithm
- BHT algorithm
- Black box
- BQP
- Bra–ket notation
- Brute-force attack
- Category:Post-quantum cryptography
- Category:Quantum algorithms
- Category:Search algorithms
- Charles H. Bennett (physicist)
- Collision attack
- Collision problem
- Constraint satisfaction problem
- Domain of a function
- Expected value
- File:Grover's algorithm circuit.svg
- File:Grovers algorithm geometry.png
- Gilles Brassard
- GitHub
- Hidden-variable theory
- Householder transformation
- Jordan form
- Lov Grover
- Mathematical formulation of quantum mechanics
- Measurement in quantum mechanics
- NP (complexity class)
- NP-completeness
- Oracle machine
- Pollard's rho algorithm
- Pre-image attack
- Quantum algorithm
- Quantum computing
- Quantum gate
- Quantum query complexity
- Quantum register
- Quantum threshold theorem
- Qubit
- Shor's algorithm
- Subroutine
- Symmetric-key algorithm
- Time complexity
- Umesh Vazirani
- Uncomputation
- Unitary operator
- Vladimir Korepin
- With high probability
- Wolfram Alpha
- SameAs
- 7grE
- Algorisme de Grover
- Algorithme de Grover
- Algoritmo de Grover
- Algoritmo de Grover
- Algoritmo di ricerca di Grover
- Algorytm Grovera
- Grover's algorithm
- Grover-Algorithmus
- Grover-algoritmus
- Groverin algoritmi
- Groverio algoritmas
- Groverov algoritam
- m.0f fr
- Q1028292
- Thuật toán Grover
- Алгоритм Гровера
- Алгоритм Ґровера
- אלגוריתם גרובר
- الگوریتم گرور
- ग्रोवर की कलनविधि
- グローバーのアルゴリズム
- 格罗弗算法
- Subject
- Category:Post-quantum cryptography
- Category:Quantum algorithms
- Category:Search algorithms
- Thumbnail
- Title
- enQuantum computation, theory of
- WasDerivedFrom
- Grover's algorithm?oldid=1106477232&ns=0
- WikiPageLength
- 29539
- Wikipage page ID
- 58498
- Wikipage revision ID
- 1106477232
- WikiPageUsesTemplate
- Template:Cite web
- Template:Further
- Template:Math
- Template:Pi
- Template:Quantum computing
- Template:Short description
- Template:Springer
- Template:Use American English
- Template:Wikiquote
