Квантовый отжиг - Quantum annealing

Квантовый отжиг ( QA ) - это метаэвристика для нахождения глобального минимума заданной целевой функции по заданному набору возможных решений (состояний-кандидатов) с помощью процесса, использующего квантовые флуктуации (другими словами, метапроцедура для поиска процедуры, которая находит абсолютный минимальный размер / длину / стоимость / расстояние из возможно очень большого, но, тем не менее, конечного набора возможных решений с использованием вычислений на основе квантовых флуктуаций вместо классических вычислений). Квантовый отжиг используется в основном для задач, в которых пространство поиска дискретно ( задачи комбинаторной оптимизации ) с множеством локальных минимумов ; такие как нахождение основного состояния в виде спинового стекла или задачи коммивояжера . Термин «квантовый отжиг» был впервые предложен в 1988 г. Б. Аполлони, Н. Чезой Бьянки и Д. Де Фалько в качестве квантового классического алгоритма. В его нынешней форме он был сформулирован Т. Кадоваки и Х. Нишимори ( ja ) в «Квантовом отжиге в поперечной модели Изинга», хотя предложение в другой форме было сделано AB Finnila, MA Gomez, C. Sebenik и JD. Долл в «Квантовом отжиге» - это новый метод минимизации многомерных функций ».

Квантовый отжиг начинается с квантово-механической суперпозиции всех возможных состояний (состояний-кандидатов) с равными весами. Затем система развивается в соответствии с зависящим от времени уравнением Шредингера , естественным квантово-механическим развитием физических систем. Амплитуды всех состояний-кандидатов продолжают изменяться, реализуя квантовый параллелизм в соответствии с зависящей от времени силой поперечного поля, которое вызывает квантовое туннелирование между состояниями. Если скорость изменения поперечного поля достаточно мала, система остается близкой к основному состоянию мгновенного гамильтониана (см. Также адиабатические квантовые вычисления ). Если скорость изменения поперечного поля увеличивается, система может временно покинуть основное состояние, но с большей вероятностью придет к основному состоянию гамильтониана конечной задачи, то есть диабатического квантового вычисления. Наконец, поперечное поле отключается, и ожидается, что система достигла основного состояния классической модели Изинга, которое соответствует решению исходной задачи оптимизации. Сразу после первоначального теоретического предложения было сообщено об экспериментальной демонстрации успеха квантового отжига для случайных магнитов.

Сравнение с моделированным отжигом

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

Квантовая механика: аналогия и преимущество

Туннельное поле - это, по сути, термин кинетической энергии, который не коммутируется с классической частью потенциальной энергии исходного стекла. Весь процесс можно смоделировать на компьютере, используя квантовый Монте-Карло (или другой стохастический метод), и таким образом получить эвристический алгоритм для нахождения основного состояния классического стекла.

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

Экспериментально и теоретически было продемонстрировано, что квантовый отжиг действительно может превзойти термический отжиг (имитированный отжиг) в некоторых случаях, особенно когда ландшафт потенциальной энергии (стоимости) состоит из очень высоких, но тонких барьеров, окружающих мелкие локальные минимумы. Поскольку тепловые вероятности перехода (пропорциональные , с температурой и с постоянной Больцмана ) зависят только от высоты барьеров, для очень высоких барьеров, чрезвычайно трудно для тепловых колебаний , чтобы получить систему из таких локальных минимумов. Однако, как отмечалось ранее , в 1989 году Ray, Чакрабарти & Чакрабарти, вероятность квантового туннелирования через тот же барьер (рассматриваемой изолированно) зависит не только от высоты барьера, но и по ее ширине и приблизительно определяется , где находится туннельное поле. Эта дополнительная регулировка по ширине при наличии квантового туннелирования может быть очень полезной: если барьеры достаточно тонкие (т. Е. ), Квантовые флуктуации могут наверняка вывести систему из мелких локальных минимумов. Для -спинового стекла высота барьера становится порядка . При постоянном значении единица становится пропорциональной времени отжига (вместо пропорциональной времени термического отжига), а может даже стать независимой для случаев, когда уменьшается as . ${\ displaystyle e ^ {- {\ frac {\ Delta} {k_ {B} T}}}}$${\ displaystyle T}$${\ displaystyle k_ {B}}$${\ displaystyle \ Delta}$${\ displaystyle \ Delta}$${\ displaystyle w}$${\ displaystyle e ^ {- {\ frac {{\ sqrt {\ Delta}} w} {\ Gamma}}}}$${\ displaystyle \ Gamma}$${\ displaystyle w}$${\ displaystyle w \ ll {\ sqrt {\ Delta}}}$${\ displaystyle N}$${\ displaystyle \ Delta}$${\ displaystyle N}$${\ displaystyle w}$${\ Displaystyle \ тау}$${\ displaystyle e ^ {\ sqrt {N}}}$${\ Displaystyle \ тау}$${\ displaystyle e ^ {N}}$${\ Displaystyle \ тау}$${\ displaystyle N}$${\ displaystyle w}$${\ displaystyle 1 / {\ sqrt {N}}}$

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

