Вчені NTT кажуть, що у них є новий спосіб перевірити квантову перевагу

Саннівейл, Каліфорнія – 26 жовтня 2022 р. – NTT Research оголосила, що вчений із Лабораторія криптографії та інформаційної безпеки (CIS). і колега з в Лабораторії соціальної інформатики NTT (SIL) написали новаторську статтю про квантову перевагу. Стаття була обрана для презентації на щорічному симпозіумі IEEE з основ комп’ютерних наук (FOCS), який відбудеться 31 жовтня – листопада. 3 в Денвері.

Співавтори статті під назвою «Перевірена квантова перевага без структури”, д-р Такаші Ямакава, видатний дослідник NTT SIL і д-р Марк Жандрі, старший науковий співробітник NTT Research Лабораторія СНД. Робота була виконана частково в Прінстонському університеті, де д-р Ямакава був запрошеним дослідником, а д-р Жандрі також працює асистентом професора інформатики. 

Тема квантової переваги (або квантового прискорення) стосується типів проблем, які квантові комп’ютери можуть вирішити швидше, ніж класичні або неквантові комп’ютери, і наскільки вони швидші. Проблеми, про які йде мова, зазвичай описуються як недетермінований клас поліноміального часу (NP). Наскільки перевага може сильно відрізнятися. Квантовий комп’ютер може вирішити конкретну проблему за хвилину чи секунду, що займає у класичного комп’ютера тиждень або, можливо, незбагненно експоненціальний час. У цій статті автори вирішують проблему перевірки цієї переваги, і роблять це ефективно. На сьогоднішній день демонстрація квантової переваги включала значну «структуру» або зворотну комунікацію між двома або більше сторонами. Прорив статті Ямакави та Жандрі полягає в демонстрації складної проблеми NP, де верифікація можлива без структури.

«Це перший випадок, коли ми спостерігаємо експоненційне квантове прискорення для проблеми пошуку NP, для якої потрібен лише випадковий оракул», — сказав професор комп’ютерних наук Техаського університету в Остіні д-р Скотт Ааронсон, який прокоментував ранню версію статті під час семінару 13 червня 2022 року в Інституті теорії обчислювальної техніки Саймонса. Вимагаючи лише випадкового оракула, тобто теоретичної чорної скриньки, яка генерує випадкові відповіді на кожен запит, Ямакава та Жандрі побудували свою проблему на основі неструктурованих обчислювальних припущень. Таким чином, їхня проблема тісніше пов’язана з односторонніми функціями замість структурованих, таких як ті, що знаходяться в криптографії з відкритим ключем. Таке одностороннє вирівнювання сприяє ефективній перевірці.

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

Проблема пошуку NP, яку розробили Ямакава та Жандрі, була проблемою «два в одному», яка передбачає пошук 1) рядка з n символів, який є кодовим словом даного коду виправлення помилок, і 2) рядка з n символів, де кожен символ відображається на нуль під випадковим оракулом. Кожна проблема окремо легка. Але знайти один рядок символів, який одночасно є кодовим словом і відображає нуль, набагато важче, принаймні класично. «Якщо ви квантовий, ви можете розв’язати це за поліноміальний час, — сказав д-р Жандрі, — але якщо ви класичний, принаймні якщо ви перебуваєте в цій моделі чорного ящика, вам потрібен експоненціальний час». З іншого боку, враховуючи потенційне рішення, його легко перевірити, перевіривши, що воно окремо вирішує кожну з двох проблем. Зверніть увагу, що, як і належить документу для FOCS, ця робота є базовою або фундаментальною. Як було зазначено у виступі доктора Ааронсона в Інституті Саймонса (обговорювалося в цьому дослідженні NTT стаття в блозі), аргумент Ямакави-Жандрі відноситься до класу прискорень, які можна легко перевірити математично, але не продемонструвати на практиці фактичним квантовим комп’ютером найближчим часом. Однак, окрім новаторської верифікаційної схеми, документ також вказує на щось нове, що стосується ступеня квантового прискорення.

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

Конференція FOCS, спонсорована Технічним комітетом з математичних основ обчислювальної техніки (TCMF) IEEE Computer Society, є провідною конференцією в галузі теоретичної інформатики. У конкурсі на участь у FOCS 2022, 63-му такому щорічному зібранні, квантові обчислення були вказані як одна з 17 загальних сфер інтересів. Презентація статті Ямакави-Жандрі запланована на 31 жовтня 2022 року о 10:15 ранку за київським часом. Щоб дізнатися більше про цю подію та зареєструватися на неї, відвідайте FOCS 2022 .