Content deleted Content added
→QAOA: QAOA link |
m Add Bernstein-Vazirani algorithm sub-section. |
||
Line 26:
The Deutsch–Jozsa algorithm solves a [[black-box]] problem which probably requires exponentially many queries to the black box for any deterministic classical computer, but can be done with exactly one query by a quantum computer. If we allow both bounded-error quantum and classical algorithms, then there is no speedup since a classical probabilistic algorithm can solve the problem with a constant number of queries with small probability of error. The algorithm determines whether a function ''f'' is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input ___domain and 0 for the other half).
===Bernstein-Vazirani algorithm===
{{main|Bernstein-Vazirani algorithm}}
The Bernstein-Vazirani algorithm was the first quantum algorithm that was exponentially more efficient than classical algorithms. It was designed to create an [[oracle separation]] between [[BQP]] and [[BPP]].
===Simon's algorithm===
| |||