Украинцы могут спать спокойно: почему нас не смогут взломать квантовые компьютеры

Давайте очень коротко поговорим о квантовых компьютерах, о том что они умеют делать, что они не умеют делать, и почему они (на текущий момент) все это (не)умеют в теории.

Многие ошибочно думают, что квантовые компьютеры уже существуют и осталось дело за малым — увеличить количество кубитов, как в свое время увеличивалось (и до сих пор увеличивается) количество транзисторов в микросхемах.

Во-первых, кубит — не транзистор, он так и норовит вернуться в классическое состояние. Его можно сравнить с транзистором, который сгорает после нескольких десятков переключений. Потому усилия исследователей направлены на то, чтобы сделать логический кубит, который проработает достаточно долго.

Во-вторых, квантовые компьютеры ничего не вычисляют "параллельно" в классическом смысле этого слова. Система более похожа на планку памяти, которая начинается с простого состояния, например, все "нули", а потом вы начинаете ее облучать, — и биты внутри щелкают по определенным правилам. Определить, что там внутри, — "ноль" или "единица", — нельзя.

В-третьих, квантовый компьютер (который еще нужно построить) решает не любые задачи. Задачу коммивояжера на нем решить нельзя ("задачей коммивояжера" называют одну из задач комбинаторной оптимизации. Суть в том, чтобы найти наиболее выгодный маршрут, который в обязательном порядке должен проходить хотя бы раз через заданные заранее города, а затем должен быть проложен в обратном порядке, чтобы обеспечить возврат в исходный город, — ред.).

И большинство интересных задач решить тоже нельзя. По крайней мере никакого "квантового ускорения" не наблюдается. По странному стечению обстоятельств, помимо моделирования квантовых процессов (точно так же, как обычный компьютер "моделирует" классические), квантовые компьютеры могут быстрее решать задачи взлома симметричных шифров (алгоритм Гровера) и некоторых алгоритмов асимметричных шифров (алгоритм Шора).

Есть еще задачи, для которых квантовые алгоритмы могут работать быстрее, но:

1. не факт, что для них не существует более быстрого классического алгоритма,
2. не факт, что эти задачи полезные.

Те установки, которые сейчас называют квантовыми компьютерами, генерируют по сути случайные числа. Весьма специального вида, но без какой-либо практической пользы. Их действительно сложно повторить на обычном компьютере. И сложно только потому, что вы не решаете задачу, довольно бессмысленную, а моделируете квантовый компьютер, который ее решает. Это называют "quantum supremacy" ("квантовое превосходство"). Но смоделировать движение каждой капли в ручье тоже сложно. И да, люди делают аналоговые компьютеры для подобных задач. Годов с 1950-х и без истерик.

Так что пока квантовых компьютеров нет. Чтобы их построить, нужно сделать хотя бы "квантовый калькулятор", а его тоже нет. Можно ли его построить? Может быть. Когда? Когда-нибудь. Никто не знает ни "как", ни "когда". В ближайшее время не предвидится.

В качестве популярного введения рекомендую книжку Scott Aaronson "Quantum Computing Since Democritus".

P.S. И не стоит волноваться по поводу того, что нацбезопасности Украины угрожают взломы при помощи квантовых компьютеров.

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

Первоисточник