Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
операций контролируемого изменения фазы при выполнении квантового фурье-преобразования равно L(L — 1)/2. Диапазон необходимых длительностей элементарных операций при сохранении точности квантового фурье-преобразования увеличивается с числом L экспоненциально и соответственно влияет на временную цену всего преобразования. Однако следует учесть, что минимальное значение длительности элементарной операции определяется временным разрешением регистрирующей системы, которое при больших значениях L может существенно ограничить этот диапазон и в результате привести к тому, что зависимость от L временной цены квантового фурье-преобразования хотя и будет более сильной, чем ~ L, но более слабой, чем I^ L2l [2.24]. Использование приближенного квантового фурье-преобразования, в котором уменьшается число операций контролируемого фазового сдвига до величины, определяемой требованием точности [2.25], может привести к аналогичному выводу. Более того, можно предложить оптимизационную процедуру выполнения такого преобразования, приводящую к полиномиальной зависимости временной цены квантового фурье-преобразования от L, позволяющую сохранить значительное ускорение квантового фурье-преобразования по сравнению с классическим фурье-преобразования и для неидеальных квантовых операций.
2.2.6. Алгоритм факторизации Шора
Алгоритм состоит в определении простых множителей р и q для заданного целого числа М = р • q путем использования квантовой схемы для определения периода г некоторой периодической функции вида ум(х) = ах mod М. где х = 0,1,... N — 1, N = 2L, а — любое число, не
2.2. Некоторые квантовые алгоритмы
87
имеющее общих делителей с рассматриваемым числом М. Например, в случае нечетного числа М — 15 можно выбрать, в частности, а = = 2 (если М — четное число, то задача разделения на множители, очевидно, сводится к задаче для соответствующего нечетного сомножителя), и тогда последовательность чисел 2°,21,... , 2х по модулю 15 представляется в следующем виде 1, 2, 4, 8, 1, 2, 4, 8 ... , то есть имеет период по х г = 4 и удовлетворяет уравнению 2Т = 1 mod 15 (в общем случае ат = 1 mod М, а параметр г называется порядком функции a mod М когда а < М и не имеет общих множителей с М).
Теперь, когда период г известен, множители числа М с помощью алгоритма Евклида определяются как наибольшие общие делители чисел 2r/2 =Ь 1 и М. В рассматриваемом случае будем иметь 15 = 5*3. Для записи этого числа, очевидно, необходимо 4 бита (24 = 16). В общем случае для записи числа М необходимо будет иметь около log2 М бит информации.
Вычислительная схема, используемая для осуществления квантового алгоритма Гора (P. Shor) (см. расширенную версию первого сообщения в 1994 г. [2.26], а также [2.22, 2.27]), представляет собой два квантовых регистра X и У, каждый состоящий в начальный момент из совокупности кубитов в нулевом булевом состоянии |0) = = |0l_i, 0^_2,... , Оо). Регистр X используется для размещения аргументов х (натуральные числа) функции ум{%), то есть N состояний \х) типа (2.39), а вспомогательный регистр Y используется для размещения значений самой функции ум(х) с подлежащим определению периодом г. Регистр Y должен быть достаточно большим, чтобы разместить значения функции ум{х), охватывающие достаточное число предполагаемых полных периодов. Для этого необходимо, чтобы число состояний регистра N = 2Ь ^ М2 ^ г2.
На первом этапе алгоритма начальное состояние |0) регистра X переводится с помощью операции Уолша-Адамара в равновероятную (с равными амплитудами) суперпозицию всех булевых состояний N = = 2Ь \х) = |жь-1, хь-2, • • • хо) при этом второй регистр остается в состоянии |0). В результате, для системы двух регистров получается состояние
N-1 N-1
\Ф,0]) = 1°> = лЛ7^?м>- (2.51)
х=0 х=0
Полное число необходимых логических операций на этом этапе опреде-
88
Глава 2
ляется числом элементарных операций Адамара, то есть числом L. Параллельно с помощью обратимой вычислительной операции квантовый регистр Y заполняется значениями функции ум(%) = 2Ж mod М и первоначальное состояние системы двух регистров превращается в суперпозицию, в которой между состояниями обоих регистров образуется определенная связь. Например, в случае М — 15 она имеет вид:
N—1 N-1
| <р[х,ум(х)]) = \х) ® IУм(х)) = л/l/NУ |ж) ® |2Ж mod 15) =
х=0 х=0
= лД7^(|0> ® |1) + |1> ® |2> + |2) ® |4) + |3) ® ®|8) + |4) ® |1) + |5) ® |2) + |6> ® |4) + ... + \N - 1) ® 12м-1 mod 15)), (2.52)
откуда следует, что последовательность значений функций (х) имеет период г — 4 и каждому фиксированному состоянию второго регистра соответствует последовательность амплитуд, оставшихся в первом регистре ж, с расстояниями друг от друга, равными периоду функции 2/15(х). Например, если зафиксировано состояние второго регистра |4), то в первом регистре соответствующие числа х отличаются на период г — 4:
