Новые квантовые алгоритмы, совершившие прорыв в нелинейных уравнениях

Привет, Хабр. Для будущих студентов курса «Математика для Data Science» подготовили перевод интересного материала.

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


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

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

«Это одна из причин, почему нам до сих пор трудно предсказывать погоду или понимать сложный поток жидкости», — говорит Эндрю Чайлдс, исследователь квантовой информатики из Университета Мэриленда. «Существуют сложные вычислительные задачи, которые можно было бы решить, если бы разгадать эту нелинейную динамику».

Но скоро это может скоро стать возможным. В независимых исследованиях, опубликованных в ноябре, две группы — одна во главе с Чайлдсом, а другая из Массачусетского Технологического Института (MIT) — описали мощные инструменты, которые позволят квантовым компьютерам лучше моделировать нелинейную динамику.

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

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

«Что особенно интересно в этих двух работах, так это то, что они нашли режим, при котором, с некоторыми допущениями, у них есть эффективный алгоритм», — говорит Мария Киферова, исследователь квантовых вычислений из Технологического Университета Сиднея, которая не связана ни с одним из этих исследований. «Это действительно впечатляет, и это значит, что оба эти исследования используют очень хорошие методы».

Цена хаоса

Более десяти лет исследователи квантовой информатики пытались использовать линейные уравнения в качестве ключа к нелинейным дифференциальным уравнениям. Важный прорыв произошел в 2010 году, когда Доминик Берри, ныне работающий в Университете Маккуори в Сиднее, создал первый алгоритм для решения линейных дифференциальных уравнений, который на квантовых компьютерах работает экспоненциально быстрее, чем на классических. Вскоре внимание Берри переключилось на нелинейные дифференциальные уравнения.

«Мы уже пытались работать над этим раньше», — говорит Берри. «Но это было весьма малоэффективно».

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

Джон Т. Консоли / Мэрилендский университет

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

Уловка состоит в том, чтобы математически преобразовать нелинейную систему в линейную. «Мы хотим иметь какую-то линейную систему, потому что это именно то, что мы имеем в нашем наборе инструментов», — говорит Чайлдс. Группы исследователей сделали это двумя разными способами.

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

К сожалению, результирующий список уравнений бесконечен. Исследователи должны принимать решение, где его можно обрубить, чтобы получить достаточно хорошую аппроксимацию. «Следует ли мне остановиться на уравнении номер 10? Номер 20? » — говорит Нуно Лурейро, физик плазмы из Массачусетского Технологического Института и соавтор исследования в Мэриленде. Команда доказала, что для определенного диапазона нелинейностей их метод может усечь этот бесконечный список и решить уравнения.

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

Алгоритм Массачусетского Технологического Института имитирует это нелинейное явление на квантовом компьютере, используя математику Бозе-Эйнштейна для соединения нелинейности и линейности. Таким образом, работая с симуляцией псевдо-конденсата Бозе-Эйнштейна, создаваемой под нелинейную задачу, этот алгоритм выводит полезную линейную аппроксимацию. «Дайте мне ваше любимое нелинейное дифференциальное уравнение, и я построю вам конденсат Бозе-Эйнштейна, который будет его моделировать», — говорит Тобиас Осборн, специалист по квантовой информатике из Ганноверского Университета имени Лейбница, не связанный ни с одним из исследований. «Это идея, которая мне очень понравилась».

Алгоритм команды под руководством Массачусетского Технологического Института моделирует любую нелинейную проблему как конденсат Бозе-Эйнштейна, экзотическое состояние материи, в котором все взаимосвязанные частицы ведут себя одинаково.

NIST

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

Осознание своих пределов

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

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

«Исследование Чайлдса математически строго. Он дает очень четкое представление о том, когда оно сработает, а когда не сработает», — говорит Осборн. «Я думаю, это действительно очень интересно. Это фундаментальный вклад».

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

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

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


Узнать подробнее о курсе «Математика для Data Science».

Записаться на открытый вебинар на тему «Статистическая зависимость».

 

Источник

, , ,

Читайте также

Меню