Недавно попалось видео, где на обложке утверждается, что квантовые компьютеры - хайп. Решил послушать, ожидал услышать стандартное про то, что концепция нереалистична, но неожиданно блогерша утверждала нечто другое: наоборот, успехи последних лет в области технологий квантовых вычислений впечатляющие и, более того, идут по графику: разработанный компаниями ранее график, например, в каком году сколько будет кубитов в квантовом компьютере, выполняется. А вот слабое место - это алгоритмы.

На данный момент есть только две практические задачи, где квантовый компьютер даёт экспоненциальное (то есть как бы "качественное") преимущество над обычным (классическим) компьютером:

1. Алгоритм Шора разложения целых чисел на простые сомножители (91=13*7). Это взлом шифров, то есть "военное" применение, для народного хозяйства это не нужно.

2. Симуляция квантовых систем - например, сложных химических систем, кристаллических решёток. Это создание новых материалов, лекарств и т.д.

И в том и в другом случае с ростом размерности задачи (количества разрядов в числе или количестве атомов в химической системе) сложность классических вычислений растёт с числом разрядов в целом числе или числом симулируемых атомов примерно в геометрической прогрессии(*), то есть очень быстро. Сложность решения этих задач на квантовом компьютере растёт не рак быстро.

Есть ещё много других квантовых алгоритмов, например, тоже широко известный алгоритм Гровера поиска подходящего элемента в неупорядоченном списке. Но они дают не очень сильное, не экспоненциальное ускорение. Грубо говоря, не качественное, а только количественное ускорение, которое на практике исчезнет совсем из-за необходимости бороться с шумами, из-за того, что каждый логический кубит должен будет реализовываться через минимум сотни физических, что мы уже обсуждали.

(*) Более правильно и точно не "геометрическая прогрессия", а всё-таки "экспоненциальный рост". Например, число операций по разложению целого числа с n разрядами на множители растёт пропорционально 2^(кубический корень из n) для лучших известных классических алгоритмов. Это несколько медленнее геометрической прогрессии. Для квантового алгоритма Шора число операций пропорционально n^3 для (но есть и улучшения). Но использую близкий термин "геометрическая прогрессия" из школьной математики. С точки зрения теории сложности вычислений степенная функция (в данном случае куб) и функция, возрастающая быстрее любой степени (геометрическая прогрессия - частный случай), - это качественное различие.

https://youtu.be/pDj1QhPOVBo?si=c384VIpf7oewPgxn