Квантовые алгоритмы (продолжение)

ЛЕКЦИЯ 20. КВАНТОВЫЕ АЛГОРИТМЫ (продолжение)

20.1. Примеры ЛЭ и соответствующих матриц, используемых для квантовых вычислений.

20.2. Квантовое преобразование Фурье.

20.3. Квантовые алгоритмы:

20.3.1. Алгоритм Саймона или задача “Оракула”;

20.3.2. Алгоритм разложения на простые множители или алгоритм Шора; дискретное логарифмирование.

20.3.3. Алгоритм поиска в базе данных или “алгоритм Гровера”

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

Напоминание. Матрица называется эрмитовой, если

Рекомендуемые материалы

Матрица называется унитарной, если

Также мы требуем локальности преобразований. Это означает, что унитарные преобразования выполняются над фиксированным числом n битов.  Физически это оправдано тем, что мы знаем, как построить ЛЭ, действующие на два бита, а n-битовые преобразования всегда можно выполнить с помощью двухбитовых.

Рассмотрим систему, состоящую из n компонент, каждая из которых имеет два состояния (кубит). В классической физике полное описание состояния такой системы требует только n битов. В квантовой механике, полное описание состояния такой системы требует знания  комплексных чисел, поскольку это состояние описывается суперпозицией всех базисных состояний (в примере, рассмотренном на предыдущей лекции n = 3, есть 8 амплитуд базисных состояний плюс условие нормировки плюс общая фаза, итого 7 комплексных чисел). Точнее говоря, состояние квантовой системы представляется точкой в 2ⁿ - мерном векторном пространстве. Для каждого из 2ⁿ  возможных положений классических компонент существует базисное состояние такого векторного пространства, которое представляется в виде, например, . Такая запись означает, что первый бит равен 0, второй - 1 и т.д. Запись в виде кет-вектора свидетельствует о том, что состояние  S - чистое. Смешанные состояния в этой лекции мы не рассматриваем. Гильбертово пространство, связываемое с такой системой - это комплексное векторное пространство, имеющее эти 2ⁿ векторов в качестве базисных.. Состояние этой системы в любой момент времени описывается вектором единичной длины в этом векторном пространстве. Итак, суперпозицию состояний будем описывать в виде:

                                                                                                     (20.0)

где a_i - комплексные амплитуды, удовлетворяющие условию нормировки  а каждый вектор  - базисный вектор гильбертова пространства.

Если на каком-то вычислительном шаге машина производит измерение (в каком-то из этих базисов), то вероятность обнаружить систему в этом базисе  есть просто . Однако измерение состояния в машине проектирует полное состояние на наблюдаемый базисный вектор (пример с поляризацией фотонов). Следовательно, “подсматривание” за состоянием машины во время вычисления, приведет к разрушению состояния и остановке вычисления.

Действие квантовых логических элементов должны представляться в виде таблиц истинности: каждому входному вектору ставится в соответствие выходной вектор. Например,

                                                                               (20.1)

Не все таблицы истинности отвечают физически реализуемым квантовым ЛЭ, поскольку многие таблицы не представляют собой унитарных преобразований. Преобразование (20.1) можно записать в виде матрицы. В ней строки соответствуют входным базисным векторам, а столбцы – выходным базисным векторам.

Элемент (i, j) матрицы дает значение коэффициента j-ого базисного выходного вектора, когда i-ый базисный вектор является входным для ЛЭ. Таблица истинности для примера, приведенного выше есть:

                                                                     (20.2)

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

.                                                                                                                                            (20.3)

Квантовый ЛЭ является “правильным” только если матрица, которой он представлен, унитарна, т.е. обратная к ней матрица равна эрмитово-сопряженной (транспонирование + комплексное сопряжение).

Рассмотрим следующий пример. Пусть входное состояние представлено суперпозицией:

.                                                                                (20.4)

Подействуем на это состояние матрицей (2):

                                         (20.5)

