Скільки чекати квантової переваги?

У середині травня IBM відкрила публічний доступ до нового квантового комп'ютера, що оперує 16 кубітами. Крім того, для свого комерційного сервісу квантових обчислень компанія підготувала 17-кубітний пристрій з дуже низьким рівнем помилок. Раніше у теоретиків був доступ лише до пристроїв з п'яти кубітів - новий обчислювач втричі піднімає цю планку.

Зазвичай квантові комп'ютери асоціюються з величезним приростом у продуктивності і вирішенням завдань, непосильних навіть для суперкомп'ютерів. Одночасно з цим квантові комп'ютери - серйозна загроза алгоритмам шифрування. Чи настало квантове майбутнє і чи варто терміново переходити на нові системи шифрування - однаково складні для звичайних і для квантових пристроїв, - на ці питання ми постараємося відповісти в новому тексті.

Що таке квантовий комп'ютер?

Звичайний комп'ютер - це універсальний обчислювальний пристрій, який можна програмувати, а потім виконувати за його допомогою будь-які послідовності класичних операцій. Відштовхуючись від такого визначення, квантовим комп'ютером варто було б назвати такий самий пристрій, але з однією відмінністю: в його роботі спостерігалися б явища квантової фізики. Однак це визначення було б не цілком вірним. У будь-якому сучасному комп'ютері і так протікають квантові процеси - наприклад, витік струму з транзисторів в результаті тунелювання. Ці процеси доводиться враховувати при проектуванні комп'ютерів, тому, в деякому сенсі, навіть той пристрій, з якого ви читаєте цей текст - теж квантовий комп'ютер.

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

У чому відмінність квантових обчислень від класичних?

Як в основі класичних обчислювачів лежать операції з бітами, так у випадку з квантовими комп'ютерами об'єктом операцій стають квантові біти, або кубіти. При вимірі біта ми завжди отримаємо один і той же результат - «нуль» або «одиницю». Вимірювання однаково приготованих кубітів буде з деякою ймовірністю давати і «нуль», і «одиницю» - до вимірювання кубіт буде одночасно і «нулем» і «одиницею». Як кажуть фізики - він буде в суперпозиції двох станів.

Виявляється, така незвичайна одиниця даних дозволяє спростити вирішення багатьох обчислювальних завдань, особливо - пов'язаних з перебором. Зате такі завдання, як складання двох натуральних чисел (наприклад, 2 + 2), для квантового комп'ютера виявляються зовсім не тривіальними.

Що представляють собою квантові біти?

Фізично кубіти бувають різних типів. Найпоширеніші (їх використовують наукові групи і IBM) - надпровідні. Це кільця з надпровідника з невеликою ізолюючою перемичкою, в яких струм тече одночасно і по, і проти годинникової стрілки. Інакше їх називають джозефсонівськими контактами. Крім того, існують кубіти на базі окремих атомів, захоплених лазерними променями. Роль нуля і одиниці в них відіграють стану електронної оболонки атомів. На їх основі вже були побудовані універсальні квантові комп'ютери. Розробляються кубіти і на основі нанорозмірних кристалів напівпровідників - квантових точок.

Які завдання квантовий комп'ютер вирішує краще класичного?

Один з найпростіших прикладів - алгоритм Дойча. Припустимо, у вас є функція, яка може мати значення нуль або одиниця, залежно від аргументу. Аргумент теж може бути нулем або одиницею. Всього існує чотири таких простих функції. Щоб дізнатися, чи завжди ця функція видає строго нуль або строго одиницю, класичному алгоритму потрібно двічі її обчислити. Для квантового алгоритму вистачить одного обчислення.

Інший приклад - алгоритм Шора для розкладання натурального числа на прості множники. Класичні алгоритми можуть зробити це тільки повним перебором, причому зі зростанням кількості знаків у розкладуваному натуральному числі кількість операцій зростає експоненційно (умовно, кожен знак збільшує час розрахунку в 10 разів). Квантовому алгоритму потрібен лише поліноміальний час (поліном від числа знаків у числі).

