Изменения
→Применение квантовых гейтов
* Разложить число на множители за <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> <ref>[https://ru.wikipedia.org/wiki/%C0%EB%E3%EE%F0%E8%F2%EC_%C3%F0%EE%E2%E5%F0%E0 Алгоритм Гровера]</ref>
* Осуществить дискретный алгоритм нахождения логарифма за полиномиальное время<ref>[https://ru.wikipedia.org/wiki/%C4%E8%F1%EA%F0%E5%F2%ED%EE%E5_%EB%EE%E3%E0%F0%E8%F4%EC%E8%F0%EE%E2%E0%ED%E8%E5 Дискретное логарифмирование.Вычислительная сложность и приложения в криптографии]</ref>
* Создать стойкую криптосистему: если "подслушать" квантовый бит, то он изменится <ref>[http://habrahabr.ru/post/127461/ Квантовая криптография стучится в дверь]</ref>
Построение квантового компьютера в виде реального физического прибора является фундаментальной задачей физики XXI века. В настоящее время построены только ограниченные его варианты (в пределах 512 кубит).
