Иногда компьютеру легко спрогнозировать будущее. Простые явления, например, когда сок стекает по стволу дерева, прямолинейны и фиксируются в нескольких строках кода при помощи линейных дифференциальных уравнений. Но в нелинейных системах взаимодействия могут влиять сами на себя: когда воздушные потоки протекают по крыльям реактивного самолёта, поток воздуха изменяет молекулярные взаимодействия, которые, в свою очередь, изменяют воздушный поток, и так далее. Эта петля обратной связи порождает хаос, где небольшие изменения в начальных условиях позже приводят к крайне изменчивому поведению, что делает прогнозы практически невозможными, каким бы мощным ни был компьютер.
«Это часть причин того, почему трудно сделать прогноз погоды или разобраться со сложным потоком жидкости,— рассказывает Эндрю Чайлдс, исследователь квантовой информации из Университета Мэриленда, — есть трудные вычислительные задачи, которые вы могли бы решить, если бы смогли разобраться в этой нелинейной динамике».
Возможно, скоро учёные разрешат этот вопрос. В отдельных исследованиях, опубликованных в ноябре 2020 года, две команды (одна во главе с Чилдсом, другая на базе Массачусетского технологического института) описали в своих работах мощные инструменты, которые позволят квантовым компьютерам точнее моделировать нелинейную динамику.
Чтобы выполнять вычисления эффективнее их классических аналогов, квантовые компьютеры используют преимущества квантовых явлений. Они уже решают сложные линейные дифференциальные уравнения экспоненциально быстрее классических машин. Исследователи давно надеялись, что с помощью умных квантовых алгоритмов смогут приручить и нелинейные задачи.
Новые подходы маскируют нелинейность под более перевариваемый набор линейных приближений, хотя сами эти методы значительно различаются. Теперь у исследователей есть два отдельных подхода к нелинейным проблемам с помощью квантовых компьютеров.
«В этих двух работах интересно то, что они нашли такой режим, при котором, с учётом некоторых предположений, есть эффективный алгоритм, — поделилась Мария Киферова, исследователь в области квантовых вычислений в Сиднейском технологическом университете, которая не связана с этими исследованиями, — это действительно захватывающе, [оба исследования] применяют очень хорошие методы».
Более десяти лет исследователи квантовой информации пытаются применять линейные уравнения как ключ к решению нелинейных дифференциальных уравнений. Один прорыв произошел в 2010 году, когда Доминик Берри, в настоящее время работающий в Университете Маккуори (Сидней), построил первый алгоритм решения линейных дифференциальных уравнений экспоненциально быстрее на квантовых, а не на классических компьютерах. Вскоре Берри переключил внимание и на нелинейные дифференциальные уравнения.
«Мы уже делали кое-какую работу над этим раньше, — рассказывает Берри, —но это было очень, очень неэффективно».
Эндрю Чайлдс из Университета Мэриленда возглавил работу, в которой учёные пытаются позволить квантовым компьютерам точнее моделировать нелинейную динамику. Алгоритм его команды превратил хаотичные системы в массив более понятных линейных уравнений с помощью метода линеаризации Карлемана. Джон Т. Консоли / Университет Мэриленда
Проблема в том, что физика, лежащая в основе квантовых компьютеров, сама по себе является принципиально линейной. «Это как учить машину летать», — сказал Бобак Киани, соавтор исследования MIT.
Итак, фокус в том, чтобы найти способ математически преобразовать нелинейную систему в линейную. «Мы хотим иметь какую-то линейную систему, потому что для линейной системы у нас есть инструментарий»", — заявил Чайлдс. Группы учёных сделали это двумя разными способами.
Команда Чайлдса применила линеаризацию Карлемана, вышедший из моды метод 1930-х годов, чтобы преобразовать нелинейные задачи в массив линейных уравнений.
К сожалению, список этих уравнений бесконечен. Исследователи должны выяснить, где можно сократить его, чтобы получить достаточное приближение. «Остановиться ли мне на уравнении под номером 10? Номер 20?» — спрашивает Нуно Лурэйро, который занимается физикой плазмы в Массачусетском технологическом институте (MIT) и является соавтором исследования Мэриленда. Команда доказала, что в определённом диапазоне нелинейности их метод может ограничить бесконечный список и решить уравнения.
В работе, подготовленной под руководством Массачусетского технологического института, применялся иной подход. Любую нелинейную проблему моделировали как конденсат Бозе-Эйнштейна. Это состояние материи, когда взаимодействия внутри ультрахолодной группы частиц приводят к тому, что каждая отдельная частица ведёт себя одинаково с другими. Все частицы взаимосвязаны, поэтому поведение каждой частицы влияет на остальные, возвращаясь к этой частице в петле, которая характеризуется нелинейностью.
Алгоритм MIT имитирует это нелинейное явление на квантовом компьютере, используя математику Бозе-Эйнштейна для соединения нелинейности и линейности. Таким образом, представляя псевдоконденсат Бозе-Эйнштейна, созданный для каждой нелинейной задачи, этот алгоритм выводит полезное линейное приближение. «Дайте мне ваше любимое нелинейное дифференциальное уравнение, тогда я построю вам конденсат Бозе-Эйнштейна, который будет его моделировать, — говорит Тобиас Осборн, учёный в области квантовой информации из Университета Лейбница в Ганновере, который не занимался ни тем, ни другим исследованием — Это идея, которую я по-настоящему полюбил».
Алгоритм, разработанный под руководством MIT, моделирует любую нелинейную проблему как конденсат Бозе-Эйнштейна, экзотическое состояние материи, где все взаимосвязанные частицы ведут себя одинаково. NIST
Берри считает, что обе работы важны по-своему (он тоже не участвовал в них). «Но, в конечном счёте, их важность показывает, что можно воспользоваться [этими методами], чтобы получить нелинейное поведение», — сказал он.
Несмотря на свою важность, эти шаги — одни из первых в области разрешения нелинейных систем. Другие исследователи, скорее всего, будут анализировать и дорабатывать каждый метод — ещё до того, как аппаратное обеспечение, необходимое для их реализации, станет реальностью. «С этими алгоритмами мы действительно смотрим в будущее», говорит Киферова. Чтобы минимизировать ошибки, шум, и применять их в решения практических нелинейных задач, требуются квантовые компьютеры с тысячами кубитов, это намного больше того, что возможно сегодня.
И оба алгоритма реалистично справляются с нелинейными проблемами. Исследование Мэриленда количественно определяет, насколько точно подход может справиться с нелинейностью при помощи нового параметра, R, то есть отношения нелинейности проблемы к её линейности — её склонности к хаосу против удерживающего систему порядка.
«Исследование Чайлдса математически строго. Он даёт очень чёткие указания на то, когда подход сработает, а когда нет, — сказал Осборн. — Я думаю, это очень, очень интересно. Это основной вклад работы в науку».
По словам Киани, исследование, проведённое под руководством MIT, не доказывает, что есть какие-то теоремы, которые ограничивают алгоритм. Но команда планирует узнать больше об ограничениях алгоритма, проведя небольшие тесты на квантовом компьютере, прежде чем переходить к более сложным проблемам.
Самым существенным предостережением для обеих методик является то, что квантовые решения принципиально отличаются от классических. Квантовые состояния соответствуют вероятностям, а не абсолютным значениям, поэтому вместо того чтобы визуализировать поток воздуха вокруг каждого сегмента фюзеляжа реактивного самолёта, например, вы извлекаете средние скорости или обнаруживаете карманы застойного воздуха. «Тот факт, что результат квантово-механический, означает, что после нужно еще многое сделать, чтобы проанализировать состояние», утверждает Киани.
Жизненно важно не переусердствовать с тем, что могут сделать квантовые компьютеры, сказал Осборн. Но в ближайшие пять-десять лет исследователи обязательно проверят многие успешные квантовые алгоритмы, подобные этим, на практических задачах. «Мы попробуем всё, что угодно, — говорит он. — И если мы будем думать об ограничениях, это может ограничить наш творческий потенциал».
«Это часть причин того, почему трудно сделать прогноз погоды или разобраться со сложным потоком жидкости,— рассказывает Эндрю Чайлдс, исследователь квантовой информации из Университета Мэриленда, — есть трудные вычислительные задачи, которые вы могли бы решить, если бы смогли разобраться в этой нелинейной динамике».
Возможно, скоро учёные разрешат этот вопрос. В отдельных исследованиях, опубликованных в ноябре 2020 года, две команды (одна во главе с Чилдсом, другая на базе Массачусетского технологического института) описали в своих работах мощные инструменты, которые позволят квантовым компьютерам точнее моделировать нелинейную динамику.
Чтобы выполнять вычисления эффективнее их классических аналогов, квантовые компьютеры используют преимущества квантовых явлений. Они уже решают сложные линейные дифференциальные уравнения экспоненциально быстрее классических машин. Исследователи давно надеялись, что с помощью умных квантовых алгоритмов смогут приручить и нелинейные задачи.
Новые подходы маскируют нелинейность под более перевариваемый набор линейных приближений, хотя сами эти методы значительно различаются. Теперь у исследователей есть два отдельных подхода к нелинейным проблемам с помощью квантовых компьютеров.
«В этих двух работах интересно то, что они нашли такой режим, при котором, с учётом некоторых предположений, есть эффективный алгоритм, — поделилась Мария Киферова, исследователь в области квантовых вычислений в Сиднейском технологическом университете, которая не связана с этими исследованиями, — это действительно захватывающе, [оба исследования] применяют очень хорошие методы».
Цена хаоса
Более десяти лет исследователи квантовой информации пытаются применять линейные уравнения как ключ к решению нелинейных дифференциальных уравнений. Один прорыв произошел в 2010 году, когда Доминик Берри, в настоящее время работающий в Университете Маккуори (Сидней), построил первый алгоритм решения линейных дифференциальных уравнений экспоненциально быстрее на квантовых, а не на классических компьютерах. Вскоре Берри переключил внимание и на нелинейные дифференциальные уравнения.
«Мы уже делали кое-какую работу над этим раньше, — рассказывает Берри, —но это было очень, очень неэффективно».
Эндрю Чайлдс из Университета Мэриленда возглавил работу, в которой учёные пытаются позволить квантовым компьютерам точнее моделировать нелинейную динамику. Алгоритм его команды превратил хаотичные системы в массив более понятных линейных уравнений с помощью метода линеаризации Карлемана. Джон Т. Консоли / Университет Мэриленда
Проблема в том, что физика, лежащая в основе квантовых компьютеров, сама по себе является принципиально линейной. «Это как учить машину летать», — сказал Бобак Киани, соавтор исследования MIT.
Итак, фокус в том, чтобы найти способ математически преобразовать нелинейную систему в линейную. «Мы хотим иметь какую-то линейную систему, потому что для линейной системы у нас есть инструментарий»", — заявил Чайлдс. Группы учёных сделали это двумя разными способами.
Команда Чайлдса применила линеаризацию Карлемана, вышедший из моды метод 1930-х годов, чтобы преобразовать нелинейные задачи в массив линейных уравнений.
К сожалению, список этих уравнений бесконечен. Исследователи должны выяснить, где можно сократить его, чтобы получить достаточное приближение. «Остановиться ли мне на уравнении под номером 10? Номер 20?» — спрашивает Нуно Лурэйро, который занимается физикой плазмы в Массачусетском технологическом институте (MIT) и является соавтором исследования Мэриленда. Команда доказала, что в определённом диапазоне нелинейности их метод может ограничить бесконечный список и решить уравнения.
В работе, подготовленной под руководством Массачусетского технологического института, применялся иной подход. Любую нелинейную проблему моделировали как конденсат Бозе-Эйнштейна. Это состояние материи, когда взаимодействия внутри ультрахолодной группы частиц приводят к тому, что каждая отдельная частица ведёт себя одинаково с другими. Все частицы взаимосвязаны, поэтому поведение каждой частицы влияет на остальные, возвращаясь к этой частице в петле, которая характеризуется нелинейностью.
Алгоритм MIT имитирует это нелинейное явление на квантовом компьютере, используя математику Бозе-Эйнштейна для соединения нелинейности и линейности. Таким образом, представляя псевдоконденсат Бозе-Эйнштейна, созданный для каждой нелинейной задачи, этот алгоритм выводит полезное линейное приближение. «Дайте мне ваше любимое нелинейное дифференциальное уравнение, тогда я построю вам конденсат Бозе-Эйнштейна, который будет его моделировать, — говорит Тобиас Осборн, учёный в области квантовой информации из Университета Лейбница в Ганновере, который не занимался ни тем, ни другим исследованием — Это идея, которую я по-настоящему полюбил».
Алгоритм, разработанный под руководством MIT, моделирует любую нелинейную проблему как конденсат Бозе-Эйнштейна, экзотическое состояние материи, где все взаимосвязанные частицы ведут себя одинаково. NIST
Берри считает, что обе работы важны по-своему (он тоже не участвовал в них). «Но, в конечном счёте, их важность показывает, что можно воспользоваться [этими методами], чтобы получить нелинейное поведение», — сказал он.
Об ограничениях
Несмотря на свою важность, эти шаги — одни из первых в области разрешения нелинейных систем. Другие исследователи, скорее всего, будут анализировать и дорабатывать каждый метод — ещё до того, как аппаратное обеспечение, необходимое для их реализации, станет реальностью. «С этими алгоритмами мы действительно смотрим в будущее», говорит Киферова. Чтобы минимизировать ошибки, шум, и применять их в решения практических нелинейных задач, требуются квантовые компьютеры с тысячами кубитов, это намного больше того, что возможно сегодня.
И оба алгоритма реалистично справляются с нелинейными проблемами. Исследование Мэриленда количественно определяет, насколько точно подход может справиться с нелинейностью при помощи нового параметра, R, то есть отношения нелинейности проблемы к её линейности — её склонности к хаосу против удерживающего систему порядка.
«Исследование Чайлдса математически строго. Он даёт очень чёткие указания на то, когда подход сработает, а когда нет, — сказал Осборн. — Я думаю, это очень, очень интересно. Это основной вклад работы в науку».
По словам Киани, исследование, проведённое под руководством MIT, не доказывает, что есть какие-то теоремы, которые ограничивают алгоритм. Но команда планирует узнать больше об ограничениях алгоритма, проведя небольшие тесты на квантовом компьютере, прежде чем переходить к более сложным проблемам.
Самым существенным предостережением для обеих методик является то, что квантовые решения принципиально отличаются от классических. Квантовые состояния соответствуют вероятностям, а не абсолютным значениям, поэтому вместо того чтобы визуализировать поток воздуха вокруг каждого сегмента фюзеляжа реактивного самолёта, например, вы извлекаете средние скорости или обнаруживаете карманы застойного воздуха. «Тот факт, что результат квантово-механический, означает, что после нужно еще многое сделать, чтобы проанализировать состояние», утверждает Киани.
Жизненно важно не переусердствовать с тем, что могут сделать квантовые компьютеры, сказал Осборн. Но в ближайшие пять-десять лет исследователи обязательно проверят многие успешные квантовые алгоритмы, подобные этим, на практических задачах. «Мы попробуем всё, что угодно, — говорит он. — И если мы будем думать об ограничениях, это может ограничить наш творческий потенциал».
- Профессия Data Scientist
- Профессия Data Analyst
- Курс «Математика и Machine Learning для Data Science»
- Курс «Алгоритмы и структуры данных»
Другие профессии и курсы
ПРОФЕССИИ
КУРСЫ
- Профессия Frontend-разработчик
- Профессия Веб-разработчик
- Профессия Этичный хакер
- Профессия C++ разработчик
- Профессия Java-разработчик
- Профессия Разработчик игр на Unity
- Профессия iOS-разработчик с нуля
- Профессия Android-разработчик с нуля
КУРСЫ
- Курс по JavaScript
- Курс по Machine Learning
- Курс «Python для веб-разработки»
- Курс по аналитике данных
- Курс по DevOps
anonymous
Интересно, можно ли идею алгоритма адаптировать для решения многомерных квадратичных уравнений на конечным полем. Возможно это позволило бы построить новую атаку на соответствующие криптосистемы, такие как Rainbow (финалист конкурса nist по постквантовой криптографии)