3 кубита
Deutsch–Jozsa
Обобщение алгоритма Дойча на n бит — экспоненциальное разделение.
История
Расширен Дойчем и Ричардом Йозсой в 1992 году.
Задача
Определить, константна f или сбалансирована для n-битного входа.
Математика
Суперпозиция всех входов + оракул + обратное QFT-подобное преобразование.
Сложность
1 запрос vs 2^(n-1)+1 классически
vs Классика
Экспоненциальное разделение сложности.