Современная электроника №9/2022

СОВРЕМЕННЫЕ ТЕХНОЛОГИИ 11 WWW.SOEL.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА ◆ № 9 2022 тонианом H p (правый график рис. 4). При идеальном адиабатическом про- цессе система минует все локальные энергетические уровни и переходит в конечное состояние с минимальным из всех возможных значением гамильто- ниана. На практике наиболее близкой к рассмотренному примеру оказалась математическая модель статистиче- ской физики, описывающая взаимо- действие между отдельными магнит- ными моментами в ферромагнитном веществе, «модель “Изинга”» (Ising model) [14]. В самом простом виде одномерной модели «Изинга» считается, что элек- троны расположены в узлах регуляр- ной плоской решетки и можно учи- тывать взаимодействие между собой только соседних магнитных момен- тов. В идеальном случае, если убрать внешнее магнитное поле, то при отсут- ствии любого другого внешнего воз- действия такая система постепенно переходит в состояние с наименьшей суммарной энергией, при котором все магнитные моменты останутся ори- ентированными вдоль некоторого выделенного направления. Это соот- ветствует «ферромагнитной модели “Изинга”». Следует отметить, что для случая неферромагнитных материа- лов спины в основном состоянии для соседних решеток будут ориентирова- ны в противоположных направлениях. В реальной жизни на систему могут воздействовать различные внешние факторы, такие, например, как тепло- вое движение электронов, магнитное поле Земли, микровибрации и т.д. Поэ- тому в реальных условиях полностью равновесного состояния с одинаковой ориентацией всех магнитных момен- тов не будет. Достаточно подробно модель «Изинга» рассмотрена в [15]. Изначально модель «Изинга» была разработана для того, чтобы описать фазовые переходы в магнетиках. Одна- ко алгоритм этой модели со временем стал основой для широкого класса так называемых решётчатых моделей (lattice model), позволяющих исследо- вать и другие процессы, которые мож- но свести к задаче о взаимном влиянии микросистем, размещённых в узлах регулярной решетки при различных внешних условиях [16]. Свойство алгоритма модели «Изин- га» адаптироваться для решения дру- гих задач позволило создать целый класс так называемых «задач оптими- зации Изинга». Например, в рассмо- тренной выше задаче коммивояжёра минимальное время прохождения по всему маршруту будет соответствовать минимальному значению гамильтониа- на в оптимизационной задаче «Изинга». Если вернуться к задаче о коммивоя- жёре и оставить ему только три пункта назначения (рис. 5) [17], то минималь- ное время, за которое будет пройден весь маршрут с одной и той же скоро- стью, можно записать в такой форме: T = V[S1 + S2 + S3 + S4 + S5 + S6], где S1(0, 1, 2, 3 ,0) – это расстояние по маршруту от стоянки коммивояжёра (точка 0) до посёлка 1, затем до посёл- ка 2, затем до посёлка 3 и обратный путь и т.д. (рис. 5). Для простейшего варианта 2-D модели «Изинга», в которой рассма- тривается вариант с четырьмя спина- ми, размещёнными по углам квадрата, гамильтониан системы можно записать в следующем виде: H 4 = – J ( σ 1 σ 2 + σ 2 σ 3 + σ 3 σ 4 + σ 4 σ 1 + σ 1 σ 3 + σ 4 σ 2 ), где: суммируются только спиновые переменные соседних пар σ i ; J > 0 – это константа, описывающая силу взаимодействия между соседни- ми спинами. Всего в модели с четырьмя спинами в углах квадрата взаимодействие реали- зуется по периметру квадрата (4 вари- анта) плюс 2 варианта по диагоналям. В модели «Изинга» суммируется энер- гия взаимодействий между спинами каждой соседней пары. При этом вза- имодействие между соседними спина- ми определяет параллельное выстра- ивание магнитных моментов вдоль некоторого выделенного направления, понижая тем самым энергию системы и внося в неё отрицательный вклад – J . С другой стороны, антипараллельная ориентация соседних моментов энер- гетически невыгодна и приводит к уве- личению энергии на величину + J . Суммарная энергия системы зави- сит от того, выровнены одинаково все спины или нет. В идеальном случае все слагаемые приведённого выше гамиль- тониана должны иметь отрицательное значение. Сравнивая последнюю, приведённую выше, формулу гамильтониана для 2-D «модели Изинга» (2D – 4 nodes) с фор- мулой минимального времени про- хождения маршрута в задаче с ком- мивояжером, можно увидеть, что оба математических выражения аналогич- ны по структуре, за исключением кон- стант. Таким образом, мы можем исходную задачу с коммивояжёром свести к алго- ритму её решения с помощью модели «Изинга», используемой в адиабатиче- ском квантовом вычислителе [18]. В общем случае основная задача ади- абатических квантовых вычислений сводится к тому, чтобы представить поставленную задачу оптимизации в такой форме, в которой её сможет решить соответствующий квантовый вычислитель. Развитие аппаратной части этих вычислителей способство- вало развитию нового направления, получившего название адиабатиче- ской квантовой оптимизации (adiabatic quantum optimization – AQO). В насто- ящее время это направление успеш- но используется в самых различных приложениях для решения трудных NP-задач. К сожалению, идеальный адиаба- тический квантовый вычислитель, в котором полностью выполнялись бы все условия адиабатического про- цесса, крайне сложно реализовать на практике. Кроме того, для решения задач класса NP с приемлемыми точностями необ- ходимы довольно большие време- на вычисления. При этом необходи- мо использовать большие количества кубитов, что, в свою очередь, увеличи- вает и шум, и время обработки [19–21]. Поэтому был разработан упрощён- ный вариант адиабатических кванто- вых вычислений, в котором эволюци- онный процесс идёт «не сам по себе», а регулируется внешним магнитным полем. Лидером в разработке и производстве таких квантовых вычислителей являет- ся канадская фирма «D-Wave Systems», предложившая почти 20 лет назад упрощённую модель адиабатическо- го устройства с управляемым эволюци- онным процессом, которое получило Рис. 5. Возможные варианты маршрутов для задачи коммивояжёра из трёх пунктов [17]