Quantum algorithms of promised problems
28 Março 2022, 16:30 • André Souto
Recap on query model in quantum computation and on Deutsch problem.
The Deutsch-Jozsa problem: classical and quantum solutions. (with a constant gap for randomized algorithms)
The Berstein-Vazirani problem: classical and quantum solutions. (with a linear gap for randomized algorithms)
The Simon problem: classical and quantum solutions. (with an exponential gap for randomized algorithms)