Лекция 9. Квантовые алгоритмы с использованием чёрных ящиков

Мы обсудили явление вычислений с оракулом и определили использование оракулов в квантовом случае. Благодаря использованию явления запутанности можно решать некоторые задачи за меньшее ичсло обращений к оракулу, чем в классическом случае. Так, мы разобрали алгоритмы Дойча-Джозсы, Бернштейна-Вазирани и Саймона, в которых ясно видно такое улучшение.