График квантового отжига в спиновых стеклах Изинга:

• 1981 Представлена ​​квантовая модель спинового стекла Изинга и изучена его переходная характеристика;
• Идея 1989 г. предположила, что квантовые флуктуации могут помочь исследовать сложные энергетические ландшафты классических спиновых стекол Изинга путем выхода из локальных минимумов (имеющих высокие, но тонкие барьеры) с помощью туннелирования;
• 1991 Экспериментальная реализация квантового спинового стекла Изинга в LiHoYF;
• 1998 Первое моделирование методом Монте-Карло, демонстрирующее квантовый отжиг в стеклянных системах Изинга;
• 1999 Первая экспериментальная демонстрация квантового отжига в стеклянных магнетиках LiHoYF Ising;
• 2011 г. Машина для квантового отжига сверхпроводящих цепей для систем спинового стекла Ising, реализованная и проданная компанией D-Wave Systems.

Реализации D-Wave

Фотография микросхемы, созданной D-Wave Systems , установленной и соединенной проволокой в ​​держателе образца. Процессор D-Wave One разработан для использования 128 сверхпроводящих логических элементов, которые демонстрируют управляемую и настраиваемую связь для выполнения операций.

В 2011 году D-Wave Systems анонсировала первый на рынке коммерческий квантовый отжигатель под названием D-Wave One и опубликовала в Nature статью о его характеристиках. Компания утверждает, что в этой системе используется чипсет процессора на 128 кубитов . 25 мая 2011 года D-Wave объявила, что корпорация Lockheed Martin заключила соглашение о покупке системы D-Wave One. 28 октября 2011 USC «s Институт информатики принял поставку D-Wave One Локхида.

В мае 2013 года было объявлено, что консорциум Google , NASA Ames и некоммерческой ассоциации университетов космических исследований приобрел у D-Wave Systems адиабатический квантовый компьютер с 512 кубитами. Уже доступно обширное исследование его эффективности в качестве квантового отжига по сравнению с некоторыми классическими алгоритмами отжига.

В июне 2014 года D-Wave анонсировала новую экосистему квантовых приложений с финансовой компанией 1QB Information Technologies (1QBit) и исследовательской группой DNA-SEQ, чтобы сосредоточиться на решении реальных проблем с помощью квантового оборудования. Как первая компания, занимающаяся производством программных приложений для коммерчески доступных квантовых компьютеров, отдел исследований и разработок 1QBit сосредоточился на процессорах квантового отжига D-Wave и успешно продемонстрировал, что эти процессоры подходят для решения реальных приложений.

С опубликованными демонстрациями запутанности вопрос о том, может ли машина D-Wave продемонстрировать квантовое ускорение по сравнению со всеми классическими компьютерами, остается без ответа. Исследование, опубликованное в журнале Science в июне 2014 года, описанное как «вероятно, наиболее полное и точное исследование производительности машины D-Wave» и «самое справедливое сравнение на сегодняшний день», попыталось определить и измерить квантовое ускорение. Было предложено несколько определений, так как некоторые из них могут быть непроверяемы эмпирическими тестами, в то время как другие, хотя и фальсифицированные, тем не менее допускают наличие преимуществ в производительности. Исследование показало, что микросхема D-Wave «не дает квантового ускорения», и не исключает такой возможности в будущих тестах. Исследователи, возглавляемые Матиасом Тройером из Швейцарского федерального технологического института , не обнаружили «квантового ускорения» во всем диапазоне своих тестов, а только неубедительные результаты при рассмотрении подмножеств тестов. Их работа проиллюстрировала «тонкую природу вопроса о квантовом ускорении». Дальнейшая работа позволила углубить понимание этих тестовых метрик и их зависимости от уравновешенных систем, тем самым упуская из-за квантовой динамики какие-либо признаки преимущества.

