Statements (24)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
quantum computer
|
| gptkbp:appliesTo |
unstructured search problems
|
| gptkbp:canBe |
NP-complete problems (as subroutine)
|
| gptkbp:classicalComplexity |
O(N)
|
| gptkbp:complexity |
O(sqrt(N))
|
| gptkbp:field |
gptkb:quantum_computing
|
| gptkbp:firstPublished |
gptkb:Proceedings_of_the_28th_Annual_ACM_Symposium_on_Theory_of_Computing
|
| https://www.w3.org/2000/01/rdf-schema#label |
Grover's algorithm
|
| gptkbp:inventedBy |
gptkb:Lov_Grover
|
| gptkbp:limitation |
not exponentially faster than classical
requires known number of solutions |
| gptkbp:numberOfQueries |
approximately pi/4 * sqrt(N)
|
| gptkbp:optimizedFor |
proven optimal for quantum search
|
| gptkbp:output |
index of target item
|
| gptkbp:purpose |
searching unsorted databases
|
| gptkbp:relatedTo |
gptkb:Deutsch–Jozsa_algorithm
gptkb:Shor's_algorithm |
| gptkbp:uses |
quantum superposition
oracle function quantum amplitude amplification |
| gptkbp:yearProposed |
1996
|
| gptkbp:bfsParent |
gptkb:Grover's_formula
gptkb:quantum_computing |
| gptkbp:bfsLayer |
5
|