Українці можуть спати спокійно: чому нас не зможуть зламати квантові комп'ютери

Давайте дуже коротко поговоримо про квантові комп'ютери, про те, що вони вміють робити, що вони не вміють робити, і чому вони (наразі) все це (не) вміють у теорії.

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

По-перше, кубіт — не транзистор, бо він весь час намагається повернутися до класичного стану. Його можна порівняти з транзистором, який згоряє після кількох десятків перемикань. Тому зусилля дослідників спрямовані на те, щоб зробити логічний кубіт таким, який пропрацює достатньо довго.

По-друге, квантові комп'ютери нічого не обчислюють "паралельно" в класичному значенні цього слова. Система більше схожа на планку пам'яті, яка починається з простого стану, наприклад, усі "нулі", а потім ви починаєте її опромінювати — і біти всередині клацають за певними правилами. Визначити, що там усередині — "нуль" чи "одиниця" — не можна.

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

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

Є ще завдання, коли квантові алгоритми можуть працювати швидше, але:

1. не факт, що для них не існує швидшого класичного алгоритму,
2. не факт, що ці завдання є корисними.

Ті установки, що зараз називають квантовими комп'ютерами, генерують по суті випадкові числа. Дуже спеціального виду, але без будь-якої практичної користі. Їх справді складно повторити на звичайному комп'ютері. І складно тільки тому, що ви не вирішуєте завдання, досить безглузде, а моделюєте квантовий комп'ютер, який його вирішує. Це називають quantum supremacy ("квантова перевага"). Але змоделювати рух кожної краплі в струмку теж складно. Так, люди роблять аналогові комп'ютери для таких завдань. Років із 1950-х і без істерик.

Отже, поки що квантових комп'ютерів не існує. Щоб їх збудувати, потрібно зробити хоча б "квантовий калькулятор", а його також не існує. Чи можна його збудувати? Можливо. Коли? Колись. Ніхто не знає ані "як", ані "коли". Найближчим часом не передбачено.

Щоб розібратися в питанні, рекомендую книгу Scott Aaronson Quantum Computing Since Democritus.

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

У мене склалося враження, що жодного засобу криптографічного захисту, який використовує асиметричні алгоритми для шифрування, схваленого Держспецзв'язку, теж немає.

Першоджерело