У 1994 році один математик придумав, як змусити квантовий комп’ютер робити те, чого жоден звичайний класичний комп’ютер не міг. Робота показала, що в принципі машина, заснована на правилах квантової механіки, може ефективно розбивати велике число на прості множники — завдання настільки складне для класичного комп’ютера, що воно є основою для більшої частини сучасної безпеки в Інтернеті.
Пішов приплив оптимізму. Можливо, думали дослідники, ми зможемо винайти квантові алгоритми, які зможуть вирішити величезну кількість різноманітних проблем.
Але прогрес зупинився. «Це була трохи неприємна траєкторія», - сказав Райан О'Доннелл Університету Карнегі-Меллона. «Люди казали: «Це дивовижно, я впевнений, що ми отримаємо багато інших дивовижних алгоритмів». Ні. Вчені виявили різке прискорення лише для одного вузького класу проблем із стандартного набору називається НП, що означає, що вони мали рішення, які можна було ефективно перевірити, наприклад факторинг.
Так було майже три десятиліття. Потім у квітні дослідники винайдений принципово новий вид задачі, яку квантовий комп’ютер має бути здатний розв’язувати експоненціально швидше, ніж класичний. Він передбачає обчислення вхідних даних для складного математичного процесу, заснованого виключно на його плутаних результатах. Поки що не встановлено, чи ця проблема є окремою, чи є першою на новому рубежі серед багатьох інших.
"Є відчуття хвилювання", - сказав Вінод Вайкунтанатан, спеціаліст з інформатики в Массачусетському технологічному інституті. «Багато людей думають про те, що ще є».
Комп’ютерні вчені намагаються зрозуміти, що квантові комп’ютери роблять краще, вивчаючи математичні моделі, які їх представляють. Часто вони уявляють собі модель квантового або класичного комп’ютера в поєднанні з ідеалізованою обчислювальною машиною, яка називається оракул. Оракули схожі на прості математичні функції чи комп’ютерні програми, які приймають вхідні дані та видають заздалегідь визначені результати. Вони можуть мати випадкову поведінку, виводячи «так», якщо вхідні дані потрапляють у певний випадковий діапазон (скажімо, від 12 до 67), і «ні», якщо це не так. Або вони можуть бути періодичними, так що введення від 1 до 10 повертає «так», від 11 до 20 дає «ні», від 21 до 30 знову видає «так» і так далі.
Скажімо, у вас є один із цих періодичних оракулів, і ви не знаєте період. Все, що ви можете зробити, це надати йому цифри та подивитися, що він виведе. З такими обмеженнями, як швидко комп’ютер зможе знайти крапку? У 1993 році Деніел Саймон, який тоді працював у Монреальському університеті, виявив, що квантовий алгоритм може обчислити відповідь на тісно пов’язану проблему експоненціально швидше, ніж будь-який класичний алгоритм.
Результат дозволив Саймону визначити одну з перших натяків на те, де можна очікувати різкої переваги квантових комп’ютерів. Але коли він подав свою статтю на провідну конференцію, її відхилили. Проте стаття зацікавила молодшого члена програмного комітету конференції — Петро Шор, який на той час працював у Bell Laboratories у Нью-Джерсі. Далі Шор виявив, що він може адаптувати алгоритм Саймона для обчислення періоду оракула, якщо він є. Тоді він зрозумів, що може ще раз адаптувати алгоритм, щоб розв’язати рівняння, яке поводиться подібно до періодичного оракула: рівняння, яке описує розкладання на множники, яке є періодичним.
Результат Шора став історичним. Відкритий ним квантовий алгоритм міг швидко зводити гігантські числа до складових простих множників, чого не може зробити жоден відомий класичний алгоритм. У наступні роки дослідники відкрили інші ефективні квантові алгоритми. Деякі з них, як-от алгоритм Шора, навіть забезпечували експоненціальну перевагу, але ніхто не міг довести драматичної квантової переваги в будь-якій задачі NP, яка не була періодичною.
Цей брак прогресу змусив двох комп’ютерників, Скотт Аронсон Техаського університету в Остіні та Андріс Амбайніс Університету Латвії, щоб зробити спостереження. Докази квантової переваги завжди здавалися залежними від оракулів, які мали якусь невипадкову структуру, таку як періодичність. У 2009 році вони здогадався що не може бути різкого прискорення проблем NP, які були випадковими чи неструктурованими. Ніхто не міг знайти виключення.
Їхня гіпотеза обмежила можливості квантових комп’ютерів. Але в ньому сказано лише те, що не було різкого прискорення для конкретного типу неструктурованої проблеми NP — тих, з відповідями «так» або «ні». Якщо проблема передбачала пошук більш конкретних кількісних відповідей, що називається проблемою пошуку, гіпотеза не застосовувалася.
Маючи це на увазі, дослідники Такаші Ямакава лабораторій соціальної інформатики NTT та Марк Жандри з NTT Research і Прінстонського університету вирішили поекспериментувати з конкретною проблемою пошуку, представленою в 2005 році Од Регев.
Уявіть собі набір флюгерів, які всі спрямовані в одному напрямку. Розмірено штовхніть кожного з них, а потім дозвольте поривчастому вітру змінити їх напрямок. Регев хотів визначити, ґрунтуючись на їхніх остаточних напрямках, куди вони всі вказали спочатку. Подібні проблеми стали називати «навчанням з помилками», оскільки поштовх і вітер діють як джерело випадкових помилок у початковому напрямку. Є докази того, що це важко вирішити як для класичних, так і для квантових алгоритмів.
Ямакава та Жандрі підкоригували налаштування. Вони змінили силу стартових ударів, зробивши їх більш передбачуваними. Вони також спричинили визначення вітру випадковим оракулом, так що в одних випадках він був ще більш випадковим, але повністю сплячим в інших.
Завдяки цим модифікаціям дослідники виявили, що квантовий алгоритм може ефективно знаходити початковий напрямок. Вони також довели, що будь-який класичний алгоритм повинен бути повільнішим на експоненціальний коефіцієнт. Як і Шор, вони адаптували свій алгоритм для вирішення реальної версії проблеми, яка замінює оракул справжнім математичним рівнянням.
Комп’ютерні спеціалісти все ще працюють над розумінням проблеми та її розробкою. Вайкуннатан порівнює це з іншим, що виникає під час стиснення даних: коли інформація стискається, два біти можуть бути випадково стиснуті в одному місці, перезаписуючи їх. Проблема прогнозування цих зіткнень заздалегідь, щоб ви могли їх уникнути, має певну схожість. «Це клас проблем, які в основному виглядають так», — сказав він. «Можливо, ці проблеми можна вирішити кількісно».
Існували надії, що неструктуровану проблему, подібну до нової, можна вирішити навіть на сьогоднішніх молодих версіях квантових комп’ютерів, що дасть можливість їх перевірити. Думка полягала в тому, що неструктуровані проблеми можуть потребувати менше ресурсів для програмування або бути менш чутливими до шуму, оскільки вони вже є випадковими. Але поки що нова проблема все ще виглядає занадто складною, щоб існуючі квантові комп’ютери її могли вирішити. «Це дивна проблема. Я не думав, щоб визначити це», - сказав Ааронсон. «Але в ретроспективі він має кілька дуже приємних особливостей».
Результат є першим прикладом значної квантової переваги в неструктурованій проблемі NP. Чи може бути багато інших проблем, які квантовий світ перетворює з практично нерозв’язних на розв’язні? Тепер є більше підстав так думати.
«Це дещо перевернуло наші переконання щодо того, з якими проблемами можуть справлятися квантові комп’ютери», — сказав О'Доннелл.
