Нарешті з’явилася задача, яку зможуть вирішити тільки квантові комп’ютери

Фахівці з інформатики роками шукали задачі певного типу, вирішити які був би здатний тільки квантовий комп’ютер, але не класичний комп’ютер, нехай навіть з майбутніх поколінь. І ось вони знайшли одну з них.

На ранніх етапах вивчення квантових комп’ютерів фахівці з інформатики задали питання, відповідь на який, на їхню думку, повинен був відкрити якусь глибоку правду про можливості цих футуристичних машин. 25 років потому відповідь на нього був знайдений. У роботі, опублікованій в травні 2018, фахівці з інформатики Рен Рез та Авішай Тал запропонували переконливий доказ того, що обчислювальні можливості квантових комп’ютерів перевершують все, чого в принципі можуть досягти класичні комп’ютери.

Рез, професор Прінстонського університету і Вайзмановского наукового інституту, а також Тал, постдок Стенфордського університету, визначили особливий тип обчислювальних завдань. Вони довели, з одним застереженням, що квантові комп’ютери могли б ефективно вирішити завдання, а традиційні комп’ютери загрузли б навічно, намагаючись це зробити. Фахівці з інформатики шукали таку задачу з 1993 року, коли вперше визначили клас задач BQP, що включає в себе всі завдання, які здатен вирішити квантовий комп’ютер.

З тих пір вони сподівалися протиставити BQP клас задач, відомий, як PH, який включає всі завдання, здійснити на будь-якому локальному комп’ютері, навіть неймовірно просунутому, розробленому який-небудь цивілізацією майбутнього. Можливість такого протиставлення залежала від відшукання задачі, яка належала б до класу BQP, але не до класу PH. І тепер Рез і Тал зробили це.

Цей результат не робить квантові комп’ютери краще класичних з практичної точки зору. По-перше, фахівці з теоретичної інформатики вже знають, що квантові комп’ютери здатні вирішувати будь-які завдання, на які здатні класичні. А інженери з працею вирішують завдання створення корисної квантової машини. Але робота Рэза і Тала демонструє відмінність категорій, в яких знаходяться квантові і класичні комп’ютери – і те, що навіть у світі, в якому класичні комп’ютери перевищили межі будь-яких мрій, квантові комп’ютери все одно зможуть їх випередити.

Квантові класи

Базова завдання теоретичної інформатики – розділити завдання на класи складності. Клас складності містить всі завдання, які можна вирішити, маючи в своєму розпорядженні певним ресурсом, таким, як час або пам’ять.

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

Читайте також  GUI Psychology. Наше сприйняття інформації і зображень

Два знаменитих класу складності – це P і NP. P – це всі завдання, які здатний швидко вирішити класичний комп’ютер. (Завдання «чи є число простим?» належить до P). До NP належать всі завдання, які класичний комп’ютер не обов’язково вирішує швидко, але правильність наявного рішення будь-якої з яких він може швидко перевірити. («Які прості множники числа?» належить до NP). Вчені вважають, що класи P і NP розрізняються, але завдання довести це розходження є складною і найголовнішою з відкритих завдань у цій області.


PH містить NP, який містить P. Є BQP класом, окремим від PH?

У 1993 році фахівці з інформатики Ітан Бернштейн і Умеш Вазирани визначили новий клас складності, який вони назвали BQP, або «квантово-полиномиальное час з обмеженням ймовірності помилок». Вони визначили клас як такий, що містить всі завдання по прийняттю рішень – завдання з відповіддю «так» або «ні», які квантові комп’ютери здатні ефективно вирішувати. Приблизно в той же час вони довели, що квантові комп’ютери здатні вирішити всі завдання, на які здатні класичні. Тобто, BQP містить всі завдання, що містяться в P.

Ще один приклад окремих класів задач. Задача комівояжера запитує, чи існує шлях, що проходить через певні міста, більш короткий, ніж задану відстань. Така задача знаходиться в NP. Більш складна задача запитує, чи є це відстань найліпшим шляхом через ці міста. Така задача знаходиться в PH.

Однак вони не змогли визначити, чи містить BQP задачі, яких немає в іншому важливому класі задач, відомому, як PH, або «поліноміальна ієрархія». PH – це узагальнення NP. Він містить всі завдання, які можна отримати, почавши з завдання з NP, і ускладнюючи її, додаючи уточнюючі твердження на кшталт «існує» і «для всіх». Класичні комп’ютери поки не можуть вирішити більшу частину завдань з PH, але цей клас можна вважати класом задач, які класичні комп’ютери могли б вирішити, якби виявилося, що P еквівалентно NP. Інакше кажучи, щоб порівняти BQP і PH, треба визначити, чи є у квантових комп’ютерів перевагу перед класичними, яке залишиться, навіть якщо класичні комп’ютери раптово навчаться вирішувати набагато більше завдань, ніж вони можуть вирішити сьогодні.