Этот пример наглядно демонстрирует проявление эффекта интерференции при квантовых вычислениях. Независимо от того, стартовали ли мы с состояния  или , у нас всегда есть шанс получить состояние  на выходе нашего ЛЭ (см. (20.1)). Однако, когда мы стартуем с суперпозиции этих двух состояний (20.4), амплитуда вероятности получить на выходе состояние  обращается в нуль. Аналогичные рассуждения можно провести и для случая другого входного состояния, когда вместо знака “-“ стоит “+”:

         .                                                                      (20.6)

В этом случае, на выходе нашего ЛЭ (20.3) исчезает амплитуда состояния !

По правилам квантовой механики если мы используем двухкубитовый ЛЭ к регистру, состоящему из большого числа битов (кубитов) - в этом случае рассматриваемая цепь должна иметь больше двух проводников- мы должны подействовать матрицей на соответствующие кубиты и оставить остальные кубиты без изменения. Эта процедура отвечает умножению состояния всего регистра на тензорное произведение матрицы ЛЭ и состояния двух выделенных кубитов и единичной матрицы, действующей на оставшиеся кубиты.

Напомним, что квантовый ЛЭ рассматривается как набор логических “проводников”, соединяющих вход и выход.

Квантовое преобразование Фурье.

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

.                         (20.*)

Обратное преобразование имеет вид:

.                                     (20.**)

Здесь: T – период дискретизации,

n – номер отсчета дискретизированного сигнала, n = 0, 1, 2,…, N-1;

k – номер гармоники сигнала, k = 0, 1, 2,…, N-1, частота гармоник равна , где T_изм– период измерения;

W – вспомогательная функция.

Недостатком данного алгоритма является большой объем повторяющихся вычислений W^nk при различных комбинациях n и k. Устранение этих избыточных операций приводит к так называемому алгоритму быстрого преобразования Фурье, который обычно и используется. Быстрое Преобразование Фурье (БПФ) - способ вычислить преобразование последовательности A за время O(n logn), вместо обычного O(n²) в случае, если n - степень 2. (конец напоминания).

Поскольку квантовые вычисления имеют дело с унитарными преобразованиями, полезно рассмотреть некоторые из основных преобразований. Рассмотрим пример, в котором вводится техника для осуществления квантовым компьютером дискретного преобразования Фурье за полиномиальное время. Это преобразование будет представлено матрицей, строки и столбцы которой будут обозначать индексы состояний. Такие состояния соответствуют бинарному представлению целых чисел в компьютере. В частности, строки и столбцы будут обозначаться индексами, начиная с “0”, до некоторого числа, которое будет оговорено.

Это преобразование работает следующим образом. Рассмотрим число а, которое удовлетворяет двойному неравенству

 для некоторого q, где число q представлено некоторым числом битов, которое растет полиномиально. Мы хотим выполнить преобразование, которое переводит состояние  (это одно из базисных состояний, которыми может быть представлен вектор в q-мерном пространстве: ) - в суперпозицию состояний

                                                                              (20.7)

Другими словами, мы хотим применить к состоянию  матрицу, элементы  которой упорядочены по правилу  Такое преобразование Фурье лежит в основе нескольких квантовых алгоритмов. Будем обозначать соответствующую матрицу как A_q. В нашем примере мы ограничимся случаем, когда q является числом, пропорциональным степени двойки. Итак, пусть , а целое число а представим двоичной последовательностью . Оказывается, что для квантового преобразования Фурье A_q нам необходимо только два типа ЛЭ. Это однобитовые логические элементы , которые действуют на j-ый бит в квантовом компьютере:

                                                         (20.8)

и двухбитовые ЛЭ S_jk, которые действуют на биты, находящихся в регистре в положениях j и k, j < k.:

,                                                           (20.9)

где .

Например, пусть регистр представлен бинарной строкой , т.е. биты пронумированы по индексу l: . ЛЭ (20.9) действует на пару кубитов из регистра так, что если значения кубитов для индексов j и k, j < k отличаются, либо оба равны нулю, то ничего не происходит, а если кубиты оказываются в состоянии “1”, то значения кубитов не меняются, но добавляется фазовый множитель . Например, пусть k = 6, j = 2 (оба кубита имеют значение “1”). Получаем фазовый сдвиг . Таким образом, действие матриц S_j,k при действии их на регистр, сводится к  - т.е. только при a = b = 1, добавляется фаза .

