Аспірантка вирішила задачу підтвердження квантових обчислень

Урмила Махадев провела вісім років в магістратурі в пошуках відповіді на один з найбільш базових питань квантових обчислень: звідки нам знати, що квантовий комп’ютер зробив хоч щось на квантовому рівні?

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

Махадев, якій на той момент було 28, вже сьомий рік була в магістратурі в Каліфорнійському університеті в Берклі – набагато довше, ніж строк, на який потрібно більшості студентів, щоб втратити терпіння і захотіти вже закінчити навчання. І ось, нарешті, вона змогла скласти «прекрасну докторську дисертацію», — сказав Умеш Вазирани, її куратор в Берклі.

Але Махадев не закінчила навчання в тому році. Вона навіть не розглядає це питання. Вона ще не закінчила.

Більше п’яти років вона працювала з іншої дослідницької завданням, яку Ааронсон назвав «одним з найбільш базових питань, який можна поставити в області квантових обчислень». А саме: якщо ви просите квантовий комп’ютер зробити для вас обчислення, звідки вам знати, чи він вашим інструкціям, та й взагалі, чи робить щось на квантовому рівні?

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

Але як тільки квантовий комп’ютер зможе проводити обчислення, на які не здатна класичний, звідки нам знати, що він проводить їх правильно? Якщо не вірити звичайного комп’ютера, в теорії можна ретельно вивчити кожен крок його обчислень самостійно. Але квантові комп’ютери за своєю суттю чинять опір подібним перевірок. Для початку, їх робота надзвичайно складна: щоб записати опис внутрішнього стану комп’ютера, що складається всього з декількох сотень квантових бітів, або кубітів, потрібно жорсткий диск розміром більше спостережуваного Всесвіту.

І навіть якщо б у вас було місце для запису цього опису, його ніяк не можна було розібрати. Внутрішній стан квантового комп’ютера зазвичай являє собою суперпозицію багатьох не квантових, а класичних станів (як у кота Шредінгера, який одночасно живий і мертвий). Але як тільки ви виміряєте квантовий стан, воно тут же схлопнется в одне з класичних. Загляньте всередину квантового комп’ютера з 300 кубітами – і ви побачите тільки 300 класичних біт, нулів і одиниць, ввічливо усміхнених вам у відповідь.

«Квантовий комп’ютер – штука потужна, але таємнича», — сказав Вазирани.

Враховуючи подібні обмеження, фахівці з інформатики давно вже думали про те, чи може квантовий комп’ютер забезпечити абсолютно надійну гарантію, що він реально зробив те, що заявляє. «Достатньо сильним буде взаємодія між квантовим і класичним світами, щоб зробити такий діалог можливим?» – запитала Доріт Ахаронова, спеціаліст з інформатики з Єврейського університету в Єрусалимі.

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

Але вона відмовлялася здаватися. Махадев продемонструвала такий рівень незмінною рішучості, який Вазирани до цього не зустрічав. «У цьому сенсі Урмила абсолютно незвичайна», — сказав він.

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

Читайте також  Робимо власний імплант для електроніки

«Абсолютно вражаюче», що такого результату зміг самотужки домогтися аспірант, сказав Ааронсон.

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

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

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

Довгий шлях

Махадев виросла в Лос-Анджелесі, в сім’ї лікарів, і навчалася в Південно-Каліфорнійському університеті, де переходила від однієї області до іншої, спочатку переконаною тільки в тому, що вона сама не хоче бути лікарем. Потім вона дуже зацікавилася курсом теоретичної інформатики, який вів Леонард Эйдлман, один з творців знаменитого алгоритму шифрування RSA. Вона поступила в магістратуру в Берклі, в пояснювальній записці вказавши, що її цікавлять всі аспекти теоретичної інформатики – крім квантових обчислень.

«Це було чимось абсолютно чужим, про що я мала найменше уявлення», — сказав вона.

Але, потрапивши в Берклі, вона незабаром змінила свою думку під впливом доступних пояснень Вазирани. Він познайомив її з питанням пошуку протоколу для підтвердження квантових обчислень, і це завдання «по-справжньому змусила працювати її уява», — сказав Вазирани.

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

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

Однак фахівці з інформатики вважають (і нещодавно зробили крок у напрямку до доказу), що багато завдань, які міг би вирішити квантовий комп’ютер, позбавлені такої особливості. Інакше кажучи, класичний комп’ютер не просто не може їх вирішити, він навіть не може розпізнати, чи правильним буде запропоноване рішення. У результаті в 2004 році Деніел Готтсман – фізик-теоретик з Інституту Периметра в Ватерлоо – задав питання, чи можливо придумати який-небудь протокол, за яким квантовий комп’ютер зміг би довести не квантовим спостерігачеві, що він реально виконав те, що заявляє.

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

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

Читайте також  Створення ігор-головоломок на Puzzle Script