Читайте також  Що таке UX/UI дизайн насправді?

«PH – один з найбільш простих існуючих класів складності», — сказав Скотт Ааронсон, спеціаліст з інформатики з Техаського університету в Остіні. «Тому ми начебто хочемо знати місце квантових обчислень у світі класичної складності».

Кращий спосіб розділити два класи складності – знайти завдання, доказово входить в один з них, і не входить в інший. Однак через поєднання фундаментальних і технічних перешкод, таке завдання було знайти дуже важко.

Щоб знайти завдання, що належить до BQP, але не до PH, потрібно визначити щось, до чого «класичний комп’ютер за визначенням не зміг би навіть ефективно перевірити відповідь, не кажучи вже про те, щоб знайти його, — сказав Ааронсон. – Це виключає безліч завдань, з якими ми працюємо в інформатиці».

Запитайте оракула

Завдання. Припустимо, у нас є два генератора випадкових чисел, кожен з яких видає послідовність цифр. Питання комп’ютера: є дві послідовності повністю незалежними один від одного, вони якось непомітно пов’язані (наприклад, отримана одна послідовність перетворенням Фур’є інший)? Ааронсон представив цю задачу «фурреляции» в 2009 і довів, що вона належить до BQP. Залишився другий, більш складний крок – довести, що фурреляция не входить до PH.


Рен Рез

У певному сенсі, саме це і вдалося зробити Рэзу і Талу. Їх робота поділяє BQP і PH за допомогою т. зв. “оракула” або «чорного ящика». Це поширений в інформатиці результат, до якого вдаються дослідники, коли те, що вони хочуть довести, ніяк їм не дається.

Найкращий спосіб розділити класи складності BQP і ЗР – виміряти обчислювальний час, необхідний для вирішення завдань з кожного класу. Але в інформатиці немає «глибокого розуміння реального обчислювального часу або можливості його виміряти», — сказав Генрі Юн, спеціаліст з інформатики з Торонтського університету.

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

Якщо ваше завдання – дізнатися, чи є таємна зв’язок між двома генераторами випадкових чисел, оракулу можна задавати питання на кшталт «яким буде шосте число у кожного генератора?» Потім потрібно порівняти обчислювальну потужність на основі кількості підказок, необхідних кожному комп’ютеру для вирішення завдання. Комп’ютер, з яким потрібно більше підказок, працює повільніше.

Читайте також  Реалізація BottomAppBar. Частина 1: Material компоненти для Android

«У якомусь сенсі ми розуміємо таку модель набагато краще. Вона більше говорить про інформації, ніж про обчисленнях», — сказав Тал.


Авішай Тал

Нова робота Рэза і тала доводить, що для вирішення проблеми форреляции квантовим комп’ютера буде потрібно набагато менше підказок, ніж класичного. Більш того, квантовому комп’ютера потрібна всього одна підказка, при тому, що в PH немає алгоритму розв’язання такої задачі навіть з необмеженою кількістю підказок. «Це означає, що існує вкрай ефективний квантовий алгоритм, який вирішує таку задачу, — сказав Рез. – Але якщо розглядати тільки класичні алгоритми, то, навіть якщо дійти до самих верхніх класів класичних алгоритмів, вони з нею не впораються». Це доводить, що з оракулом фурреляция належить до завдань, що належать до BQP, але не до PH.

Рез і Тал майже дійшли до цього результату близько чотирьох років тому, але не змогли зробити один крок в майбутньому доказі. А потім, усього за місяць до публікації, Тал почув про нову роботу за генераторів псевдовипадкових чисел, і зрозумів, що технології з тієї статті якраз дають те, що їм з Рэзом потрібно було для того, щоб закінчити їх власну. «Це був відсутній фрагмент», — сказав Тал.

Новини про поділ класів BQP і PH поширилися швидко. «Світ квантової складності гуде», — писав Ленс Фортнау, спеціаліст з інформатики з Технологічного університету Джорджії на наступний день після публікації роботи.

Робота дає залізну впевненість у тому, що квантові комп’ютери існують в окремому обчислювальному світі від класичних (принаймні, за визначенням з оракулом). Навіть у світі, де P еквівалентно NP – там, де вирішити задачу комівояжера так само просто, як знайти найбільш підходящу сходинку в електронній таблиці – доказ Рэза і Тала демонструє наявність завдань, вирішити які може тільки квантовий комп’ютер.

«Навіть якщо б P був еквівалентний NP, навіть з таким сильним припущенням, — сказав Фортнау, — квантові комп’ютери все одно не наздогнати».

Степан Лютий

Обожнюю технології в сучасному світі. Хоча частенько і замислююся над тим, як далеко вони нас заведуть. Не те, щоб я прям і знаюся на ядрах, пікселях, коллайдерах і інших парсеках. Просто приходжу в захват від того, що може в творчому пориві вигадати людський розум.

You may also like...

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *