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

Две команды исследователей нашли разные способы обсчёта нелинейных систем на квантовых компьютерах посредством их маскировки под линейные

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

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

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

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

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

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

Цена хаоса

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

«Мы работали с этим раньше, — сказал Берри. – Но это был очень, очень неэффективный подход».


Эндрю Чайлдс

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

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

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

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

Команда из MIT использовала другой подход. Она моделировала нелинейные задачи как конденсат Бозе-Эйнштейна. Это особое состояние материи, в котором взаимодействия в группе чрезвычайно охлаждённых частиц заставляют все частицы вести себя одинаково. Поскольку все частицы связаны, поведение каждой из них влияет на все остальные, что вносит свой вклад в петлю обратной связи, характерную для нелинейных процессов.

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


Алгоритм команды из MIT моделировал каждую нелинейную задачу как конденсат Бозе-Эйнштейна

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

Знай свои пределы

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

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

«Математически исследование Чайлдса весьма строгое. Он чётко заявляет, когда его подход сработает, а когда – нет, — сказал Осборн. – Думаю, это очень, очень интересно. Это один из важных вкладов в тему».

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

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

Осборн говорит, что важно не преувеличивать возможности квантовых компьютеров. Однако в следующие 5-10 лет исследователи обязательно будут проверять множество подобных успешных квантовых алгоритмов. «Мы будем пробовать всякое, — сказал он. – А если всё время думать об ограничениях, это может ограничить наше творчество».

 

Источник

, ,

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

Меню