Алгоритм Дойча: вопрос о функции за одно обращение

Если ты проведёшь алгоритм Дойча по шагам для всех четырёх функций одного бита, объяснишь, почему он узнаёт свойство функции, не узнавая её значений, и назовёшь, в каком смысле его выигрыш настоящий, а в каком нет, - листай до «Теперь сам».

Как думаешь, можно ли сравнить два значения за один вопрос

Функция f принимает один бит и возвращает один бит. Она спрятана в чёрном ящике: можно подать вход и получить выход. Нужно узнать одно: f(0) = f(1) или нет.

Ответь себе до чтения: сколько раз придётся обратиться к ящику? Обычной программе - два: узнав только f(0), про f(1) не знаешь ничего. Кажется, что иначе и быть не может. Но квантовому алгоритму хватает одного обращения. Он не узнаёт ни f(0), ни f(1) - и всё же узнаёт, равны ли они. Вопрос задан сразу про оба входа, а ответ извлечён такой, какой из одного измерения извлечь можно: один бит.

На что это похоже

Весы без гирь. Нужно узнать, одинаково ли весят два предмета. Взвешивать каждый отдельно - два измерения, и получишь больше, чем просили: оба веса. Положить предметы на две чашки - одно измерение, и оно отвечает ровно на заданный вопрос, не сообщая ни одного веса.

Алгоритм Дойча кладёт f(0) и f(1) на две чашки. Чашки - это две амплитуды, значения функции - знаки при них, а стрелка весов - интерференция: она показывает, одинаковы знаки или нет.

Механизм: знак вместо значения

Функций от одного бита четыре:

f(0) f(1)
 0    0        постоянная
 1    1        постоянная
 0    1        принимает оба значения
 1    0        принимает оба значения

Оракул. Квантовое обращение к функции устроим так: оно меняет знак амплитуды у тех входов x, где f(x) = 1, и не трогает остальные. В настоящей схеме это получается из обычного обращения к f за один раз. Берут вспомогательный кубит в состоянии (1/√2, −1/√2) и вычисляют f(x) так, чтобы её значение переворачивало этот кубит; переворот такого состояния - то же самое, что умножение на −1. Множитель относится ко всей строке «вход x и вспомогательный кубит», поэтому его можно считать знаком при амплитуде входа x; вспомогательный кубит остаётся прежним. Схемой называют последовательность вентилей.

Алгоритм.

1. кубит в состоянии «ноль»:   (1, 0)
2. вентиль Адамара:            (1/√2, 1/√2)     вопрос задан обоим
                                                входам сразу
3. оракул, одно обращение:     (±1/√2, ±1/√2)   знаки - по значениям f
4. вентиль Адамара
5. измерить

Знаки в третьей строке независимы: минус у первой амплитуды при f(0) = 1, у второй - при f(1) = 1. После третьего шага возможны два случая.

f(0) = f(1):  знаки одинаковы:  ±(1/√2,  1/√2)  →  Адамар  →  ±(1, 0)
                                →  измерение даёт 0
f(0) ≠ f(1):  знаки разные:     ±(1/√2, −1/√2)  →  Адамар  →  ±(0, 1)
                                →  измерение даёт 1

Общий знак всего состояния на вероятности не влияет. Важен относительный знак двух амплитуд, а его вентиль Адамара превращает в различие между «нулём» и «единицей» - это его работа из прошлого урока, выполненная в обратную сторону.

Ответ получается с вероятностью единица, за одно обращение. При этом, получив 0, мы знаем, что функция постоянна, но не знаем, равна она нулю или единице: эти сведения ушли в общий знак, который не измеряется. Одно измерение одного кубита даёт один бит, и он потрачен на то, о чём спрашивали.

