About: Grover's algorithm

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Grover's algorithm Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Software, within Data Space : el.dbpedia.org associated with source document(s)

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.

Attributes	Values
rdf:type	software
rdfs:label	Grover's algorithm (en)
rdfs:comment	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. (en)
sameAs	Grover's algorithm Grover's algorithm
dbp:wikiPageUsesTemplate	dbt:Cite_web dbt:Further dbt:Math dbt:Pi dbt:Short_description dbt:Use_American_English dbt:Wikiquote dbt:Springer dbt:Quantum_computing
Subject	Post-quantum cryptography Quantum algorithms Search algorithms
thumbnail	wiki-commons:Special:FilePath/Grover's_algorithm_circuit.svg?width=300
foaf:depiction
gold:hypernym	Algorithm
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Grover's_algorithm?oldid=1073259268&ns=0
Wikipage page ID	58498 (xsd:integer)
page length (characters) of wiki page	28985 (xsd:nonNegativeInteger)
Wikipage revision ID	1073259268 (xsd:integer)
Link from a Wikipage to another Wikipage	NP-completeness NP-completeness Umesh Vazirani Uncomputation Unitary operator Amplitude amplification Ancilla bit Asymptotically optimal algorithm BHT algorithm BQP Black box Boolean satisfiability problem Vladimir Korepin Bra–ket notation Brute-force attack Post-quantum cryptography Quantum algorithms Search algorithms Gilles Brassard GitHub Jordan normal form Domain of a function Quantum algorithm Quantum computing Quantum logic gate Quantum register Quantum threshold theorem Qubit With high probability WolframAlpha Charles H. Bennett (physicist) Decision tree model Householder transformation Preimage attack Time complexity Collision attack Constraint satisfaction problem Hidden-variable theory Oracle machine Symmetric-key algorithm Expected value Lov Grover Subroutine Mathematical formulation of quantum mechanics Measurement in quantum mechanics Pollard's rho algorithm Shor's algorithm Collision problem
has abstract	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. 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 researchers generally believe that NP-complete problems are difficult because their search spaces have essentially no structure, the optimality of Grover's algorithm for unstructured search suggests (but does not prove) that quantum computers cannot solve NP-complete problems in polynomial time. 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. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Grover's_algorithm
is Wikipage redirect of	Quadratic speedup theorem Quantum partial search Grovers algorithm Grover algorithm Grover search algorithm
is Link from a Wikipage to another Wikipage of	List of terms relating to algorithms and data structures Mølmer–Sørensen gate 1996 in science 1999 in science Aanderaa–Karp–Rosenberg conjecture Amplitude amplification BHT algorithm BQP Binary search algorithm Lenstra elliptic-curve factorization Cryptanalysis Crypto-shredding Key size Counterfactual quantum computation List of algorithms Index of cryptography articles Index of physics articles (G) DiVincenzo's criteria

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (72 GB total memory, 1 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software