Первое экспоненциальное квантовое преимущество для задачи естественного потока

Как заяц узнал от черепахи, скорость — это еще не все. Ученые-теоретики в области компьютерной техники из Sandia National Laboratories и Boston University обнаружили, что квантовые компьютеры не имеют себе равных в решении сложных математических задач. Необычно то, что они доказали, что квантовые компьютеры не быстрее обычных компьютеров; вместо этого они используют гораздо меньше памяти.

Открытие переворачивает общепринятое мнение о том, что ценность квантового компьютера заключается в том, что он может решать определенные задачи гораздо быстрее обычного. Это также может помочь исследователям найти больше реальных применений для быстро развивающейся технологии.

«Это первое экспоненциальное квантовое преимущество для задачи естественного потока», — сказал Оджас Парекх из Sandia, член команды.

Память важна для любого компьютера. Чем больше памяти, тем большие проблемы он может решать. Для квантовых компьютеров, которые хранят информацию в кубитах, «пространство действительно имеет значение, потому что сложно построить квантовые компьютеры с большим количеством кубитов», — сказал Парех.

Команда представила свои выводы на Симпозиуме по теории вычислений, который проходил с 24 по 28 июня в Ванкувере, Британская Колумбия. Математическое доказательство доступно на arXiv сервер препринтов.

Ценность квантовых компьютеров может заключаться не только в скорости, но и в эффективности памяти

В 1994 году американский ученый Питер Шор поразил мир, когда доказал, что будущие квантовые компьютеры смогут взламывать стандартные алгоритмы шифрования пугающе быстро. Однако за прошедшие 30 лет исследователи обнаружили лишь несколько других проблем, которые эти компьютеры могут решать быстрее обычных.

Исследования, проведенные в Сандиа и Бостонском университете, теперь указывают на другую область, где возможно квантовое преимущество.

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

Переключение внимания на другие характеристики, такие как эффективность, может помочь ученым найти более практическое применение квантовым компьютерам.

«Не упускаем ли мы сейчас важные квантовые преимущества из-за того, что сосредоточены или предвзяты к определенным видам проблем?» — сказал Парекх.

Что такое естественная проблема потоковой передачи и почему это важно

Математическая задача, лежащая в основе утверждения команды, называемая максимальным направленным разрезом, имеет важное значение, поскольку исследователи называют ее естественной задачей.

«Когда мы говорим о естественной проблеме, — сказал Джон Каллаугер из Сандии, — мы имеем в виду, что это проблема, представляющая независимый интерес, — что люди уже изучали ее в классических условиях».

Парекх далее пояснил: «Задача максимального направленного разреза заключается в поиске двух групп агентов в сети с наибольшим количеством коммуникаций, направленных от одной группы к другой. Эта задача находит применение в кибербезопасности, а также в анализе и проектировании социальных сетей».

Обычно компьютерам требуется гораздо больше памяти, поскольку такого рода проблемы становятся более сложными. Но квантовым компьютерам это не нужно, обнаружила команда. Они экспоненциально более эффективны в использовании памяти, по крайней мере, когда данные поступают в потоке. Потоковые вычисления полезны, когда наборы данных слишком велики для того, чтобы поместиться в памяти компьютера, или когда данные создаются непрерывно.

Каллафэр ранее опубликовал, что квантовые компьютеры могут иметь явное, но меньшее преимущество, чем то, что он и его команда сейчас доказали. Новое открытие экспоненциального отношения имеет важное значение, поскольку преимущество должно быть очень большим, чтобы оправдать время и деньги, необходимые для создания и эксплуатации квантового компьютера.

Как и алгоритм Шора, новое открытие пока носит теоретический характер, поскольку оно еще не было продемонстрировано на компьютере.

Открытие намекает на будущую роль квантовых вычислений

Максимально направленный разрез сам по себе не очень полезен. Однако это широко известная задача оптимизации в высшей математике, которую исследовательская группа рассматривает как намек на виды практического использования квантовых компьютеров в будущем.

«В кибербезопасности, например, эффективное решение задач оптимизации может привести к более эффективному распределению ресурсов, совершенствованию стратегий реагирования на инциденты и более точной оценке рисков», — отметила Воронова.

Каллафэр добавил: «Это может указать путь к алгоритмам, которые смогут решать задачи, слишком большие для обработки любым классическим компьютером».

«Подобных алгоритмов может быть больше», — предположила Воронова.

«Никто на самом деле не имеет полной картины», — сказал Парекх.