142
правки
Изменения
→Применение квантовых гейтов
Квантовая модель вычислений позволяет:
* Разложить число на множители за <tex>n^2</tex>Постановка задачи разложения числа на множители выглядит следующим образом: на вход подается составное число <tex>N</tex> в двоичной записи, на выход должны быть выданы два числа <tex>p, q,</tex> такие что <tex>N = pq</tex>. Типичный размер <tex>N</tex> порядка <tex>2^{2000}</tex>. Мотивацией для решения данной задачи является отсутствие на данный момент полиномиального классического алгоритма. Решение этой задачи позволит, например, взломать систему RSA. Лучший из известных классических алгоритмов имеет <tex>O(2^{\sqrt[3]{n}})</tex> в качестве оценки времени работы. Уже сегодня существует квантовый алгоритм, который решает эту задачу за <tex>O(n^2)</tex> [Питер Шор, 1994].
* Сделать полный перебор за <tex>{\sqrt{n}}</tex>
* Осуществить дискретный алгоритм нахождения логарифма за полиномиальное время