Вариант для n бит, алгоритм Дойча-Йожи. Про функцию от n бит заранее гарантировано, что она либо постоянна, либо принимает значение 1 ровно на половине входов; других функций не дадут. Схема та же: вентиль Адамара на каждый кубит, одно обращение к оракулу, снова вентили Адамара, измерение. Если функция постоянна, все 2ⁿ амплитуд после оракула имеют один знак и собираются обратно в строку из нулей. После второго слоя вентилей амплитуда нулевой строки равна сумме всех 2ⁿ амплитуд, делённой на √(2ⁿ). Если значения поделены поровну, плюсов и минусов в этой сумме одинаково, вклады в точности гасятся, и нулевая строка не выпадет никогда.

Правило

Алгоритм Дойча: вентиль Адамара, одно обращение к оракулу, меняющему знак амплитуды при f(x) = 1, снова вентиль Адамара, измерение. Результат 0 означает f(0) = f(1), результат 1 - f(0) ≠ f(1). Узнаётся свойство функции в целом, а не её значения. Вариант для n бит одним обращением отличает постоянную функцию от принимающей оба значения поровну.

Разбор: четыре функции, один запрос на каждую

Функция orakul меняет знак амплитуды там, где f равна единице. Моделирование при этом читает оба значения f: оно хранит обе амплитуды по отдельности. Квантовое устройство выполняет оракул один раз - над суперпозицией. В выводе - функция, заданная парой значений, и вероятности исходов 0 и 1 после всего алгоритма.

import math

def adamar(s):
    k = 1 / math.sqrt(2)
    return [k * (s[0] + s[1]), k * (s[0] - s[1])]

def orakul(s, f):
    itog = []
    for x in range(2):
        if f[x] == 1:
            itog.append(-s[x])
        else:
            itog.append(s[x])
    return itog

for f in [[0, 0], [1, 1], [0, 1], [1, 0]]:
    s = adamar(orakul(adamar([1.0, 0.0]), f))
    print(f, [round(s[0] * s[0], 4), round(s[1] * s[1], 4)])

[0, 0] [1.0, 0.0]
[1, 1] [1.0, 0.0]
[0, 1] [0.0, 1.0]
[1, 0] [0.0, 1.0]

Для обеих постоянных функций измерение даёт 0 с вероятностью единица, для обеих непостоянных - 1. Никакой случайности в ответе нет, хотя посередине вычисления кубит был в равной суперпозиции.

Функции [0, 0] и [1, 1] дают одинаковый результат, и различить их алгоритм не может: у первой оракул не трогает ничего, у второй меняет знак обеих амплитуд сразу. То же с парой [0, 1] и [1, 0]. Четыре функции делятся на два класса, и алгоритм определяет класс - ровно один бит сведений за одно обращение.

Противоречия со здравым смыслом нет: измерение одного кубита даёт один бит. Нарушено только привычное представление, что этот бит обязан быть значением функции в одной точке.

Разбор: восемь входов и обещание

Три кубита, восемь входов. Функция задана списком значений. adamar_vse применяет вентиль Адамара к каждому кубиту по очереди (в программе n - число амплитуд, восемь, а shag - бит очередного кубита: пара i и i + shag различается только им); odin_zapros выполняет весь алгоритм и возвращает вероятность получить при измерении строку 000.

import math

def adamar_vse(s):
    n = len(s)
    shag = 1
    while shag < n:
        novoe = list(s)
        for i in range(n):
            if i & shag == 0:
                a = s[i]
                b = s[i + shag]
                novoe[i] = (a + b) / math.sqrt(2)
                novoe[i + shag] = (a - b) / math.sqrt(2)
        s = novoe
        shag = shag * 2
    return s

def odin_zapros(f):
    n = len(f)
    s = [0.0] * n
    s[0] = 1.0
    s = adamar_vse(s)
    for x in range(n):
        if f[x] == 1:
            s[x] = -s[x]
    s = adamar_vse(s)
    return round(s[0] * s[0], 4)

postoyannaya = [0, 0, 0, 0, 0, 0, 0, 0]
edinicy = [1, 1, 1, 1, 1, 1, 1, 1]
polovina = [0, 1, 1, 0, 1, 0, 0, 1]
drugaya = [0, 0, 0, 0, 1, 1, 1, 1]
perekos = [0, 0, 0, 1, 0, 0, 0, 0]
for f in [postoyannaya, edinicy, polovina, drugaya, perekos]:
    print(f, odin_zapros(f))

