Новая теоретическая работа от Google Quantum AI показывает, что крупномасштабные квантовые компьютеры могут решать определенные задачи оптимизации, которые неразрешимы для обычных классических компьютеров.
Быстрые ссылки
- Бумага
- Делиться
От разработки более эффективных авиамаршрутов до организации клинических испытаний — задачи оптимизации встречаются повсюду. Однако даже самые мощные суперкомпьютеры с трудом находят оптимальное решение для многих реальных задач. Это привело к возникновению важного вопроса, который обсуждается уже несколько десятилетий в области квантовых вычислений: смогут ли квантовые машины успешно решать задачи оптимизации, с которыми не справляются классические? Это оказалось очень сложным математическим вопросом, который до сих пор остается в значительной степени открытым. По мере быстрого развития возможностей квантового оборудования такие теоретические проблемы, как определение возможных коммерческих и научных вариантов использования крупномасштабных квантовых компьютеров с коррекцией ошибок, становятся все более актуальными.
В недавней статье в журнале Nature исследователи из Google Quantum AI и их коллеги из Стэнфорда, Массачусетского технологического института и Калифорнийского технологического института проливают новый свет на этот вопрос. Мы представляем эффективный квантовый алгоритм — называемый декодированной квантовой интерферометрией (DQI) — который использует волновую природу квантовой механики для создания интерференционных картин, сходящихся к почти оптимальным решениям, которые невероятно сложно найти с помощью классических компьютеров.
Квантовая связь между оптимизацией и декодированием
Однако есть один нюанс. Для построения необходимых интерференционных картин необходимо решить другую сложную вычислительную задачу, называемую декодированием. В задаче декодирования дается решетка и точка в пространстве, и нужно найти ближайший к этой точке элемент решетки. Например, углы клеток на шахматной доске образуют двумерную решетку. После того, как песчинка будет брошена в случайное место на шахматной доске, задача декодирования будет заключаться в поиске ближайшего угла. Хотя эта задача проста для двумерной квадратной решетки, она может стать очень сложной на некоторых решетках, занимающих сотни или тысячи измерений.
К счастью, проблемы декодирования были чрезвычайно хорошо изучены за последние несколько десятилетий, главным образом благодаря применению в исправлении ошибок, возникающих при хранении или передаче данных. Было разработано множество сложных и мощных алгоритмов для решения задач декодирования для различных специально структурированных решеток. Мы обнаружили, что для определенных типов задач оптимизации соответствующие задачи декодирования имеют подходящую структуру для решения некоторыми из этих мощных алгоритмов декодирования. Однако только благодаря возможностям квантовых вычислений эти алгоритмы декодирования могут быть использованы также для решения задач оптимизации. Сочетая квантовую интерференцию DQI с этими сложными алгоритмами декодирования, достаточно большой квантовый компьютер мог бы найти приблизительные решения этих задач оптимизации — решения, которые, по-видимому, недоступны для любого известного классического метода.
Это математическое открытие квантового алгоритма, обеспечивающего ускорение оптимизации, улучшает наше понимание будущих вариантов использования квантовых компьютеров. Когда аппаратное обеспечение для квантовых вычислений станет достаточно совершенным, исследователи смогут использовать алгоритм DQI для решения сложных классических задач оптимизации.
Наглядное представление преобразования задачи оптимизации на сложном ландшафте целевой функции в задачу декодирования для периодической решетки.
Очевидная квантовая победа: оптимальное пересечение полиномов.
В данной работе наш лучший результат получен для задачи, которую мы называем оптимальным пересечением полиномов (ОПП). В задаче ОПП дается список целевых точек, и необходимо пересечь как можно больше из них, подбирая коэффициенты полинома, степень которого меньше числа точек. Это распространенная задача в науке о данных, известная как полиномиальная регрессия. Варианты этой задачи возникали в контексте цифровой коррекции ошибок, а также криптографии. Следовательно, для ее решения в некоторых частных случаях были разработаны сложные алгоритмы, но в других случаях задача остается безнадежно сложной для решения с использованием известных алгоритмов на обычных классических компьютерах.
Используя DQI, квантовый компьютер мог бы преобразовать это в задачу декодирования кодов Рида-Соломона (широко используемое семейство кодов, встречающихся на DVD и QR-кодах). Для декодирования кодов Рида-Соломона были разработаны очень хорошие алгоритмы, и в результате квантовые компьютеры, использующие DQI, могут находить более точные приближенные оптимумы для задачи OPI, чем это возможно с помощью известных алгоритмов на классических компьютерах. Например, наш анализ показывает, что некоторые примеры задачи OPI могут быть решены квантовыми компьютерами, используя всего несколько миллионов элементарных квантовых логических операций, тогда как для решения на обычном классическом компьютере с использованием наиболее эффективного известного классического алгоритма потребовалось бы более 10²³ (сто секстиллионов) элементарных операций.
Иллюстрация задачи OPI: необходимо найти многочлен низкой степени, пересекающий как можно больше целевых множеств. Многочлены f и g , показанные здесь, несмотря на свои существенные различия, пересекают три целевых множества, таким образом, получая одинаковое значение целевой функции. Это явление, когда удаленные решения достигают одинаковых значений целевой функции, является одной из причин, почему эту задачу так сложно решить с помощью обычных компьютеров.
Откуда берется квантовое преимущество?
Если посмотреть на ситуацию со стороны, то можно задаться вопросом, почему вообще преобразование задач оптимизации в задачи декодирования должно быть выгодным? Более глубокое понимание этого вопроса позволит развить интуицию, которая поможет в поиске дополнительных задач оптимизации, в решении которых квантовые компьютеры могут принести пользу.
Как исходные задачи оптимизации, так и задачи декодирования, в которые мы их преобразуем, относятся к NP-трудным задачам. Это означает, что эффективно найти точные решения для всех экземпляров этих задач невозможно, даже с помощью квантовых компьютеров. Используя квантовые эффекты, DQI преобразует одну сложную задачу в другую сложную задачу. Как это достигается? Ключевой момент заключается в том, что NP-трудность отражает сложность самых сложных экземпляров данной задачи. Если экземпляры задачи ограничены наличием некоторой дополнительной структуры, это может упростить их . Перспектива DQI состоит в том, что определенные виды структуры могут значительно упростить задачу декодирования, не упрощая при этом задачу оптимизации, решаемую с помощью обычных компьютеров.
В задаче OPI возникающая решетка имеет алгебраическую структуру; компоненты базисных векторов, вместо того чтобы быть произвольными, получаются путем последовательного возведения числа в более высокие степени. Эта алгебраическая структура отражена как в исходной задаче оптимизации (OPI), так и в задаче декодирования, в которую ее могут преобразовать квантовые компьютеры (декодирование Рида-Соломона). Эта структура значительно упрощает задачу декодирования, но, насколько нам известно, не упрощает задачу оптимизации для обычных компьютеров. В этих обстоятельствах возможность преобразования задачи оптимизации в задачу декодирования с использованием возможностей квантовых вычислений дает преимущество.
Случайные задачи разреженной оптимизации: заманчивая задача.
В данной работе мы также рассматриваем более общие решетки, не имеющие алгебраической структуры, но базисные векторы которых разрежены, то есть состоят в основном из нулей. Соответствующая задача оптимизации называется max-k-XORSAT и иллюстрируется ниже. Разреженность решетки отражается в том, что каждое из ограничений включает лишь несколько переменных (не более k ). В max-k-XORSAT ограничений больше, чем переменных, и невозможно удовлетворить все из них. Вместо этого необходимо найти решение, удовлетворяющее как можно большему числу ограничений. Хотя это может звучать абстрактно, задача max-k-XORSAT обычно используется в качестве тестовой площадки для новых алгоритмов оптимизации и включает в себя ряд других известных задач оптимизации в качестве частных случаев, таких как max-cut и QUBO.
Пример задачи max-k-XORSAT с k = 2, имеющей 4 переменные и 5 ограничений. Присвоив каждой из переменных A, B, C, D значение 0 или 1, сколько ограничений можно удовлетворить?
DQI может преобразовать задачу max-k-XORSAT в задачу декодирования для кодов, определяемых разреженными матрицами. Такие коды называются кодами с низкой плотностью проверок четности (LDPC). В 1960-х годах было обнаружено, что разреженность значительно упрощает задачу декодирования. Однако разреженность исходной задачи max-k-XORSAT также упрощает ее решение на обычных компьютерах с использованием алгоритма, называемого имитацией отжига. Таким образом, трудно найти задачи max-k-XORSAT с подходящей разреженностью, которая бы обеспечивала декодеру большую эффективность, чем алгоритм имитации отжига, с которым мы сравниваем задачу. В статье мы приводим пример задачи, где разреженность подобрана таким образом, что DQI, по-видимому, имеет преимущество в скорости по сравнению с имитацией отжига. Тем не менее, нам удалось эффективно решить эту задачу на обычном компьютере, используя специализированный алгоритм, адаптированный к нашему примеру. Таким образом, в настоящее время, в отличие от OPI, у нас нет примера задачи max-k-XORSAT, которую можно было бы решить с помощью DQI, но которую нельзя было бы эффективно решить с помощью какого-либо известного алгоритма, работающего на обычных компьютерах.
Поскольку задачи разреженной оптимизации имеют широкое практическое применение, мы продолжаем искать способы, с помощью которых DQI может обеспечить квантовое преимущество в задачах разреженной оптимизации. В частности, DQI стимулировал новые направления исследований как классических, так и квантовых алгоритмов для декодирования LDPC-кодов.
Перспективы
Алгоритм DQI предоставляет мощный новый инструментарий для разработки алгоритмов квантовой оптимизации. Такой подход, заключающийся в преобразовании задач оптимизации в задачи декодирования, предлагает новый способ решения одного из самых давних вопросов в этой области. Мы с нетерпением ждем, что создадут исследователи как в Google, так и в более широком сообществе с помощью этих инструментов.
Источник: research.google
