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 викликів, по одному на біт. Спитай один раз — прочитай усю строку. Під обома фактами одна формула: амплітуда результату 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)