[0, 0, 0, 0, 0, 0, 0, 0] 1.0
[1, 1, 1, 1, 1, 1, 1, 1] 1.0
[0, 1, 1, 0, 1, 0, 0, 1] 0.0
[0, 0, 0, 0, 1, 1, 1, 1] 0.0
[0, 0, 0, 1, 0, 0, 0, 0] 0.5625

Постоянные функции дают строку 000 наверняка. Обе функции с четырьмя единицами из восьми - никогда. Одно обращение, одно измерение: 000 - постоянная, что-то другое - поровну.

Последняя строка - функция, которая не выполняет обещания: единица только в одном месте из восьми. Вероятность 000 получилась 0,5625: семь амплитуд с плюсом и одна с минусом дают (7 − 1) / 8 = 0,75, а квадрат этого числа - 0,5625. Строка, отличная от 000, по-прежнему доказывает, что функция не постоянна; а вот выпавшая 000 теперь ничего не значит. Алгоритм рассчитан на два случая, и за их пределами ответ «постоянная» ненадёжен.

Теперь честное сравнение. Детерминированной программе в худшем случае нужно пять обращений из восьми: четыре одинаковых значения подряд ещё не доказывают постоянства. Для n бит - 2ⁿ⁻¹ + 1 против одного. Выглядит как экспоненциальный выигрыш. Но программа, которая спрашивает значения в случайных точках (каждую выбирает заново, повторы разрешены), после двадцати одинаковых ответов ошибается с вероятностью около двух миллионных: функция «поровну» так совпала бы с шансом 2 в минус девятнадцатой: первый ответ любой, остальные девятнадцать должны с ним совпасть. Против случайных алгоритмов выигрыш Дойча-Йожи - только в том, что ответ точный, а не почти точный.

Задачи, где квантовый алгоритм обгоняет и случайные, появились следом; их схема та же, а вопрос «одинаковы ли знаки» заменён поиском периода. К ним ведёт последний урок главы.

Что ломается без этого

«Алгоритм вычислил функцию в двух точках за один раз». Ни одного значения он не узнал. Он узнал один бит - равны ли значения - и только его.

Алгоритм применяют без обещания. На функции, которая и не постоянна, и не поделена поровну, результат из одних нулей возможен и у непостоянной функции и перестаёт что-либо доказывать; любой другой по-прежнему означает «не постоянна».

Число обращений принимают за время работы. Сравниваются обращения к чёрному ящику. В настоящей задаче функция - программа, и её стоимость входит в счёт.

Сравнивают только с детерминированной программой. Честный соперник квантового алгоритма - лучший классический, включая случайные.

Зачем это в работе

Шаблон алгоритмов этой главы. Равная суперпозиция, обращение к функции, которое прячет сведения в знаки, преобразование, собирающее знаки в измеряемый результат. У Гровера на третьем шаге отражение, у Шора - преобразование, находящее период; первые два шага те же.

Правильный вопрос к квантовому ускорению. Не «быстрее чего», а «быстрее лучшего известного классического алгоритма и при каких допущениях». Заявления о выигрыше различаются именно этим.

Модель с оракулом. Оценки «сколько обращений нужно» - редкий случай, когда нижние границы удаётся доказывать. Корень из N для поиска, о котором следующий урок, доказан именно в ней.

Теперь сам

1. Проведи алгоритм Дойча для функции f(0) = 1, f(1) = 0: выпиши амплитуды после каждого шага.
2. Алгоритм выдал 0. Что известно о функции и что неизвестно?
3. Сколько обращений нужно детерминированной программе, чтобы отличить постоянную функцию от функции «поровну» при четырёх входных битах?
4. Почему при постоянной функции вариант для n бит всегда даёт строку из нулей?
5. В каком смысле выигрыш алгоритма Дойча-Йожи не экспоненциальный?