This HTML5 document contains 77 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
n13http://dbpedia.org/resource/File:
foafhttp://xmlns.com/foaf/0.1/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n10http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
n12http://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
goldhttp://purl.org/linguistics/gold/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Grover's_algorithm
rdf:type
dbo:Software
rdfs:label
Grover's algorithm
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.
owl:sameAs
freebase:m.0f_fr yago-res:Grover's_algorithm
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Cite_web dbt:Further dbt:Pi dbt:Springer dbt:Wikiquote dbt:Math dbt:Use_American_English dbt:Quantum_computing
dct:subject
dbc:Search_algorithms dbc:Quantum_algorithms dbc:Post-quantum_cryptography
dbo:thumbnail
n10:Grover's_algorithm_circuit.svg?width=300
foaf:depiction
n10:Grovers_algorithm_geometry.png n10:Grover's_algorithm_circuit.svg
gold:hypernym
dbr:Algorithm
prov:wasDerivedFrom
n12:Grover's_algorithm?oldid=1073259268&ns=0
dbo:wikiPageID
58498
dbo:wikiPageLength
28985
dbo:wikiPageRevisionID
1073259268
dbo:wikiPageWikiLink
dbr:Hidden-variable_theory dbc:Quantum_algorithms dbr:Unitary_operator dbr:With_high_probability dbc:Post-quantum_cryptography dbr:Vladimir_Korepin dbr:Quantum_computing dbr:Mathematical_formulation_of_quantum_mechanics dbr:Time_complexity dbr:NP-completeness dbr:Lov_Grover dbr:Shor's_algorithm dbr:Subroutine dbr:Asymptotically_optimal_algorithm dbr:Symmetric-key_algorithm dbr:Bra–ket_notation dbr:Boolean_satisfiability_problem dbr:BHT_algorithm dbr:Quantum_threshold_theorem dbr:Umesh_Vazirani dbr:Quantum_logic_gate dbr:Collision_attack dbr:Expected_value dbr:Qubit dbr:Collision_problem dbr:NP_(complexity) dbr:Charles_H._Bennett_(physicist) dbr:Brute-force_attack n13:Grovers_algorithm_geometry.png dbr:Decision_tree_model dbr:Oracle_machine dbr:Black_box dbr:Jordan_normal_form dbr:Quantum_algorithm dbr:Ancilla_bit dbc:Search_algorithms dbr:Householder_transformation dbr:Measurement_in_quantum_mechanics n13:Grover's_algorithm_circuit.svg dbr:Pollard's_rho_algorithm dbr:Amplitude_amplification dbr:Gilles_Brassard dbr:GitHub dbr:WolframAlpha dbr:BQP dbr:Preimage_attack dbr:Domain_of_a_function dbr:Quantum_register dbr:Constraint_satisfaction_problem dbr:Uncomputation
dbo: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.
foaf:isPrimaryTopicOf
n12:Grover's_algorithm