Самый заезженный пример – факторизация (разложение на простые множители) целых чисел [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