5.5. Нахождение периода функции

Задача определения периода функции является важным примером применения квантового преобразования Фурье.

Предположим, что имеется периодическая функция с периодом . Это означает, что для всех выполняется тождество:

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

В качестве начального состояния возьмем следующую однородную суперпозицию (квантовая схема для получения такого состояния представлена в задаче 5.3.3):

Проведем измерение второго регистра (регистра функции). Предположим, что при этом мы получим некоторое значение функции . Пусть - одно из значений аргумента, при котором . В результате редукции вектора состояния в суперпозиции «выживут» только слагаемые, отвечающие , где , поскольку только для них . В результате первый регистр (отвечающий аргументу ) перейдет в следующее квантовое состояние:

Выполним теперь квантовое преобразование Фурье над полученным состоянием. Согласно определению, каждое отдельно взятое базисное состояние будет подвергнуто следующему преобразованию:

Суперпозиция, представляющая состояние , в результате квантового преобразования Фурье примет вид:

Задача 5.14 Пусть , где и . Покажите, что , если , где и при всех остальных значениях .

Результаты представленной выше задачи показывают, что выходное состояние регистра может быть записано в виде:

Последний шаг процедуры – это измерение полученного состояния. Мы видим, что с равной вероятностью возможно любое из состояний , где .

Пусть Природа «выбрала» некоторое и в результате измерения возникло состояние . Тогда, имеем следующее тождество для четырех целых чисел:

Здесь и доступные исследователю числа, в то время как и - числа, неизвестные ему. Наша цель- определить . Полученное тождество показывает, что исследователь не может гарантированно определить при однократном выполнении процедуры. Чтобы его поиски оказались продуктивны, ему следует уповать на то, что «выбранное» Природой число и период окажутся взаимно простыми (т.е. не будут иметь общих делителей, кроме единицы). Тогда, приведя дробь к несократимой, он сможет восстановить и . В этом случае нам удастся с помощью одного уравнения (7) найти два неизвестных целых числа. Если же исследователю не повезет и Природа «выберет» такое , что дробь окажется сократимой, то вместо истинного периода он получит меньшее значение.

Приведем пример. Пусть - заранее известное число. - период, неизвестный исследователю. Природа может «выбрать» любое от 0 до 63. Пусть, например, она «выбрала» . Тогда исследователь получит . Сократив дробь до , исследователь правильно определит, что и . Пусть теперь, Природа «выбрала» . Этот выбор неудачен для исследователя, поскольку числа 12 и 64 имеют общий делитель, равный 4. Теперь . Сократив дробь до , исследователь может сделать неправильный вывод, будто бы и . Для того, чтобы с высокой вероятностью получить правильный ответ, исследователь будет вынужден повторять описанную процедуру многократно. Тогда, очевидно, в качестве ответа ему следует взять период, отвечающий наибольшему из возможных значений (максимальный знаменатель в дроби после ее сокращения).

Оценим, сколько раз исследователь должен проделать описанную выше процедуру, чтобы определить неизвестный период с высокой гарантией. Для этого нужно оценить вероятность того, что «выбранное» Природой число окажется взаимно простым с . Известно, что при больших количество простых чисел, не превышающих можно оценить как . Отсюда следует, что вероятность удачи при отдельном испытании больше или порядка . Таким образом, если исследователь повторит процедуру раз, то с высокой гарантией, он сможет найти неизвестный период. Например, если , то потребуется всего порядка 1000 испытаний (в оценках такого рода мы не делаем различия между натуральным и двоичным логарифмами).

Резюмируем полученный результат. Квантовый алгоритм нахождения периода функций требует всего операций (для квантового преобразования Фурье требуется операций и операций требуется для описанной выше процедуры угадывания). Рассматриваемый алгоритм является полиномиальным по числу кубитов и, соответственно, по количеству знаков в числе (поскольку число шагов алгоритма определяется полиномом третьей степени).

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