Квантовый криптоанализ




Квантовый криптоанализ - часть 3


/p>

Представьте себе два квантовых регистра, каждый регистр состоит из определённого числа двухпозиционных квантовых систем, которые мы называем "кубитами" (квантовыми битами). Возьмём первый регистр и поместим его в суперпозицию всех возможных целочисленных значений, которые могут в нём находится. Это можно сделать, если первоначально установить все кубиты в состояние 0, а затем применить к каждому кубиту унитарное преобразование, которое создаёт суперпозицию состояний 0 и 1:

|0> ---> 1/\/2*(|0> + |1>)

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

1/\/2*(|0> + |1>) x 1/\/2*(|0> + |1>) = 1/2*(|00> + |01> + |10> + |11>)

где 00 - двоичный 0, 01 - двоичная 1, 10 - двоичная 2, и наконец, 11 - двоичная 3.

Затем мы производим арифметическую операцию, которая воспользуется преимуществом квантового параллелизма для вычисления функции FN(x) для каждого x в суперпозиции. Значения FN(x) заносятся во второй регистр, так что после вычисления два регистра оказываются переплетёнными:

Sumx(|x>|F(x))

(мы проигнорировали нормализационную константу). Теперь произведём измерение второго регистра. Измерение выдаёт случайно выбранное значение FN(k) для некоторого k. Состояние первого регистра сразу после измерения, вследствие периодичности FN(x), является когерентной суперпозицией всех состояний |x>, при которых x = k, k+r, k+2r, ..., то есть всех k, для которых FN(x) = FN(k). Значение k выбирается случайным образом, следовательно состояние первого регистра впоследствии трансформируется, посредством единичных операций, которые устанавливают любое k в 0 (то есть |k> становится равным |0> плюс фазовый фактор) и модифицируют период r до множества из 1/r. Эта операция известна как квантовое преобразование Фурье. Первый регистр после этого готов к последнему измерению, которые выдаст число, которое является наиболее лучше аппроксимацией множества из 1/r. Из этого результата можно вычислить r, после чего можно легко вычислить множители числа N. Время выполнения квантового алгоритма разложения предполагается, будет расти как квадратичная зависимость от L, и числа, состоящие из 100 цифр могут быть разложены за доли секунды!




Содержание  Назад  Вперед