Math
Один вопрос, заданный однажды
Чёрный ящик считает функцию f из n битов в один бит, и спрашивать его можно только про входы. Чтобы наверняка узнать, постоянна она или сбалансирована, классически нужно полтаблицы плюс один вызов. Адамар на все, ОДИН вызов с ответом в виде знака, снова Адамар — и исход «все нули» решает дело. Таблица истинности здесь кликается, так что обещание можно нарушить руками: для любой таблицы ответ выпадает с вероятностью (1 − 2k/N)². А если таблица оказалась f(x) = s·x, тот же один вызов возвращает саму строку s.
Что происходит
Чёрный ящик считает какую-то функцию f из n битов в один бит. Обещано, что она либо постоянна, либо сбалансирована — один и тот же ответ везде, или один ответ ровно на половине входов, — и надо сказать, что именно. Классически обхода нет: половина таблицы может совпадать, а следующая запись всё испортит, поэтому уверенность стоит N/2 + 1 вызовов. Девять при шестнадцати входах, тридцать три при шестидесяти четырёх. Теперь квантовый вариант, и он в три строки. Адамар на каждый кубит — все N входов спрошены разом. Вызов оракула, который отвечает не битом, а ЗНАКОМ: ставит минус на каждый вход, где f равна единице. Снова Адамар на каждый кубит. Измерить. Если все кубиты прочитались нулями — функция была постоянной; что угодно другое означает сбалансированную, и всё это заняло один вызов. Модуль больше, чем демонстрация, потому что таблица истинности сверху кликается. Нарушь обещание: переверни одну ячейку — и f не постоянна и не сбалансирована, а алгоритм не ломается, он ухудшается на величину, которую можно выписать. Для ЛЮБОЙ таблицы исход «все нули» имеет вероятность (1 − 2k/N)², где k — сколько в таблице единиц. Постоянная — это k = 0, и получается единица. Сбалансированная — k = N/2, и получается ровно ноль. Одна перевёрнутая ячейка при шестнадцати входах даёт 4/256, один прогон из шестидесяти четырёх, и панель называет это число прежде, чем ты станешь считать. Вот чего стоит обещание внутри алгоритма, в цифрах. Здесь прячется и второе. Когда таблица оказывается линейной — f(x) = s·x mod 2 для какой-то скрытой строки s, — те же три шага не просто отвечают «да» или «нет»: исходом становится сама s, с вероятностью единица, а у всех прочих исходов вероятность ровно ноль. Это Бернштейн — Вазирани, и классически она стоит n вызовов, по одному на бит s. Спроси один раз — прочти всю строку. Под обоими фактами одна формула: амплитуда исхода y — это преобразование Уолша — Адамара от (−1)^f, и модуль считает её второй раз прямо по таблице истинности, чтобы держать оба пути вместе.
Уравнения модуля
Уравнения три шага: H на каждом кубите; один вызов оракула как знак, |x> -> (−1)^f(x) |x>; снова H на каждом кубите амплитуда исхода y: (1/N) сумма по x от (−1)^(f(x) + x·y) - преобразование Уолша–Адамара от (−1)^f P(все нули) = (1 − 2k/N)² где k - число единиц в таблице истинности; ТОЧНО, для любой таблицы вообще константа (k = 0 или N): 1; сбалансированная (k = N/2): 0; одна клетка сбалансированной таблицы перевёрнута: 4/N² = 1/64 при N = 16 классическая стоимость, чтобы быть УВЕРЕННЫМ: N/2 + 1 вызовов (3, 5, 9, 17, 33 при n = 2…6) против 1 линейная таблица f(x) = s·x mod 2 (Бернстайн–Вазирани): исход И ЕСТЬ s, вероятность 1, любой другой исход ровно 0; классическая стоимость n вызовов, по одному на бит f = 1 везде даёт в точности те же вероятности, что и f = 0 везде - разница в глобальном знаке, а глобальный знак не измеряется подсчитано, 2000 запусков при n = 4: константа 2000 из 2000 на всех нулях; скрытое s = 11, 2000 из 2000 на 11; сбалансированная 0 на всех нулях; одна клетка перевёрнута 30 (точно 31.25)
