Ученые NTT говорят, что у них есть новый способ проверить квантовое преимущество

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

Соавторы статьи под названием «Поддающееся проверке квантовое преимущество без структуры», — доктор Такаси Ямакава, выдающийся исследователь NTT SIL и доктор Марк Жандри, старший научный сотрудник Исследования НТТ Лаборатория СНГ. Работа была частично выполнена в Принстонском университете, где доктор Ямакава был приглашенным научным сотрудником, а доктор Жандри также работает доцентом кафедры информатики. 

Тема квантового преимущества (или квантового ускорения) связана с типами задач, которые квантовые компьютеры могут решать быстрее, чем классические или неквантовые компьютеры, и с тем, насколько они быстрее. Рассматриваемые проблемы обычно описываются как класс недетерминированного полиномиального времени (NP). Насколько преимущество может варьироваться в огромной степени. Квантовый компьютер может решить конкретную задачу за минуту или секунду, на что у классического компьютера уходит неделя или, возможно, непостижимо экспоненциальное количество времени. В этой статье авторы решают задачу подтверждения этого превосходства и делают это эффективно. На сегодняшний день демонстрация квантового преимущества предполагает значительную «структуру» или двустороннюю коммуникацию между двумя или более сторонами. Прорыв в статье Ямакавы и Чандри заключается в демонстрации NP-сложной проблемы, где верификация возможна без структуры.

«Это первый раз, когда мы наблюдаем экспоненциальное квантовое ускорение для задачи поиска NP, для которой требуется только случайный оракул», — сказал профессор компьютерных наук Техасского университета в Остине доктор Скотт Ааронсон, который прокомментировал раннюю версию. статьи во время семинара 13 июня 2022 года в Институте теории вычислений Саймонса. Требуя только случайного оракула, то есть теоретического черного ящика, который генерирует случайные ответы на каждый запрос, Ямакава и Чандри построили свою проблему на неструктурированных вычислительных предположениях. Таким образом, их проблема более тесно связана с односторонними функциями, а не со структурированными, такими как те, которые встречаются в криптографии с открытым ключом. Такое одностороннее согласование способствует эффективной проверке.

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

Задача поиска NP, которую разработали Ямакава и Чандри, представляла собой задачу «два в одном», которая влечет за собой поиск 1) строки из n символов, которая является кодовым словом заданного кода исправления ошибок, и 2) строки из n символов, в которой каждый символ отображается в ноль при случайном оракуле. Каждая задача по отдельности решается легко. Но найти одну строку символов, которая одновременно является кодовым словом и отображается в ноль, гораздо сложнее, по крайней мере, в классическом смысле. «Если вы квантовый человек, вы можете решить эту задачу за полиномиальное время, — сказал доктор Жандри, — но если вы придерживаетесь классической модели, по крайней мере, если вы находитесь в этой модели черного ящика, вам нужно экспоненциальное время». С другой стороны, имея потенциальное решение, его легко проверить, проверив, что оно решает каждую из двух задач по отдельности. Обратите внимание, что, как и положено статье для FOCS, эта работа является базовой или основополагающей. Как указано в докладе доктора Ааронсона в Институте Саймонса (обсуждаемом в этом исследовании NTT Research) статьи блога), аргумент Ямакавы-Жандри относится к классу ускорений, которые можно легко проверить математически, но в ближайшее время невозможно продемонстрировать на практике с помощью реального квантового компьютера. Однако помимо новаторской схемы проверки в документе также указывается на что-то новое, касающееся степени квантового ускорения.

«До нашей работы у нас были примеры квантового преимущества для задач NP, таких как факторинг или, в случае с черным ящиком, нахождение периода. Но оказывается, что квантовый алгоритм, лежащий в основе всех этих примеров, по сути был поиском периода, хотя показать, как применять поиск периода к этим примерам, часто было нетривиально», — сказал доктор Жандри. «Наша статья показывает, что есть как минимум второй случай. Вы могли бы оптимистично интерпретировать это как утверждение, что есть надежда, что квантовое преимущество более широко распространено, чем мы думали ранее».

Спонсируемая Техническим комитетом компьютерного общества IEEE по математическим основам вычислений (TCMF), FOCS является ведущей конференцией в области теоретической информатики. В объявлении о подаче докладов на FOCS 2022, 63-м подобном ежегодном собрании, квантовые вычисления были названы одной из 17 общих областей интересов. Доклад Ямакавы-Жандри планируется представить 31 октября 2022 года в 10:15 по московскому времени. Чтобы узнать больше о мероприятии и зарегистрироваться на него, посетите ФОКС 2022 Веб-сайт.