Квантовый отжиг

Чтобы узнать о других значениях, см. Отжиг (значения) .

Квантовый отжиг ( QA ) — это процесс оптимизации для поиска глобального минимума заданной целевой функции по заданному набору возможных решений (состояний-кандидатов) с помощью процесса, использующего квантовые флуктуации . Квантовый отжиг используется в основном для задач, где пространство поиска дискретно ( задачи комбинаторной оптимизации ) со многими локальными минимумами ; например, найти Основное состояние спинового стекла или задача коммивояжера . Термин «квантовый отжиг» был впервые предложен в 1988 году Б. Аполлони, Н. Чеза Бьянки и Д. Де Фалько как классический квантовый алгоритм. В нынешнем виде он был сформулирован Т. Кадоваки и Х. Нисимори ( джа ) в 1998 году. хотя вариант мнимого времени без квантовой когерентности обсуждался А. Б. Финнилой, М. А. Гомесом, К. Себеником и Дж. Д. Доллом в 1994 году.

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

Сравнение с имитацией отжига

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

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

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

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

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

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

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

Хронология идей, связанных с квантовым отжигом в спиновых стеклах Изинга:

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

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

Дополнительная информация: D-Wave Systems § Компьютерные системы и D-Wave Two.

Фотография чипа, созданного 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 года Южной Калифорнии Университета Институт информационных наук получил самолет Lockheed D-Wave One.

В мае 2013 года было объявлено, что консорциум Google , НАСА Эймса и некоммерческой ассоциации университетов космических исследований приобрел у 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 превосходит как моделируемый отжиг, так и квантовый метод Монте-Карло почти в 100 000 000 раз в ряде сложных задач оптимизации.

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

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

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

• Бапст, В.; Фойни, Л.; Крзакала, Ф.; Семерджян Г.; Зампони, Ф. (2013). «Квантовый адиабатический алгоритм, примененный к задачам случайной оптимизации: перспектива квантового спинового стекла». Отчеты по физике . 523 (3): 127–205. arXiv : 1210.0811 . Бибкод : 2013ФР...523..127Б . дои : 10.1016/j.physrep.2012.10.002 . S2CID   19019744 .
• Чандра, Анджан К.; Дас, Арнаб и Чакрабарти, Бикас К. , ред. (2010). Квантовая закалка, отжиг и расчет . Конспект лекций по физике. Том. 802. Гейдельберг: Спрингер. ISBN  978-3-64211-469-4 .
• Дас, Арнаб и Чакрабарти, Бикас К., ред. (2005). Квантовый отжиг и связанные с ним методы оптимизации . Конспект лекций по физике. Том. 679. Гейдельберг: Спрингер. ISBN  978-3-54027-987-7 .
• Дутта, А.; Эппли, Г.; Чакрабарти, Британская Колумбия; Дивакаран, У.; Розенбаум, Т.Ф. и Сен, Д. (2015). Квантовые фазовые переходы в спиновых моделях поперечного поля: от статистической физики к квантовой информации . Кембридж и Дели: Издательство Кембриджского университета. ISBN  978-1-10706-879-7 .
• Ли, Фусян; Черняк В.Ю.; Синицын Н.А. (2013). «Квантовый отжиг и вычисления: краткая документальная заметка». Наука и культура . 79 : 485–500. arXiv : 1310.1339 . Бибкод : 2013arXiv1310.1339G . .
• Сузуки, С.; Иноуэ, Ж.-И. и Чакрабарти, Б.К. (2013). «Глава 8 о квантовом отжиге». Квантовые фазы Изинга и переходы в поперечных моделях Изинга (2-е изд.). Гейдельберг: Спрингер. ISBN  978-3-64233-038-4 .
• Танака, С.; Тамура Р. и Чакрабарти Б.К. (2017). Квантовые спиновые стекла, отжиг и расчет . Кембридж и Дели: Издательство Кембриджского университета. ISBN  978-1-10711-319-0 .
• «Квантовый отжиг и вычисления: проблемы и перспективы» . Философские труды А. 381 . Королевское общество, Лондон. Январь 2023 г.