Фазовый запрос из битового оракула
Используя чёрный ящик для битового запроса
$$|X\rangle\otimes|b\rangle\longmapsto|X\rangle\otimes|b\oplus f(X)\rangle,$$
постройте чёрный ящик для фазового запроса
$$|X\rangle\longmapsto(-1)^{f(X)}|X\rangle.$$
Здесь $X=b_1b_2\ldots b_n$ — двоичная запись, а $|X\rangle=|b_1\rangle|b_2\rangle\cdots|b_n\rangle$.
Решения пока нет.