Расчет на волшебной пыли

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

Если говорить по-простому, то это принципиально новый тип аналогового компьютера, позволяющий решать задачи, по сложности недоступные ни суперкомпьютерам, ни квантовым. Статья об этом замечательном открытии опубликована в Nature materials .

Как набить рюкзак

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

Дело в том, что суперкомпьютеры решают эти задачи, что называется, «в лоб», очень быстро выполняя миллиарды расчетов, пока не придут к оптимальному решению. Квантовые компьютеры, появление которых пока только планируется, смогут экспоненциально ускорить этот процесс, выполняя гораздо больше вычислений одновременно, но и они по-прежнему работают по тому же принципу, перебирая все эти миллионы решений, пока не обнаружат оптимальное. Существует, однако, класс задач, для решения которых таким методом даже квантовому компьютеру потребуются тысячи лет. Самыми известные —задача о ранце и задача коммивояжера. Суть первой состоит в том, чтобы уложить как можно большее число ценных вещей в рюкзак при условии, что вместимость его ограничена. Вторая заключается в поиске самого выгодного маршрута, проходящего через ряд городов хотя бы по одному разу с последующим возвратом в исходный город. О сложности этой задачи говорит такой факт: если городов десять, то число вариантов маршрутов равно 2¹⁰, то есть 1024, а если их 100, то вариантов будет 2¹⁰⁰. Это так много, что выбрать из них кратчайший даже методом перебора невозможно, какой бы компьютер ни использовать.

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

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

Волшебная пыль

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

Понятие квазичастицы было введено в научный оборот Львом Ландау в 1940 году, чтобы упростить описание физических процессов, затрагивающих большое количество частиц и происходящих в кристаллах. В его основу легло простое соображение, вытекающее из известного феномена, который называется «дуализм волна–частица», согласно которому любой физический объект может быть описан и как волна, и как частица. А если любую частицу можно описать как волну, следовательно, любое колебание можно описать как частицу.

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

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

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

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

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

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

Процесс образования экситон-поляритона состоит в следующем: фотон попадает в полупроводник и поглощается с образованием экситона. Затем экситон рекомбинирует, испуская такой же фотон. Фотон опять поглощается, экситон опять рекомбинирует, и так далее. И уже нет ни экситона, ни фотона, а есть смешанное состояние — поляритон.

Конденсация, от которой все зависит

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

Подсветить самую большую впадину

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

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

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

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

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

Интенсивность фотолюминисцеции поляритонов в зависимости от выбранной модели потенциального поля

Источник: Nature materials

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

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

Через тернии к новому компьютеру

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

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