Новый квантовый алгоритм повышает уровень эффективности решений

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

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

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

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

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

«Это означает использование меньшего количества квантовых ресурсов и квантовых схем без ущерба для производительности», — сказал г-н Виджендран, который проводил свои исследования в Австралийском национальном университете совместно с Центром передового опыта в области квантовых вычислений и коммуникационных технологий ARC (CQC2T) и A*STAR в Сингапур.

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

«Для такого типа проблем найти оптимальное решение зачастую непрактично», — сказал г-н Виджендран.

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

Самый известный алгоритм аппроксимации задачи MaxCut — это классический алгоритм Гоеманса-Вильямсона 1994 года.

В 2014 году исследователи из Массачусетского технологического института впервые обратились к квантовым вычислениям. Их подход был известен как алгоритм квантовой аппроксимационной оптимизации (QAOA) и начинается с квантового состояния, которое является первоначальным предположением, и направлен на его развитие до состояния, которое решает данную проблему, путем корректировки параметров, управляющих эволюцией. Продолжающиеся исследования эффективности алгоритма квантовой аппроксимированной оптимизации показывают, что теоретически при наличии достаточно глубоких квантовых схем алгоритм квантовой аппроксимационной оптимизации потенциально может превзойти современный алгоритм Гоманса-Вильямсона.

Но пока невозможно проверить потенциал, потому что аппаратное обеспечение квантовых вычислений недостаточно хорошо, сказал г-н Виджендран.

«На практике оборудование шумит, а это значит, что при большом количестве последовательных операций качество решения ухудшается».

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

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

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

Г-н Виджендран сотрудничал с аспиранткой АНУ Аритрой Дас и доктором Даксом Энчан Кохом, ученым из A*STAR, под руководством доктора Саеда Асада и профессора Пинг Куй Лама, чтобы применить этот подход к обеспечению качества в сельском хозяйстве.

Чтобы оценить эффективность алгоритма, команда вывела аналитические выражения для измерения производительности и смоделировала их классическим способом.

Их алгоритм, получивший название eXpressive QAOA (XQAOA), превзошел стандартный алгоритм QAOA, его варианты и современный классический алгоритм Гоеманса-Вильямсона в задаче MaxCut для графов со 128 и 256 вершинами (что эквивалентно 128 и 256 кубитам) – даже при использовании минимум операций.

В отличие от QAOA, XQAOA не страдала ловушками, что значительно облегчило эволюцию квантового состояния.

Самым удивительным, как объяснил г-н Виджендран, было то, что они обнаружили, что их алгоритм сходится к классическому решению.

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

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

«Существует заблуждение, что квантовые компьютеры предлагают всеобъемлющие, универсальные решения. Однако классические решения оказались более эффективными в некоторых задачах.

«Выбор количественных методов для немедленного решения проблем без предварительного рассмотрения того, превосходит ли количественный подход классические методы, является ошибкой.

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

Хотя их текущие исследования показывают, что набор рассматриваемых ими проблем не имеет количественного преимущества, г-н Виджендран сохраняет оптимизм.

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

Эта статья была впервые опубликована Австралийский национальный университет физики.