8. Алгоритмы Гровера и Шора: ускоренный поиск и угроза основам асимметричного шифрования

В этой главе мы завершим свои изыскания рассмотрением двух алгоритмов, которые вызвали волнение по поводу возможностей практических квантовых вычислений.

• Алгоритм поиска Гровера. Это неструктурированный алгоритм квантового поиска, созданный Ловом Гровером. Он способен с высокой вероятностью определять входные данные с помощью функции — черного ящика или оракула. Алгоритм позволяет найти элемент за шагов, тогда как среднее значение для классического аналога — N / 2 шагов.

• Алгоритм факторизации целых чисел Шора. Печально известная квантовая факторизация, которая, по словам экспертов, сможет поставить на колени современное асимметричное шифрование. По алгоритму Шора целые числа можно факторизовать приблизительно за log(n3) шагов, в отличие от наиболее быстрого классического алгоритма — метода решета числового поля, которому требуется шагов.

Давайте начнем.

Квантовый неструктурированный поиск

Алгоритм Гровера — это неструктурированная процедура квантового поиска, предназначенная для нахождения строки из n бит в числовом «стоге сена» из N элементов. Как показано на рис. 8.1, квантовый алгоритм Гровера дает значительное ускорение шагов. Может показаться, что это не так уж и много в сравнении с классическим решением, но, когда речь идет о миллионах строк, квадратный корень из 106 намного меньше, чем 106.

 

Рис. 8.1. Временная сложность неструктурированного поиска

Если x — элемент, который мы ищем, то алгоритм Гровера можно описать с помощью следующего псевдокода.

1. Подготовка входных данных при заданной функции (оракула) f: {0, 1… N – 1} → {0, 1}. Обратите внимание, что размер ввода равен 2n, где n — это количество битов, а N — количество шагов, или размер «стога сена». Конечная цель состоит в том, чтобы найти x, при котором f(x) = 1.

2. Приведение всех входных кубитов в состояние суперпозиции.

3. Выполнение инверсии фаз на входных кубитах.

4. Выполнение инверсии относительно среднего значения на входе.

5. Повторение шагов 3 и 4 минимум раз. Существует большая вероятность того, что x будет найден на этой стадии.

Давайте внимательнее рассмотрим критические шаги фазовой инверсии и инверсии относительно среднего значения.

Фазовая инверсия

Это первый шаг в алгоритме, и он должен выполняться в суперпозиции всех состояний в «стоге сена». Если искомый элемент равен x′, где f (x′) = 1, то суперпозицию можно выразить как . В конечном счете фазовая инверсия выполняет следующее:

 

