|
gptkbp:instanceOf
|
quantum computer
|
|
gptkbp:application
|
theoretical demonstration of quantum advantage
|
|
gptkbp:classicalComplexity
|
O(2^n)
|
|
gptkbp:complexity
|
quantum polynomial time
|
|
gptkbp:demonstrates
|
quantum speedup
|
|
gptkbp:designedBy
|
gptkb:David_Deutsch
gptkb:Richard_Jozsa
|
|
gptkbp:field
|
gptkb:quantum_computing
|
|
gptkbp:hasConcept
|
gptkb:Hadamard_transform
interference
superposition
quantum oracle
quantum parallelism
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
Deutsch–Jozsa algorithm
|
|
gptkbp:input
|
black-box function
|
|
gptkbp:introducedIn
|
1992
|
|
gptkbp:namedAfter
|
gptkb:David_Deutsch
gptkb:Richard_Jozsa
|
|
gptkbp:notableFor
|
first quantum algorithm to show exponential speedup over classical algorithms
|
|
gptkbp:output
|
boolean value
|
|
gptkbp:publishedIn
|
gptkb:Proceedings_of_the_Royal_Society_of_London_A
|
|
gptkbp:quantumComplexity
|
O(1)
|
|
gptkbp:relatedTo
|
gptkb:Grover's_algorithm
gptkb:Bernstein–Vazirani_algorithm
gptkb:Shor's_algorithm
gptkb:Simon's_algorithm
|
|
gptkbp:solvedBy
|
gptkb:Deutsch–Jozsa_problem
|
|
gptkbp:bfsParent
|
gptkb:quantum_computing
gptkb:Deutsch_algorithm
|
|
gptkbp:bfsLayer
|
5
|