Дарья Ежик
январь 2016.
3190

Какие задачи невозможно решить с помощью современных компьютеров, но будет возможно с квантовым?

Ответить
Ответить
Комментировать
1
Подписаться
4
1 ответ
Поделиться

Самый заезженный пример – факторизация (разложение на простые множители) целых чисел [1]. Некто взял простые числа X и Y, сообщил вам их произведение X*Y. Вам нужно выполнить обратную операцию: зная только X*Y, найти эти X и Y. Например, вам сообщают число 143, а вы в ответ должны назвать 11 и 13, потому что 11*13 = 143.

Пока никто не придумал алгоритм, который позволил бы классическому компьютеру раскладывать числа на простые множители за разумное время. На сегодняшний день рекордное достижение – разложение 768-битного (или 232-значного) числа на два простых 384-битных (116-значных) множителя, на что ушло несколько лет работы коллектива исследователей [2].

Суммарно все процессоры, задействованные в переборе, выполнили примерно 10^20 (100 квинтиллионов) операций. Если бы вы попробовали повторить эти вычисления на одноядерном процессоре с частотой 2.2 ГГц, вам пришлось бы ждать ответа примерно 2000 лет.

Подлость в том, что разложить 1024-битное число (которое всего на треть длиннее) примерно в тысячу раз сложнее. То есть даже относительно небольшое увеличение входного числа приводит к катастрофическому росту вычислительной сложности и делает задачу неразрешимой для существующих классических компьютеров.

Квантовый компьютер может щелкать такие задачи как орешки. С 1994-го года известен алгоритм Шора [3], который позволяет искать простые множители за время порядка N^3, где N – количество бит в числе. То есть увеличение длины числа в 2 раза увеличивает время работы алгоритма примерно в 8 раз. Это, конечно, бесконечно лучше, чем суб-экспоненциальный рост сложности лучшего из классических алгоритмов.

Ссылки для чтения на ночь:

[1] wikipedia.org

[2] wikipedia.org

[3] wikipedia.org

5
-1
Прокомментировать
Ответить
Читайте также на Яндекс.Кью
Читайте также на Яндекс.Кью