Квантовые компьютеры: надежды и реальность - Валиев К.А.
Скачать (прямая ссылка):
ИМ) = \/l7^(|2) + |6) + |10) + ... + |4^ + o) ® 14) =
,_________ А (2.53)
= Vi/(A+i)X)irj’+^014)’
3=0
где 0 ^ I ^ г < М, А = [N/r — 1] (целая часть). В рассматриваемом случае 1 = 2 — начальное значение х в (2.53), определяемое выбором фиксированного значения состояния второго регистра |4).
Состояние (2.53) является однородной некогерентной суперпозицией нумеруемых числами j и I базисных состояний в первом регистре с периодом г в зависимости от х = г j + I (рис. 2.5а). Таким образом, второй регистр служит для приготовления периодического состояния в первом регистре. Это оказывается возможным благодаря использованию суперпозиции квантовых состояний обоих регистров, что является проявлением квантового параллелизма в алгоритме Шора. При
2.2. Некоторые квантовые алгоритмы
89
этом не возникает необходимости отдельного измерения состояния второго регистра.
На втором этапе алгоритма для экстракции периода г над состоянием первого регистра производится операция фурье-преобразования (2.41) (для простоты предположим, что N точно делится на г, так что А =
= N/r — 1):
A N-1
QFTjy: уЯЙ^\гЗ+1) =* (2'54)
j=0 ?;=0
где
'2ni(jr + /)&>
3=0
Вероятность получить состояние |fc) определяется выражением
fi(k) = (y/r/N)^2ex (2.55)
А 2 P(k) = \fi(k)\2 = {r/N2)^2exp[2Trijrk/N] , (2.56)
j=o
которое не зависит от /. Учитывая, что основной вклад в (2.56) дают слагаемые, у которых rk/N близко к целому числу, точнее
—г/2 ^ rk mod N ^ г/2, (2.57)
в случае малых значений r/N для каждого значения г, которое удовлетворяет (2.57), можно получить оценку для вероятности [2.22]:
р(к) ^ 4/(7г2г). (2.58)
Из (2.58) следует, что по крайней мере с вероятностью 4/7Г2 = 0,405 измеренное значение к принимает дискретные значения к = vN/г, где v = 0,1,... г — 1 — целое число. То есть в результате квантового фурье-преобразования суперпозиция (2.53) преобразуется в равновероятную суперпозицию (2.55) с периодом N/r (рис. 2.5 6).
Измерение вероятности (2.56) позволяет далее определить значения к = vN/г, имея которые при известном fc/iV, можно найти отношение v/г. Если v и г не имеют общих множителей, кроме единицы, можно
90
Глава 2
\<рА
r/N-
I t(k)\
4/л-2
x=rj+l
б)
N/r N/r N/r N/r N/r N/r
k=vN/r
Рис. 2.5. Схематический вид идеальных зависимостей функций а) \срг (ж)|2 и б) \f(k)\2 в отсутствии декогерентизации.
определить период г путем преобразования отношения v/r к неприводимому виду, то есть к виду, когда числитель и знаменатель не имеют других общих наибольших делителей, кроме единицы. После этого с помощью алгоритма Евклида легко найти и множители числа М.
Определение неизвестного периода с помощью фурье-преобразова-ния в некоторой степени аналогично измерению постоянных решетки кристалла методом рентгеновской или нейтронной дифракции. Заметим также, что для определения периода г не требуется определять все значения ум(х). В этом смысле задача подобна задаче Дойча, в которой важно знать только некоторые свойства функции /(ж), а не все ее значения.
Алгоритм Шора содержит вероятностный аспект. Это связано с тем, что благодаря наличию разного рода шумов период г, а следовательно, и множители числа М. полученные в процессе описанных выше вычислений, не будут точными. Реально для извлечения периода из фурье-преобразования следует произвести еще ряд дополнительных вычислительных операций, например, произвести умножение полученных множителей с помощью классических вычислительных операций для проверки результата. Если число М не получится, то весь алгоритм Шора повторяется с другим значением v, пока не будет получен правильный ответ. Это может, вообще говоря, существенно ухудшить эффективность всей процедуры алгоритма квантовой факторизации.
2.2. Некоторые квантовые алгоритмы
91
Разложения числа N на множители с помощью классических операций в простейшем случае можно попытаться сделать путем деления N на 2, 3, 4 и т.д. до y/N. Число элементарных операций в этом случае будет y/N = 2L/2, то есть экспоненциально зависит от числа кубитов в регистре L. Проблема факторизации стала привлекать внимание, в связи с использованием систем секретного обмена данными по открытому каналу связи с открытым ключом (криптография), например, шифрованных по методу RSA (R. Rivest, A. Shamir, L.Adleman).
Наилучший из известных сейчас классических алгоритмов факторизации требует порядка exp(const-L1/3(logL)2/3) операций [2.28]. Для факторизации, например, 1000-значного числа (соответствующий регистр должен был бы иметь L ~ 1000 кубит!) потребуется ~ 1023 классических операций, которую гигофлопный классический компьютер выполнял бы за более чем 107лет.
