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

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

Поскольку происходящее с шариками может быть представимо в виде последовательности элементарных операций и описывается довольно простыми физическими и математическими законами, то модель таких «блужданий» широко используется для создания различных компьютерных алгоритмов. Фактически, выбор расположения («топологии») гвоздиков на доске Гальтона с шариками может соответствовать вычислению той или иной задачи, что весьма похоже на биллиардную модель вычислений, предложенную Тоффоли и Фредкиным в своей известной работе «Conservative logic» в 1982 году.

При соприкосновении с каждым гвоздиком у шарика есть два варианта — отлететь с равной вероятностью вправо или влево. Точно так же каждый бит в двоичном классическом коде имеет два возможных значения — «0» или «1». Однако что случится, если мы попытаемся повторить опыт Гальтона в микромире, когда вместо шариков у нас будут квантовые частицы, а вместо гвоздиков на поверхности — крошечные, невидимые глазу препятствия?

«Если множество квантовых частиц будет блуждать по такой "доске", то больше всего их скопится как раз не в центре, а ближе к краям, — объясняет Александр Алоджанц. — Это происходит по простой причине: квантовая частица, сталкиваясь с препятствием, ведет себя как волна: она и проходит сквозь него, и отражается. То есть частица идет как бы и влево, и вправо одновременно. Это и есть квантовое случайное блуждание».

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

Еще один интересный вопрос — а что будет, если расположение (топология) гвоздиков на доске упорядочено неким замысловатым образом?

Скорость в квадрате

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

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

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

Когда квантовое становится неквантовым

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

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

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

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

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

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

Он добавляет, что, поскольку каждый алгоритм, который на них реализуется, можно математически записать в виде блужданий, ученые могут однозначно предсказать, будет функционировать он как квантовый или как классический. Причем, по словам исследователя, это можно сделать с вероятностью более 70% для незнакомых графов, и от 80% и более для знакомых. Такая постановка вопроса может помочь существенно сэкономить ресурсы, выделяемые на разработку квантового компьютера.

Квантовый софт, распространение информации и энергетика

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

«Если мы видим, что на некотором графе квантовые блуждания работают плохо, тогда мы знаем, что для этого графа лучше подойдет классическая система. Значит этот граф нам [для создания квантовых систем] не интересен», ― поясняет Мельников.

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

«Помимо реализации квантовых вычислений, еще одно важное приложение ― доставка энергии из точки в точку с минимальными затратами энергии на саму транспортировку, ― отмечает Алексей Мельников. ― К примеру, чтобы по проводу переносить электроны, вам нужно приложить напряжение, то есть затратить энергию на перенос электронов от положительного потенциала к отрицательному. А можно найти такой граф, в котором электроны бегут cлучайным образом по системе, но при этом приходят в нужную точку сами благодаря свойству квантовой суперпозиции. Это называется идеальный транспорт, мы к нему стремимся».

Статья: Melnikov A.A., Fedichkin L.E., Lee R‐K., Alodjants A., Machine Learning Transfer Efficiencies for Noisy Quantum Walks. Advanced quantum technologies, 2020/10.1002/qute.202070043