Чтобы выполнить преобразование Фурье, достаточно подействовать на входной регистр набором матриц:

.                               (20.10)

Другими словами, запись (20.10) означает, что ЛЭ R_j действуют в обратном порядке от R_l-1 до R₀, а между R_j+1 и R_j применяются ЛЭ S_j,k, где k > j. Например, для 3-х битов (l = 0, 1, 2,3) матрица будет иметь вид:

.                                                                                 (20.11)

Для того, чтобы выполнить преобразование Фурье A_q при q = 2^l, нам необходимо  ЛЭ R_j и  элементов S_j,k. Сумма арифметической прогрессии, которую образуют число ЛЭ S_j,k равна . Тогда полное число ЛЭ, реализующих квантовое преобразование Фурье равно . Для трех кубитов нужно 6 ЛЭ. Заметим, что при экспоненциальном росте числа q, количество ЛЭ растет полиномиально с увеличением l. Здесь l - число кубитов, необходимых для представления q. Т.е. при добавлении одного двоичного разряда в представлении числа, само число вырастает в 2 раза (экспоненциально), а число ЛЭ - в  раз. Например, для рассмотренного случая l = 3 (q = 8), при увеличении до l + 1 = 4 (q = 16), получаем  -  в такое число раз увеличится число ЛЭ. Если же исходное число кубитов велико, скажем, l = 100 (2¹⁰⁰ = 10³⁰, поскольку 1024 = 2¹⁰ » 10³), то  - разница впечатляет!

Применение указанной последовательности преобразований (матриц) (20.10) дает состояние на выходе:

,                                                                             (20.12)

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

Как же работает такое преобразование Фурье?

Рассмотрим преобразование, переводящее состояние  в состояние . Прежде всего, заметим, что матрица R действует l раз (0, 1, 2,...l-1, т.е. всего l раз). Значит множители  в матрицах R перемножаются, что дает общий множитель . Поэтому, остается только понять, как получаются фазовые множители  в выражении (20.7). Прежде всего, заметим, что матрицы S_j,k не изменяют значения кубитов, они лишь меняют относительные фазы. Поэтому имеется лишь один способ переключить значение j-ого бита из a_j в b_j - с помощью матриц R_j. Их действие добавляет фазу p, если оба бита a_j и b_j находятся в состоянии 1 (имеют значение 1) и не меняет значение бита в других случаях . Далее, действие матрицы S_j,k сводится к добавлению  к соответствующей фазе, когда оба значения битов a_j и b_j равны 1, в противном случае, амплитуды не меняются. Тогда на пути преобразования от  к  происходит изменение фазы

                                                                              (20.13)

Поскольку в первой сумме в (20.13) стоит повторяющийся индекс j, то можно формально учесть это просто оставив только вторую сумму, но потребовав, чтобы индекс j мог бы принимать значение k. Т.о. выражение (20.13) можно преобразовать к виду:

                                                                                            (20.14)

Разница с предыдущим заключается только в индексе суммирования.

Поскольку состояние с представляет собой “реверсированное” состояние b, это выражение можно переписать как

                                                                                                     (20.15)

где мы просто поменяли порядок изменения индекса к: теперь биты в с нумеруются в обратном направлении.

Сделаем замену  в сумме (20.15). Тогда  и

         (20.16)

Учтем, что при суммировании добавление фазы  не влияет на общую фазу. Тогда, в итоге при суммировании по всем j и k, меньшим, чем l, получаем искомую фазу:

                                                                      (20.17)

где последнее равенство следует из свойства дистрибутивности умножения. Теперь получается, что  - двоичное представление числа а и аналогично для с, поэтому выражение (20.17) равно , что играет роль фазы в комплексной амплитуде перехода  преобразования (20.7).