Есть много открытых вопросов относительно квантового ускорения. Ссылка на ETH в предыдущем разделе предназначена только для одного класса тестовых задач. Потенциально могут быть другие классы проблем, в которых может произойти квантовое ускорение. Исследователи из Google, LANL, USC, Texas A&M и D-Wave усердно работают над поиском таких классов проблем.

В декабре 2015 года Google объявил, что D-Wave 2X превосходит модели отжига и квантовый Монте-Карло примерно в 100000000 раз по набору сложных задач оптимизации.

Архитектура D-Wave отличается от традиционных квантовых компьютеров. Неизвестно, что он полиномиально эквивалентен универсальному квантовому компьютеру и, в частности, не может выполнять алгоритм Шора, потому что алгоритм Шора не является процессом восхождения на холмы. Алгоритм Шора требует универсального квантового компьютера. D-Wave утверждает, что выполняет только квантовый отжиг.

«Междисциплинарное введение в алгоритмы, основанные на квантовом отжиге» представляет собой введение в задачи комбинаторной оптимизации ( NP-трудные ), общую структуру алгоритмов на основе квантового отжига и два примера таких алгоритмов для решения экземпляров max- Задачи SAT и Minimum Multicut, а также обзор систем квантового отжига, производимых D-Wave Systems. Сообщалось, что гибридные квантово-классические алгоритмы для крупномасштабных задач дискретно-непрерывной оптимизации иллюстрируют квантовое преимущество.

использованная литература

дальнейшее чтение

• Венегас-Андрака, Сальвадор, Э .; Крус-Сантос, Уильям; МакГеоч, Кэтрин; Ланзагорта, Марко (2018). «Междисциплинарное введение в алгоритмы на основе квантового отжига». Современная физика . 59 (2): 174–197. arXiv : 1803.03372 . Bibcode : 2018ConPh..59..174V . DOI : 10.1080 / 00107514.2018.1450720 . S2CID  118974781 .
• http://iopscience.iop.org/0305-4470/39/36/R01 . Цитировать журнал требует |journal=( помощь );Отсутствует или пусто |title=( справка )
• Сузуки С., Ж.-и. Иноуэ и Б.К. Чакрабарти, Квантовые фазы Изинга и переходы в поперечных моделях Изинга , Springer, Heidelberg (2013), глава 8 о квантовом отжиге.
• Bapst, V .; Foini, L .; Krzakala, F .; Semerjian, G .; Зампони, Ф. (2013). «Квантовый адиабатический алгоритм, применяемый к задачам случайной оптимизации: перспектива квантового спинового стекла». Отчеты по физике . 523 (3): 127–205. arXiv : 1210.0811 . Bibcode : 2013PhR ... 523..127B . DOI : 10.1016 / j.physrep.2012.10.002 . S2CID  19019744 .
• Арнаб Дас и Бикас К. Чакрабарти (редакторы), Квантовый отжиг и соответствующие методы оптимизации , Лекция по физике, 679 , Springer, Heidelberg (2005).
• Анджан К. Чандра, Арнаб Дас и Бикас К. Чакрабарти (ред.), Квантовое тушение, отжиг и вычисления , Лекция по физике, 802 , Springer, Heidelberg (2010).
• Ли, Фусян; Черняк В.Я .; Синицын, Н.А. (2013). «Квантовый отжиг и вычисления: краткая документация». arXiv : 1310,1339 . Bibcode : 2013arXiv1310.1339G . Цитировать журнал требует |journal=( помощь ).
• А. Датта, Г. Эппли, Б. К. Чакрабарти, У. Дивакаран, Т. Ф. Розенбаум и Д. Сен, «Квантовые фазовые переходы в моделях поперечного спина: от статистической физики к квантовой информации» , Издательство Кембриджского университета, Кембридж и Дели (2015).
• С. Танака, Р. Тамура и Б. К. Чакрабарти, Квантовые спиновые стекла, отжиг и вычисления , Cambridge University Press, Кембридж и Дели (2017).
• Индийская ассоциация научных новостей, специальный выпуск журнала «Наука и культура» о «Квантовом скачке в вычислениях» , Vol. 85 (5–6), май – июнь (2019 г.)