Внедрение Q# в ваши любимые языки и платформы (Python, .NET, ASP.NET, Julia, Lua, PowerShell) / Comments / Habr

BkmzSpb Nov 26 2021 at 13:11

Первое, что нужно понять, квантовый компьютер -- это не компьютер "с квантами", а отдельное устройство для решения определенных, весьма специфических задач (по крайней мере сейчас и, вероятно, в ближайшие 10-20 лет). Ближайшая аналогия -- дискретная видеокарта. Видеокарта никогда не выполняет код, который пишет "hello world' в консоль, она лишь принимает некий специфический байткод шейдера, какие-то данные (через не самую быструю шину), после чего выполняет какие-то действия внутри себя и либо выдает результаты обратно (например, как результат compute-шейдера), либо выводит их в стороннее устройство -- как кадр вашей любимой игры на подключенные мониторы.

Квантовый компьютер действует аналогично -- это не замена CPU. Квантовый компьютер так же принимает какой-то код программы -- на данном этапе это последовательность gates, которые определяют, какие операции применяются к каким кубитам. Фактически это квантовые машинные инструкции а не высокоуровневые функции. Далее в квантовый компьютер можно отправить данные -- закодировать начальне состояния кубитов в 0 или 1. После происходит "выпонение" алгоритма. После чего результат можно считать -- измерить состояние каждого кубита (после чего кубиты становятся бесполезными и продолжать вычисления с ними можно только начав с самого начала), при этом все возможные квантовые состояния кубита при измерении дают либо 0 либо 1. Вот тут начинается самое интересное. Если кубит не находится в состоянии "строго 0" или "строго 1", то результат измерения будет случайным, но при этом подчиняясь определенному распределению.

Так что же это значит?

Выполнив алгоритм один раз, вы не получите никакого результата. Если на выходе вы считываете один кубит и знаете, что ожидамое распределение -- 70% это 1 и 30% это 0, то прогнав данные 10 раз в идеальном случае вы получите 7 измерений 1 и 3 измерений 0, после чего сможете сделать какой-то вывод. Больше прогонов -> лучше статистика, особенно для сложных алгоритмов где вероятности могут слабо отличаться друг от друга.
Особенность квантовых вычислений -- в их скорости, а точнее в количестве операций, необходимых для получения результата. Иными словами, сложность алгоритмов -- меньше, и при определенном стечении обстоятельств решение некоторых задач, даже учитывая особенности, описанные в пункте 1, будет происходить на порядки быстрее, чем на обычном CPU. Это в свою очередь позволяет достичь "квантового превосходства" (quantum supremacy) -- решение с помощью квантового компьютера задачи, которую ни один обычный компьютер/суперкомпьютер не сможет решить за разумное время ( = ни один гипотетический суперкомпьютер с самыми лучшими чипами на планете не сможет решить проблему).

Из совсем простых примеров -- алгоритм Гровера, который фактически позвояет найти элемент в неупорядоченной коллекции за N^0.5, вместо классического N. Не самый значительный прирост (квадратичные а не экспоненциальный), тем не менее на очень больших данных разница будет колоссальна.

Чуть более сложный, но при этом намного более эффективный алгоритм -- алгоритм Шора, который факторизует целые числа (ищет все простые делители). Если совсем на пальцах, классический алгоритм имеет сложность порядка exp(log(N)), а алгоритм Шора -- log(N) (опуская множители и полиномиальные степени которые не влияют на общую картину). Это в свою очередь ставит под угрозу стандартне методы шифрования, которые полагаются на невозможность быстрой факторизации классическими методами.

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