То есть если данный x не является искомым элементом (x ≠ x′), то он оставляет суперпозицию без изменений. В противном случае он инвертирует фазу (знак «минус» перед комплексным коэффициентом αх'|x′〉 кубита, см. графическое представление на рис. 8.2).

 

Рис. 8.2. Графическое представление фазовой инверсии

Это первый шаг в алгоритме Гровера: мы увидим, как инверсия фазы помогает найти искомый элемент, но сейчас рассмотрим второй шаг — инверсию относительно среднего значения.

Инверсия относительно среднего значения

С учетом приведенной ранее суперпозиции определяем среднее значение μ как среднее значение амплитуд:

.

Теперь мы должны зеркально отобразить амплитуды относительно этого среднего значения, то есть:

 

.

Чтобы можно было лучше понять это, на рис. 8.3 приведено графическое представление инверсии относительно среднего значения.

 

Рис. 8.3. Графическое представление инверсии относительно среднего значения

Здесь показано полученное методом суперпозиции состояние кубитов, которое определяется как волновая функция ψ. Среднее значение μ этой функции на графике представлено горизонтальной линией. Инверсия относительно среднего значения выполняет зеркальное отражение волны (показана пунктирной линией). Это эквивалентно повороту волны относительно оси μ. Давайте разберемся во всем этом, объединив все шаги, чтобы увидеть их в действии.

На рис. 8.4 показано следующее.

Суперпозиция всех кубитов переводит все амплитуды в .

Затем фазовая инверсия переводит амплитуду для x' в . Обратите внимание, что здесь есть эффект небольшого снижения среднего значения μ (см. рис. 8.4, шаг 2).

 

Рис. 8.4. Одна итерация алгоритма Гровера

После инверсии относительно среднего значения средняя амплитуда немного уменьшится, но x' так же, как и , поднимется выше среднего значения μ.

Если повторить эту последовательность шагов, то амплитуда x' будет увеличиваться примерно на , пока после приблизительно шагов не станет равной .

• В этот момент, если мы измерим наши кубиты, вероятность нахождения x' (искомого элемента) согласно принципам квантовой механики равна квадрату амплитуды, что составляет 1/2.

• Таким образом, все готово. Примерно за шагов мы нашли отмеченный элемент x'.

Теперь соберем все это в квантовой схеме с соответствующей реализацией в коде.

Практическая реализация

Рассмотрим схему для алгоритма Гровера в IBM Q Experience. Она демонстрирует одну итерацию алгоритма при помощи двух кубитов (рис. 8.5).

 

Рис. 8.5. Квантовая схема для алгоритма Гровера с двумя кубитами и A = 01

Скрипт Python для создания схемы, изображенной на рис. 8.5, дан в листинге 8.1.

Листинг 8.1. Скрипт Python для схемы, приведенной на рис. 8.5

import sys,time,math

# Импорт QISKit

from qiskit import QuantumCircuit, QuantumProgram

 

# Конфигурация Q Experience

sys.path.append('../Config/')

import Qconfig

 

# Импорт базовых средств отображения графики

from qiskit.tools.visualization import plot_histogram

 

# Установка значений входных битов, которые будут использоваться для поиска

def input_phase (circuit, qubits):

    # Раскомментировать при A = 00

    # Закомментировать при A = 11

    circuit.s(qubits[0])

    #circuit.s(qubits[1])

    return

 

# circuit  — двухкубитная схема для алгоритма Гровера

# qubits  — массив кубитов (размером 2)

def invert_over_the_mean (circuit, qubits):

    for i in range (2):

        circuit.h(qubits[i])

        circuit.x(qubits[i])

 

    circuit.h(qubits[1])

    circuit.cx(qubits[0], qubits[1])

    circuit.h(qubits[1])

 

    for i in range (2):

        circuit.x(qubits[i])

        circuit.h(qubits[i])

 

def invert_phase (circuit, qubits):

    # Оракул

    circuit.h(qubits[1])

    circuit.cx(qubits[0], qubits[1])

    circuit.h(qubits[1])

 

def main():

    # Настройка квантовой программы

    qp = QuantumProgram()

 

    qp.set_api(Qconfig.APItoken, Qconfig.config["url"])

 

    # Создание кубитов/регистров

    size = 2

    q = qp.create_quantum_register('q', size)

    c = qp.create_classical_register('c', size)

 

    # Квантовая схема

    grover = qp.create_circuit('grover', [q], [c])

 

    # 1. Перевод всех кубитов в суперпозицию

    for i in range (size):

        grover.h(q[i])

 

    # Настройка входных данных

    input_phase(grover, q)

 

    # 2. Фазовая инверсия

    invert_phase(grover, q)

 

    input_phase(grover, q)

 

    # 3. Инверсия относительно среднего значения

    invert_over_the_mean (grover, q)

 

    # Измерение

    for i in range (size):

        grover.measure(q[i], c[i])

 

    circuits = ['grover']

 

    # Выполнение квантовой схемы на моделирующем устройстве

    backend = "local_qasm_simulator"

    # Количество запусков эксперимента

    shots = 1024

 

    result = qp.execute(circuits, backend=backend, shots=shots

        , max_credits=3, timeout=240)

    counts = result.get_counts("grover")

    print("Counts:" + str(counts))

 

    # Необязательно

    #plot_histogram(counts)

 

###########################################

# main

if __name__ == '__main__':

    start_time = time.time()

    main()

    print("--- %s seconds ---" % (time.time()   — start_time))

В листинге 8.1 выполняется одна итерация алгоритма Гровера с двумя битами на входе и использованием двух кубитов. И хотя в предыдущем разделе утверждается, что общее количество итераций задается приблизительно шагами, для инверсии относительно среднего значения необходимо это число умножить на π/4 и округлить в меньшую сторону (floor) (см. доказательство на рис. 8.8). Следовательно, мы получаем , где N = 2bits. Тогда для двух бит .

• Скрипт начинается с создания квантовой схемы с двумя кубитами и двумя классическими регистрами для хранения результатов измерения на них.

• Затем все кубиты переводятся в суперпозицию при помощи вентиля Адамара.

• Прежде чем выполнить итерацию, подготавливаются входные данные с использованием фазового вентиля (S) и правил из табл. 8.1.

Таблица 8.1. Правила подготовки входных данных для листинга 8.1

Входные данные (А)	Вентили/кубиты
00	S(01)
10	S(0)
01	S(1)
11	Ничего

• Затем выполняется инверсия фаз, а следом за ней — инверсия относительно среднего значения входных кубитов в соответствии с одной итерацией алгоритма.

• Наконец, измеряются результаты и схема выполняется на локальном или удаленном моделирующем устройстве. Выводятся полученные численные значения.

Обобщенная схема

В целом схему, представленную на рис. 8.5, можно обобщить для любого количества входных кубитов (рис. 8.6).

 

Рис. 8.6. Обобщенная форма алгоритма Гровера для произвольного числа кубитов

• Первый блок на рис. 8.6 переводит все кубиты в суперпозицию применением вентиля Адамара к входным данным размера n. Это шаг инициализации.

Затем в схему фазовой инверсии (Uf) подаются входные данные в суперпозиции и входные значения фаз (знак «минус»). Это позволяет установить желаемую фазу именно там, где нужно. Таким образом, получены выходные данные . Но как можно достичь такого результата? Ответ: желаемый эффект был получен с помощью исключающего ИЛИ к входному состоянию со знаком «минус» (рис. 8.7). В третьей строке таблицы истинности для исключающего ИЛИ между f(x) и b (в правой части рис. 8.7) показан эффект применения фазовой инверсии.

 

Рис. 8.7. Схема для фазовой инверсии

Наконец, как показано на рис. 8.3, инверсия относительно среднего значения — то же самое, что и отражение относительно . Для лучшего понимания полученное методом суперпозиции состояние ψ и среднее значение μ могут быть представлены в виде векторов в двумерном пространстве (см. рис. 8.8). Чтобы отразить ψ, создайте вектор, ортогональный к μ, а затем — проекцию ψ в новый квадрант под тем же углом θ.

 

Рис. 8.8. Схема для инверсии относительно среднего значения

Доказательство того, что инверсия относительно среднего значения выполняет преобразование , состоит из трех этапов, которые приведены на схеме на рис. 8.8.

1. Преобразование в вектор, состоящий из нулей, . Это достигается применением вентиля Адамара к входным данным.

2. Отражение относительно вектора из нулей . Это можно сделать, умножив его на разреженную матрицу .

3. Обратное преобразование в еще одним применением вентиля Адамара. Тогда:

 

(8.1)

Обратите внимание, что и . Наконец, применение матрицы (8.1) к состоянию дает

 

 

Таким образом, получен алгоритм Гровера для неструктурированного поиска. Он быстрый, мощный и скоро будет вовсю использоваться в центрах обработки данных для ускорения любых видов поиска в базах данных. Поскольку он значительно производительнее классического собрата, существует вероятность того, что через несколько лет, когда квантовые компьютеры станут более доступными для коммерческого применения, бо'льшая часть поисков в Интернете будет выполняться при помощи этой квантовой рабочей лошадки. Прежде чем мы закончим, стоит отметить, что на момент написания книги какой-либо полезной реализации или эксперимента, который может найти что-то реальное, для IBM Q Experience не существует. Надеюсь, это изменится в будущем, но пока алгоритм Гровера хорошо работает в теории. В следующем разделе мы эффектно завершим книгу рассмотрением знаменитого алгоритма Шора для факторизации целых чисел.

Факторизация целых чисел при помощи алгоритма Шора

Игра в кошки-мышки между криптографией и криптоанализом продолжается: первая разрабатывает новые способы шифрования наших ежедневно создаваемых данных, а второй ищет слабые места, чтобы их взломать. Современное асимметричное шифрование опирается на хорошо известную сложность факторизации очень больших простых чисел (в диапазоне сотен цифр). В этом разделе рассматривается внутренняя работа алгоритма Шора — метода, который дает экспоненциальное ускорение для факторизации целых чисел при помощи квантового компьютера. Затем поговорим о реализации с использованием библиотеки под названием ProjectQ. Далее мы смоделируем целочисленные выборки и оценим результаты. Наконец, рассмотрим текущие и перспективные направления факторизации целых чисел в квантовых системах.

Квантовая факторизация бросает вызов асимметричному шифрованию

В основополагающей статье Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer Питер Шор предложил метод квантовой факторизации, использующий принцип, давно известный математикам: найти период (также известный как порядок) элемента a в мультипликативной группе по модулю N, то есть такое наименьшее положительное целое число, что:

,

где N — число, раскладываемое на множители; r — период a по модулю N.

Примечание

Факторизация больших целых чисел — это задача, которая занимала умы математиков на протяжении тысячелетий. В 1976 году Г.Л. Миллер предположил, что с помощью случайных чисел факторизацию можно свести к нахождению периода элемента по модулю N, что значительно упрощает данную задачу. Это основная идея алгоритма Шора.

Ученый разделил свой алгоритм на три этапа, два из которых выполняются на классическом компьютере за полиномиальное время.

1. Подготовка входных данных. Выполняется на классическом компьютере за полиномиальное время log(N).

2. Нахождение периода r элемента a, при котором , посредством квантовой схемы. Согласно Шору, для этого потребуется O((log N)2(log log N)(log log log N)) шагов на квантовом компьютере.

3. Обработка выходных данных. Выполняется на классическом компьютере за полиномиальное время log(N).

Почему этот метод вызывает такую обеспокоенность? Сравните его временную сложность (О) с этим же параметром действующего классического чемпиона — метода решета числового поля. Данные приведены в табл. 8.2 (включает еще одного лидера — популярный алгоритм квадратичного решета).

Таблица 8.2. Временная сложность популярных алгоритмов факторизации

Алгоритм	Временная сложность
Шора
Решета числового поля
Квадратичного решета

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

Примечание

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

Но пока рано паниковать: до практической реализации на реальном квантовом компьютере еще далеко. Тем не менее данный алгоритм можно смоделировать в классической системе с помощью ProjectQ — прекрасной библиотеки Python. Мы познакомимся с ее реализацией позже, а в следующем разделе посмотрим, как можно эффективно решить задачу факторизации, определив период.

Нахождение периода

Нахождение периода является базовым блоком алгоритма Шора. При помощи модульной арифметики данная задача может быть сведена к поиску периода (r) функции f(x) = ax mod N (рис. 8.9).

На рис. 8.9 приведен пример периодической функции f(x) с периодом r = 4. Чтобы алгоритм был осуществим, f(x) должна отвечать трем условиям.

1. f(x) однозначная для каждого периода, то есть значения f(x) не должны повторяться. На рис. 8.9 данные значения представлены вершинами всех линий за период.

 

Рис. 8.9. Периодическая функция f(x)

2. Для любого количества периодов M период r должен быть делителем. Например, при M = 100 и периоде r = 4 отношение M / r = 25.

3. Результат деления M на r должен быть больше, чем r, то есть M > r2.

Алгоритм Шора преобразует f(x) в квантовую схему Uf, где входные кубиты находятся в суперпозиции. Измерив второй регистр в Uf, мы можем увидеть значения амплитуд , показанные на графике амплитуд на рис. 8.9. Здесь амплитуды отстоят друг от друга на четыре деления, что является искомым периодом. В данном частном случае мы получаем периодические суперпозиции с r = 4. Но что нам делать с ними? Алгоритм Шора использует еще один прием — квантовое преобразование Фурье.

Преобразование Фурье

Преобразование Фурье — это процесс изменения данных, который допускает сдвиги во входных данных без изменения распределения выходных данных.

Это хорошо, потому что теперь у нас есть периодическая суперпозиция, где ненулевые амплитуды кратны периоду (рис. 8.10).

 

Рис. 8.10. Преобразование Фурье, показывающее периодическую суперпозицию

Но каким будет выходное значение преобразования Фурье? И чем оно нам поможет? Ответ: его выходным значением является случайное число, кратное M / r. В данном случае при M = 100 и r = 4 получаем случайное число, кратное 100 / 4 = 25, что соответствует нашей цели. Посмотрим, как это происходит.

Передача результатов преобразования Фурье в алгоритм Евклида для нахождения наибольшего общего делителя

После многократного выполнения преобразования Фурье мы получим множество случайных M / r. Например, можем получить 50, 75, 25 и т.д. Теперь, если мы применим к случайным выходным результатам алгоритм Евклида для нахождения наибольшего общего делителя (НОД), то, разделив M на НОД, найдем период r. Таким образом:

r = M / НОД(50, 75…) = 100 / 25 = 4.

Это краткое описание алгоритма нахождения периода с использованием квантовой схемы. Чтобы понять, каким образом с помощью данного метода можно эффективно найти множитель, приведу пример факторизации числа N = 21. Решение задачи основано на двух весьма эффективных операциях:

• модульной арифметике: a = b(mod N). Например, 3 = 15(mod 12);

• НОД(a, b). Например, НОД(15, 21) = 3.

Тогда при N = 21 нужно решить уравнение x2≡ 1(mod 21). А именно найти такой нетривиальный квадратный корень x, что:

• N является делителем (x + 1)(x – 1);

• N не является делителем (x ± 1).

Наконец, восстановить простой множитель, применив НОД(N, x + 1).

Чтобы найти нетривиальный множитель для N = 21, выберем случайным образом x. Например, при N = 21 выбираем x = 2, тогда:

20≡ 1 (mod 21)

21≡ 2 (mod 21)

22≡ 4 (mod 21)

23≡ 8 (mod 21)

24≡ 16 (mod 21)

25≡ 11 (mod 21)

26≡ 1 (mod 21). Получен период r = 6.

В данном случае 26 = (23)2. Значит, 23 = 8 — нетривиальный множитель, при котором 21 является делителем (8 + 1)(8 – 1). Наконец, мы восстанавливаем значение множителя с помощью НОД(N, x + 1) = НОД(21, 9) = 3. Вообще говоря, нужно выбрать x случайным образом и затем пройти в цикле по x0, x1… xr≡ mod N. Если нам повезло и r четный, то (xr/2)2≡ 1(mod N). И тогда существует нетривиальный квадратный корень 1 mod N.

Примечание

Было доказано, что вероятность того, что нам повезет и r окажется четным, а x2≡ 1 (mod N), равна 1/2. Однако, учитывая высокую вероятность успеха, это незначительно в общем масштабе.

Теперь запустим алгоритм, воспользовавшись прекрасной библиотекой Python под названием ProjectQ.

Алгоритм Шора с использованием ProjectQ

ProjectQ — это платформа с открытым исходным кодом для квантовых вычислений, которая реализует алгоритм Шора при помощи схемы, предложенной Стефаном Борегаром. В ней применяются 2n + 3 кубитов, где n — количество битов факторизуемого числа N. Метод Борегара подразделяется на следующие шаги.

1. Если N четное, возвращается множитель 2.

2. Классическим способом определяется, выполняется ли N = pq при p ≥ 1 и q ≥ 2, и если да, то возвращается множитель p (на классическом компьютере это можно выполнить за полиномиальное время).

3. Выбирается такое случайное число a, что 1 < a ≤ N – 1. При помощи алгоритма Евклида для нахождения наибольшего общего делителя определяем, верно ли, что НОД(a, N) > 1. Если да, то возвращается множитель НОД(a, N).

4. Для нахождения порядка r для a по модулю N используется квантовая схема. На квантовом компьютере данный шаг выполняется за полиномиальное время.

5. Если r нечетное или r четное, но ar/2 = –1(mod N), то происходит переход к шагу 3. В противном случае вычисляется НОД(ar / 2 – 1, N) или НОД(ar / 2 + 1, N). Выполняется проверка, является ли одно из этих значений нетривиальным множителем N, и если да, то возвращается данный множитель (на классическом компьютере это может быть выполнено за полиномиальное время).

Борегар находит период, выполнив несколько управляемых суммирований и умножений в пространстве Фурье, чтобы найти решение f(x) = = ax(mod N) →ar≡ 1 mod N (рис. 8.11).

• Управляемый умножитель Ua производит отображение , где:

• a — это классическое взаимно простое с модулем число, которое используется как основание для ax(mod N);

• x — квантовый регистр;

• c — регистр таких управляющих кубитов, что Ua = ax(mod N), если c = 1, и x в ином случае.

 

Рис. 8.11. Квантовая схема Борегара для нахождения периода

• Управляемый умножитель Ua, в свою очередь, реализован как ряд модульных сумматоров с двойным управлением, при которых:

• если оба управляющих кубита c1 = c2 = 1, то на выходе . То есть это a + b(mod N) в пространстве Фурье. Обратите внимание, что этот вентиль складывает два числа: взаимно простое с модулем a и квантовое b;

• если оба управляющих кубита, c1 и c2, находятся в состоянии , то .

• Модульный сумматор с двойным управлением построен на основе квантовой суммирующей схемы по Драперу. В данной схеме реализовано сложение классического значения (a) с квантовым значением (b) в пространстве Фурье.

Факторизация с помощью ProjectQ

Установим ProjectQ и протестируем алгоритм. В первую очередь воспользуемся менеджером пакетов Python для загрузки и установки ProjectQ (для простоты я использую Windows; пользователи Linux должны следовать той же процедуре):

C:\> pip install projectq

Затем возьмите скрипт shor.py из папки с примерами для ProjectQ или исходников книги (Workspace\Ch08\p08.shor.py). Запустите его и введите факторизуемое число (листинг 8.2).

Листинг 8.2. Алгоритм Шора с ProjectQ в действии

C:\>python shor.py

Number to factor: 21

 

Factoring N = 21: ..........

 

Factors found : 7 * 3 = 21

Gate class counts:

    AllocateQubitGate : 166

    CCR : 1467

    CR : 7180

    CSwapGate : 50

    CXGate : 200

    DeallocateQubitGate : 166

    HGate : 2600

    MeasureGate : 11

    R : 608

    XGate : 206

 

Gate counts:

    Allocate : 166

    CCR(0.098174770425) : 18

    CCR(0.196349540849) : 30

    CCR(0.392699081699) : 70

    CCR(0.490873852124) : 18

    CCR(0.785398163397) : 80

    CCR(0.981747704246) : 38

    CCR(1.079922474671) : 20

    CCR(1.178097245096) : 16

    ...

    R(5.252350217719) : 1

    R(5.301437602932) : 1

    R(5.497787143782) : 1

    X : 206

 

Max. width (number of qubits) : 13.

--- 5.834410190582275 seconds ---

При N = 21 скрипт выдает набор весьма полезных статистических данных, таких как:

• количество задействованных кубитов. При N = 21 нужно пять кубитов, тогда общее количество кубитов 2 · 5 + 3 = 13;

• общее количество использованных вентилей по типам. В данном случае с двойным управлением CCR = 1467, CR = 7180, CSwap = 50, CX = 200, R = 608, X = 206 и т.д. до общего количества 12 646 квантовых вентилей.

В ProjectQ квантовая схема для нахождения периода с помощью алгоритма Борегара приведена в листинге 8.3.

• Функция run_shor принимает три аргумента:

• квантовый движок или моделирующее устройство, предоставляемое ProjectQ;

• N — факторизуемое число;

• a — взаимно простое с модулем число, которое используется в качестве основания для ax mod N.

• Затем функция проходит в цикле от a = 0 до a = ln (N) с входным квантовым регистром x в суперпозиции и выполняется квантовая схема для f(a) = ax mod N (рис. 8.11).

• Далее выполняется преобразование Фурье на регистре x, зависящем от предыдущих выходных значений, и производятся измерения.

• Наконец, измеренные значения суммируются, суммой является число в пределах [0, 1]. Затем выполняется разложение в цепную дробь, чтобы вернуть делитель или возможное значение периода (r).

Листинг 8.3. Квантовая подпрограмма для нахождения периода в ProjectQ

def run_shor(eng, N, a):

    n = int(math.ceil(math.log(N, 2)))

 

    x = eng.allocate_qureg(n)

 

    X | x[0]

 

    measurements = [0] * (2 * n) # будет хранить 2n результатов измерений

 

    ctrl_qubit = eng.allocate_qubit()

 

    for k in range(2 * n):

        current_a = pow(a, 1 << (2 * n   — 1   — k), N)

 

            # Одна итерация QPE с одним кубитом

        H | ctrl_qubit

 

        with Control(eng, ctrl_qubit):

            MultiplyByConstantModN(current_a, N) | x

 

        # Выполнить инверсию QFT --> повороты в зависимости

        # от предыдущих выходных значений

        for i in range(k):

            if measurements[i]:

                R(-math.pi/(1 << (k – i))) | ctrl_qubit

 

        H | ctrl_qubit

        # и измерить

        Measure | ctrl_qubit

        eng.flush()

        measurements[k] = int(ctrl_qubit)

        if measurements[k]:

            X | ctrl_qubit

 

    Measure | x

    # Перевод измеренных значений в числа, лежащие в пределах [0, 1)

    y = sum([(measurements[2 * n   — 1   — i]*1. / (1 << (i + 1)))

        for i in range(2 * n)])

 

    # Разложение на множители для получения делителя (или периода?)

    r = Fraction(y).limit_denominator(N-1).denominator

 

    # Возврат (возможного) значения периода

    return r

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

Результаты моделирования

Квантовая подпрограмма для нахождения периода в ProjectQ создается моделированием квантовой схемы на классическом компьютере, из-за чего ее применение для факторизации больших чисел нецелесообразно. Фактически она не способна разложить число, состоящее более чем из четырех цифр, на домашнем компьютере за приемлемое время. В табл. 8.3 приведен набор результатов для различных значений N — от 15 до 2491, полученных на моем ноутбуке.

Таблица 8.3. Результаты факторизации различных значений N

Число N	Кубиты	Время, с	Память, Мбайт	Количество квантовых вентилей
15	11	2,44	50	CCR = 792; CR = 3186; CSwap = 32; CX = 128; H = 1408; R = 320; X = 130; Measure = 9
105	17	27,74	200	CCR = 3735; CR = 25 062; CSwap = 98; CX = 392; H = 6666; R = 1568; X = 393; Measure = 15
1150	25	17 542,12 (4,8 ч)	500	CCR = 15 366; CR = 139 382; CSwap = 242; CX = 968; H = 24 222; R = 5829; X = 981; Measure = 23
2491	27	246 164,74 (68,3 ч)	2048	CCR = 20 601; CR = 194 670; CSwap = 288; CX = 1152; H = 31 126; R = 7509; X = 1166; Measure = 25

На факторизацию четырехзначного числа 2491 ушло более 68 часов на 64-разрядном ПК с Windows 7, с процессором Intel Core i-5, с тактовой частотой 2,6 ГГц и с 16 Гбайт оперативной памяти. Я попытался разложить немного большее N = 8122, но через неделю сдался. В целом эти результаты показывают, что алгоритм можно успешно смоделировать для небольших N, однако его необходимо реализовать на реальном квантовом компьютере, чтобы проверить его действительную мощь.

В этой главе мы завершили свои исследования двумя алгоритмами, которые вызвали волнения по поводу возможностей практических квантовых вычислений. Это алгоритм Гровера — неструктурированный метод квантового поиска, способный находить входные данные в среднем за √N шагов, что намного быстрее, чем лучшее классическое решение со средним значением N / 2 шагов. Предполагаю, что в будущем все поиски в Интернете будут выполняться при помощи алгоритма Гровера.

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

Наконец, я хотел бы подвести итог, сказав, что изо всех сил пытался объяснить сложные концепции квантовых вычислений, смешивая математику, программное обеспечение и столько числовых данных, сколько смог собрать. Множество чашек кофе было выпито, много бессонных ночей было потрачено на написание этой книги. Я надеюсь, что вам понравилось читать эту книгу так же, как мне — писать ее. И помните слова великого физика Ричарда Фейнмана: «Если кто-то говорит вам, что он понимает квантовую механику, это значит, что он не понимает квантовую механику».