Имеется, однако, большая проблема. Преобразование Фурье, которое было рассмотрено - это некая унитарная операция, описываемая матрицей размером LxL. Поэтому нельзя изначально предполагать, что ее можно осуществить за poly (logL) число элементарных операций. Можно показать, что любую унитарную операцию размером LxL можно выполнить на квантовом компьютере за  шагов. Однако классическому компьютеру требуется такое же количество шагов для выполнения операции умножения матрицы размером LxL на L - мерный столбец. В нашем случае Фурье преобразования A_q эта граница не может считаться удовлетворительной. Так для больших значений j - k при выполнении преобразования, выполняемого ЛЭ S_j,k (20.9), происходит домножение на число, имеющее очень малый фазовый множитель. Так в рассмотренном примере, этот фактор составляет , когда мы брали кубиты, номера которых отличались на 4. Если же оперировать с длинными числами, двоичное представление которых имеет много разрядов, показатель экспоненты резко уменьшается (для кубитов, отличающихся на 8 позиций, он составит ! Такое преобразование очень трудно точно реализовать физически и поэтому при выполнении квантовых вычислений появились бы факторы нарушающие такие вычисления. К счастью, было показано (Д.Коппершит, 1994), что результат можно интерпретировать как приблизительное преобразование Фурье, в котором игнорируются эти малые множители. Такое приблизительное преобразование весьма близко к точному и сильно уменьшает число ЛЭ, реализующих матрицы S_j,k. В целом, это позволяет выполнить квантовое преобразование Фурье не за , а за  шагов. Эти свойства вытекают из классической теории быстрого преобразования Фурье, где показано, как уменьшить число в  шагов, нужных для матричного умножения, до  шагов. Если применить тот же прием в квантовом случае, то модно показать, что число шагов сводится к . Этот факт позволяет использовать рассмотренное квантовое преобразование Фурье в алгоритме факторизации.

Алгоритмы факторизации числа на простые множители и дискретного логарифмирования были предложены Питером Шором. Сами по себе эти квантовые алгоритмы, действительно приводящие к выходу из NP-класа сложности не являются прорывом в области вычислительной техники, в том смысле, что эти методы, не являются основными в решении вычислительных задач. Единственная причина, по которой они интересны - то, что такие методы (односторонние функции) используются при распределении ключа. Заметим, однако, что к настоящему времени найден классический алгоритм, позволяющий определить является ли данное число простым или нет за полиномиальное время.

Перечислим известные к настоящему времени квантовые алгоритмы.

1. Алгоритм Саймона или задача “Оракула”, 1997г.. (экспоненциальное время при классических вычислениях и квадратичное время при квантовых). Он также известен под названием “алгоритм Дойча” (1985) и, наверное, является первым квантовым алгоритмом. Этот алгоритм решает задачу определения типа функции, глядя только на результат ее действия.

Бесплатная лекция: "Мероприятия по снижению стресс-коррозионных проявлений на МГ" также доступна.

2. Алгоритм разложения на простые множители или алгоритм Шора 1993г. Для факторизации L - битового числа N лучший классический алгоритм[1] асимптотически дает время . Квантовый метод дает асимптотически  шагов. Заметим, что функция  растет чрезвычайно медленно, поэтому можно считать, что квантовый метод дает . Ключевая идея этого алгоритма - определение периода некой последовательности с помощью фурье-преобразования. Период этой последовательности экспоненциально зависит от L, поэтому такой метод непрактичен для обычных классических вычислений.

3. Алгоритм поиска в базе данных . Известен также под названием “алгоритм Гровера” 1997г. Имеется список из N наименований. Классический алгоритм дает порядка N/2 обращений к базе данных для отыскания нужного наименования. Квантовый требует порядка  обращений. Например, если N = 10⁴, классический метод дает ответ примерно за 5000 обращений, а квантовый - за 100. Если же N = 10⁶, то в классике поиск потребует 5х10⁵. А квантовый метод всего 1000!

ЛИТЕРАТУРА

1. P.Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on Quantum Computer. Quant-ph/9508027.

2. P.Shor. Introduction to Quantum Algorithms. Quant-ph/000503.

[1] Ñ ïîïðàâêîé íà ñòàòüþ, âûøåäøóþ â 2002 ã, ãäå ïðåäëàãàåòñÿ êëàññè÷åñêèé ïîëèíîìèàëüíûé àëãîðèòì, òðåáóþùèé âðåìåíè ïîðÿäêà .