2 кубита
Алгоритм Дойча
Первый квантовый алгоритм, показавший преимущество над классическим вычислением.
История
Предложен Дэвидом Дойчем в 1985 году.
Задача
Определить, является ли функция f:{0,1}→{0,1} константной или сбалансированной.
Математика
Использует интерференцию: H·U_f·H на верхнем кубите.
Сложность
1 запрос vs 2 классически
vs Классика
Классически нужно 2 вычисления функции, квантово — 1.