Приблизно в цей час Махадев зіткнулася з проблемою підтвердження. Спочатку вона намагалася видати «безумовний» результат, без припущень про те, що може і чого не може робити квантовий комп’ютер. Але, після того, як вона деякий час працювала над завданням без успіху, Вазирани запропонував замість цього можливість використання «пост-квантової» криптографії – тобто, криптографії, злом якої, на думку дослідників, знаходиться за межами можливостей навіть квантових комп’ютерів, хоча точно їм це невідомо. (Такі методи, як алгоритм RSA, що використовується для шифрування онлайн-перекладів, не відносяться до пост-квантовим — великий квантовий комп’ютер здатний зламати їх, оскільки їх безпека ґрунтується на складності розкладання великих чисел на множники).

В 2016 році, працюючи над іншим завданням, Махадев і Вазирани зробили прорив, який надалі виявиться вирішальним. Спільно з Полом Крістіано, фахівцем з інформатики з OpenAI, компанії з Сан-Франциско, вони розробили спосіб використання криптографії для того, щоб змусити квантовий комп’ютер перейти в «секретний стан» – такий стан, опис якого відомо класичного перевіряючому, але не самому квантовому комп’ютера.

Їх процедура ґрунтується на функції-«пастці» – такої, яку легко виконати, але важко звернути, якщо тільки у вас немає секретного криптографічного ключа. (В той момент дослідники ще не знали, як зробити відповідну пастку – це прийшло пізніше). Функція також повинна володіти властивістю «два в один», що означає, що для кожного набору вихідних даних є два різні набори вхідних даних. Наприклад, можна уявити собі функцію, возводящую числа в квадрат – крім числа 0, для кожного результату (наприклад, 9) є два відповідних йому вхідних числа (3 і -3).

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

Потім ви наказуєте комп’ютера виміряти підсумкове стан і повідомити результат. Вимірювання схлопывает стан до одного з можливих наборів вихідних даних, а вхідна стан схлопывается так, щоб відповідати йому, оскільки вони заплутані – наприклад, якщо ми використовуємо функцію квадрата, то, якщо вихідний стан буде дорівнює 9, тоді вхідний схлопнется до суперпозиції 3 і -3.

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

У 2017 році Махадев зрозуміла, як створювати функції-пастки, на яких заснований метод з секретним станом, використовуючи криптографію під назвою “навчання з помилками” (LWE). За допомогою таких функцій-пасток вона змогла створити квантову версію «сліпих» обчислень, за допомогою яких користувачі систем хмарних обчислень можуть приховувати свої дані, щоб комп’ютери хмари не могли їх читати, навіть якщо вони виконують обчислення з ними. Незабаром після цього Махадев, Вазирани і Крістіано об’єдналися з Видиком і Цвикой Бракерски (з інституту Вейцмана в Ізраїлі), щоб ще сильніше поліпшити якість цих функцій, і використовувати метод секретного стану для розробки гарантованого способу, яким квантовий комп’ютер здатний генерувати доказово випадкові числа.

Махадев могла б отримати ступінь вже на підставі таких результатів, але вона намірилася продовжувати роботу, поки не вирішить проблему підтвердження. «Я ніколи не думала про випуск, оскільки моєю метою був зовсім не випуск», — сказала вона.

Читайте також  Програмування — це матеріалізація ідей

Іноді невпевненість у здатності вирішити цю задачу тиснула на неї. Але, сказала вона, «я проводила час за навчанням цікавлять мене речей, тому це проведення часу не можна назвати марною тратою».

Висічено на камені

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

Складність буде в тому, як зрозуміла Махадев, щоб змусити квантовий комп’ютер пообіцяти зробити якийсь певний вимір до того, як він дізнається, про який саме вимірі його попросить перевіряючий – інакше комп’ютера буде дуже просто обдурити його. Саме тут і вступає в гру метод секретного стану. Протокол Махадев вимагає від квантового комп’ютера спочатку створити секретний стан, а потім заплутати його з станом, що він повинен вимірювати. І тільки потім комп’ютер дізнається, який вимір необхідно проводити.

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

«Це настільки чудова ідея! – писав Відік. – Вона вражає мене кожен раз, коли Урмила її пояснює».

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

У будь-якому випадку, впевненість протоколу LWE робить роботу Махадев виграшною в будь-якому випадку, писав Відік. Єдиний варіант, при якому квантовий комп’ютер може обдурити протокол – якщо хтось із світу квантових обчислень придумає, як зламати LWE, що саме по собі стане визначним досягненням.

Протокол Махадев навряд чи буде втілений на реальному квантовому комп’ютері в осяжному майбутньому. Поки що йому потрібно занадто велика з практичної точки зору обчислювальна потужність. Але в майбутньому це може змінитися, коли квантові комп’ютери будуть рости, і дослідники раціоналізують цей протокол.

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

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

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

«Мені здається, що за нею послідує безліч похідних ідей, — сказав Ааронсон. – Я з нетерпінням чекаю нових результатів від Урміли».

Степан Лютий

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

Вам також сподобається...

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

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