Є ще кілька прикладів, пов'язаних з перебором, які швидко вирішуються за допомогою квантових алгоритмів. Основний приріст продуктивності в таких завданнях пов'язаний саме з існуванням кубітів у суперпозиції станів. Цікаво, що в ряді випадків в алгоритм можна вводити суперпозицію порядку обчислень. Тобто, наприклад, одночасно проводити над числом множення, а потім зведення в ступінь, і зведення в ступінь, а потім множення. Такі операції дозволяють з'ясувати за одну дію, чи є різниця між порядком виконання двох операцій (, і.

Крім того, дотримуючись природи квантового комп'ютера, з його допомогою можна моделювати квантові системи. Щоб проаналізувати поведінку системи з 50 кубітів (тут - частинок, які можуть бути в двох станах одночасно), потрібно щонайменше 2⁵⁰ біт оперативної пам'яті - не враховуючи логічні вентилі в системі.

Як це пов'язано з тим, з чим можна зустрітися в реальному житті?

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

З квантовим комп'ютером пов'язані і деякі побоювання - йому під силу виявляються багато завдань з розшифровки даних. Наприклад, алгоритм шифрування RSA заснований на тому, що класичний комп'ютер не може за розумний час розкласти на прості множники число довжиною кілька тисяч біт. Тому ключ дешифрування можна передавати у відкритому вигляді. Якщо хакер зберігає десь набір відкритих ключів і даних, зашифрованих з їх допомогою, то в майбутньому квантовий комп'ютер допоможе йому розшифрувати ці дані. Цікаво, що з тих же міркувань квантовий комп'ютер можна використовувати для атаки на системи блокчейна, подібні біткойну.

Варто зазначити, що побоювання, що стосуються алгоритму RSA, можуть бути передчасними. Зі зростанням ключа буде рости і час обчислення для квантового комп'ютера - для ключа розміром в терабіт буде потрібно понад 2¹⁰⁰ операцій квантового комп'ютера. Практичність використання ключів настільки великого розміру - окреме питання. Тим не менш, багато компаній вже почали розробляти методи постквантової криптографії, однаково складні для дешифрування і класичним, і квантовим комп'ютером. Наприклад, у деяких версіях Chrome такі алгоритми вже використовуються.

Тобто квантовий комп'ютер вже перевершив класичний?

Зараз квантові комп'ютери знаходяться лише на перших стадіях свого розвитку - навіть багаторазовий приріст продуктивності через використання квантових алгоритмів не дозволяє їм надійно перевершити звичайні комп'ютери. Тим не менш, вже є серйозні заявки на квантову перевагу від неуніверсальних квантових обчислювачів. Це пристрої, які здатні вирішувати строго певну задачу. Наприкінці 2015 року показала, що пристрій для квантового відпалу в 100 мільйонів разів швидше вирішує завдання оптимізації, ніж звичайний комп'ютер. Однак йшлося про спеціально розроблене штучне завдання, що підходить для конкретної мети. А нещодавно група китайських фізиків розробила бозонний семплер, який завдяки своїй квантовій природі обійшов ENIAC (перший комп'ютер людства) в 220 разів.

Але універсальні квантові комп'ютери, які можна порівнювати з класичними комп'ютерами, все ще використовують занадто малу кількість кубітів - до 17 штук. Такі системи все ще можна повністю моделювати навіть звичайним настільним комп'ютером.

Скільки треба кубітів, щоб обійти сучасні суперкомп'ютери?

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

Без боротьби з помилками збільшення кількості кубітів практично не збільшує продуктивності системи. Так, за оцінками фізиків, нова 16-кубітна система IBM лише на 40 відсотків продуктивніша 5-кубітного комп'ютера-попередника. Надпровідні кубити цього типу роблять близько однієї помилки на 100 операцій. За словами фахівців IBM, комерційний 17-кубітний квантовий комп'ютер за рахунок зниженого рівня помилок володіє в два рази більшою продуктивністю.

За різними оцінками, для надійної демонстрації квантової переваги з урахуванням неідеальності реальних систем буде потрібно близько 50 кубітів. Нарощувати число кубітів дуже складно через процеси декогеренції.

Тим не менш, фізики вважають, що цей кордон скоро вдасться перетнути. Так, лабораторія компанії під керівництвом Джона Мартініса планує запустити 20-кубітний універсальний комп'ютер протягом найближчого місяця. А в найбільш амбітні плани входить запуск 50-кубітного універсального квантового комп'ютера вже до кінця 2017 року.