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

Для использования в других целях см. Отжиг (значения).

Квантовый отжиг (QA) это метаэвристический для поиска глобальный минимум данного целевая функция над заданным набором возможных решений (состояний-кандидатов) процессом, использующим квантовые флуктуации (другими словами, метапроцедура для поиска процедуры, которая находит абсолютный минимальный размер / длину / стоимость / расстояние из, возможно, очень большого, но, тем не менее, конечного набора возможных решений с использованием вычислений на основе квантовых флуктуаций вместо классических вычислений) . Квантовый отжиг используется в основном для задач, где пространство поиска дискретно (комбинаторная оптимизация проблемы) со многими локальные минимумы; например, найти основное состояние из спин-стекло[1] или задача коммивояжера. Квантовый отжиг был впервые предложен в 1988 г. Б. Аполлони, Н. Чезой Бьянки и Д. Де Фалько.[2][3] В нынешнем виде он был сформулирован Т. Кадоваки и Х. Нисимори (я ) в «Квантовом отжиге в поперечной модели Изинга»[4] хотя предложение в другой форме было сделано А. Б. Финнилой, М. А. Гомесом, К. Себеником и Дж. Д. Доллем в статье «Квантовый отжиг: новый метод минимизации многомерных функций».[5]

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

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

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

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

Quant-annl.jpg

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

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

Экспериментально и теоретически было продемонстрировано, что квантовый отжиг действительно может превзойти термический отжиг (имитированный отжиг) в некоторых случаях, особенно когда ландшафт потенциальной энергии (стоимости) состоит из очень высоких, но тонких барьеров, окружающих мелкие локальные минимумы.[13] Поскольку вероятности теплового перехода (пропорциональные , с температура и то Постоянная Больцмана ) зависят только от высоты Из-за очень высоких барьеров тепловым флуктуациям чрезвычайно сложно вывести систему из таких локальных минимумов. Однако, как ранее в 1989 году утверждали Рэй, Чакрабарти и Чакрабарти,[1] вероятность квантового туннелирования через один и тот же барьер (рассматриваемый отдельно) зависит не только от высоты барьера, но и по его ширине и приблизительно дается выражением , куда - туннельное поле.[14] Эта дополнительная ручка по ширине , при наличии квантового туннелирования, может быть очень полезным: если барьеры достаточно тонкие (т.е. ) квантовые флуктуации наверняка могут вывести систему из мелких локальных минимумов. Для -спиновое стекло, высота барьера становится в порядке . При постоянном значении один получает пропорционально на время отжига (вместо пропорционально для термического отжига), а может даже стать -независимо для случаев, когда уменьшается как .[15] [16]

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

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

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

В 2011, Системы D-Wave анонсировала первый коммерческий квантовый отжигатель на рынке под названием D-Wave One и опубликовала статью в Nature о его характеристиках.[18] Компания утверждает, что в этой системе используется 128 кубит чипсет процессора.[19] 25 мая 2011 года D-Wave объявила, что Локхид Мартин Корпорация заключила договор о покупке системы D-Wave One.[20] 28 октября 2011 г. USC с Институт информационных наук получил поставку Lockheed D-Wave One.

В мае 2013 года было объявлено, что консорциум Google, НАСА Эймс и некоммерческая Ассоциация университетов космических исследований приобрел адиабатический квантовый компьютер от D-Wave Systems с 512 кубитами.[21][22] Уже доступно обширное исследование его эффективности в качестве квантового отжига по сравнению с некоторыми классическими алгоритмами отжига.[23]

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

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

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

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

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

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

Рекомендации

  1. ^ а б Ray, P .; Chakrabarti, B.K .; Чакрабарти, Арунава (1989). «Модель Шеррингтона-Киркпатрика в поперечном поле: отсутствие нарушения реплики симметрии из-за квантовых флуктуаций». Физический обзор B. 39 (16): 11828–11832. Bibcode:1989PhRvB..3911828R. Дои:10.1103 / PhysRevB.39.11828. PMID  9948016.
  2. ^ Аполлони, Бруно; Чеза-Бьянки, Николо; Де Фалько, Диего (июль 1988 г.). «Численная реализация квантового отжига». Стохастические процессы, физика и геометрия, Труды конференции Аскона-Локарно.
  3. ^ Аполлони, Бруно; Карвалью, Мария Ч .; Де Фалько, Диего (1989). «Квантовая стохастическая оптимизация». Stoc. Proc. Приложение. 33 (2): 233–244. Дои:10.1016/0304-4149(89)90040-9.
  4. ^ Kadowaki, T .; Нисимори, Х. (1998). «Квантовый отжиг в поперечной модели Изинга». Phys. Ред. E. 58 (5): 5355. arXiv:cond-mat / 9804280. Bibcode:1998PhRvE..58.5355K. Дои:10.1103 / PhysRevE.58.5355. S2CID  36114913.
  5. ^ Finnila, A.B .; Gomez, M.A .; Себеник, Ц .; Стенсон, С .; Долл, J.D. (1994). «Квантовый отжиг: новый метод минимизации многомерных функций». Письма по химической физике. 219 (5–6): 343–348. arXiv:хим-ph / 9404003. Bibcode:1994CPL ... 219..343F. Дои:10.1016/0009-2614(94)00117-0. S2CID  97302385.
  6. ^ Farhi, E .; Goldstone, J .; Gutmann, S .; Lapan, J .; Ludgren, A .; Преда, Д. (2001). «Алгоритм квантовой адиабатической эволюции, примененный к случайным экземплярам NP-полной задачи». Наука. 292 (5516): 472–5. arXiv:Quant-ph / 0104129. Bibcode:2001Наука ... 292..472F. Дои:10.1126 / science.1057726. PMID  11313487. S2CID  10132718.
  7. ^ Э. Кроссон, Э. Фархи, C.Y-Y. Линь, HH. Линь, П. Шор, «Различные стратегии оптимизации с использованием квантового адиабатического алгоритма» arXiv:1401.7320
  8. ^ Д. Мутукришнан, Т. Альбаш, Д.А. Лидар, "Когда диабатический эффект превосходит адиабатический при квантовой оптимизации" arXiv:1505.01249
  9. ^ Brooke, J .; Битко, Д .; Розенбаум, Т. Ф .; Эппли, Г. (1999). «Квантовый отжиг неупорядоченного магнита». Наука. 284 (5415): 779–81. arXiv:cond-mat / 0105238. Bibcode:1999Научный ... 284..779B. Дои:10.1126 / science.284.5415.779. PMID  10221904. S2CID  37564720.
  10. ^ Морита, Сатоши; Нисимори, Хидетоши (2008). «Математические основы квантового отжига». Журнал математической физики. 49 (12): 125210. arXiv:0806.1859. Bibcode:2008JMP .... 49l5210M. Дои:10.1063/1.2995837. S2CID  13992889.
  11. ^ Г. Э. Санторо и Э. Тосатти "Оптимизация с использованием квантовой механики: квантовый отжиг через адиабатическую эволюцию "J. Phys. A 39, R393 (2006)
  12. ^ Heim, B .; Rønnow, T. F .; Исаков, С. В .; Тройер, М. (2015). «Квантовый отжиг против классического отжига спиновых стекол Изинга». Наука. 348 (6231): 215–217. arXiv:1411.5693. Bibcode:2015Научный ... 348..215H. Дои:10.1126 / science.aaa4170. PMID  25765071.
  13. ^ "локальные / глобальные минимумы / максимумы".
  14. ^ А. Дас, Б.К. Чакрабарти и Р. Б. Стинчкомб "Квантовый отжиг в системе с кинетическими ограничениями ", Phys. Rev. E 72 Изобразительное искусство. 026701 (2005)
  15. ^ См., Например, S. Mukherjee и B.K. Chakrabarti "Multivariable Optimization: Quantum Annealing & Computing", Eur. Phys. J. ST 224, с. 17–24 (2015) arXiv:1408.3262
  16. ^ Das, A .; Чакрабарти, Б. К. (2008). «Квантовый отжиг и аналоговые квантовые вычисления». Ред. Мод. Phys. 80 (3): 1061–1081. arXiv:0801.2193. Bibcode:2008RvMP ... 80.1061D. CiteSeerX  10.1.1.563.9990. Дои:10.1103 / RevModPhys.80.1061. S2CID  14255125.
  17. ^ Ф. Ли; В. Ю. Черняк; Синицын Н.А. (2018). «Квантовый отжиг и термализация: выводы из интегрируемости». Письма с физическими проверками. 121 (19): 190601. arXiv:1804.00371. Bibcode:2018arXiv180400371L. Дои:10.1103 / PhysRevLett.121.190601. PMID  30468584. S2CID  53594139.
  18. ^ Johnson, M. W .; и другие. (2011). «Квантовый отжиг с изготовленными спинами». Природа. 473 (7346): 194–8. Bibcode:2011Натура.473..194J. Дои:10.1038 / природа10012. PMID  21562559. S2CID  205224761.
  19. ^ «Обучение программированию D-Wave One». Получено 11 мая 2011.
  20. ^ «D-Wave Systems продает свою первую систему квантовых вычислений компании Lockheed Martin Corporation». 2011-05-25. Получено 2011-05-30.
  21. ^ Джонс, Н. (2013). «Google и НАСА скупают квантовый компьютер». Новости природы. Дои:10.1038 / природа.2013.12999. S2CID  57405432.
  22. ^ Смелянский В. Н., Э. Г. Риффель, С. И. Кныш, К. П. Уильямс, М. В. Джонсон, М. К. Том, В. Г. Макреди, К. Л. Пуденц, "Краткосрочный квантовый вычислительный подход для сложных вычислительных задач в исследовании космоса", arXiv:1204.2821
  23. ^ Boixo, S .; Rønnow, T. F .; Исаков, С. В .; Wang, Z .; Wecker, D .; Лидар, Д. А .; Martinis, J.M .; Тройер, М. (2014). «Доказательства квантового отжига с более чем сотней кубитов». Природа Физика. 10 (3): 218–224. arXiv:1304.4595. Bibcode:2014НатФ..10..218Б. Дои:10,1038 / nphys2900. S2CID  8031023.
  24. ^ «D-Wave Systems, создающая экосистему квантовых приложений, объявляет о партнерстве с DNA-SEQ Alliance и 1QBit». Системы D-Wave. Получено 22 июн 2014.
  25. ^ «1QBit Research». 1QBit. Архивировано из оригинал 19 июня 2014 г.. Получено 22 июн 2014.
  26. ^ Т. Лантинг; и другие. (2014-05-29). «Запутанность в процессоре квантового отжига». Физический обзор X. 4 (2): 021041. arXiv:1401.3500. Bibcode:2014PhRvX ... 4b1041L. Дои:10.1103 / PhysRevX.4.021041. S2CID  19235104.
  27. ^ Гельмут Кацграбер, цитируется в (Чо 2014 ).
  28. ^ Чо, Адриан (20 июня 2014 г.), «Квантовый или нет, но противоречивый компьютер не дает ускорения», Наука, 344 (6190): 1330–1331, Bibcode:2014Научный ... 344.1330C, Дои:10.1126 / science.344.6190.1330, PMID  24948715.
  29. ^ Мохаммад Х. Амин, "Поиски квантового ускорения в квазистатических квантовых отжигателях" arXiv:1503.04216
  30. ^ Стейгер, Дамиан; Хайм, Беттина; Рённов, Троелс; Тройер, Маттиас (22 октября 2015 г.), «Производительность оборудования для квантового отжига», в Хакридже, Дэвид А. Эберт, Рейнхард; Gruneisen, Mark T; Дусек, Милослав; Рарити, Джон Дж. (Ред.), Электрооптические и инфракрасные системы: технологии и приложения XII; и квантовая информатика и технологии, 9648, п. 964816, г. Дои:10.1117/12.2202661, S2CID  57916974
  31. ^ «Когда может победить квантовый отжиг?». Блог исследований. Получено 2016-01-21.
  32. ^ Венегас-Андрака, С.Е .; Cruz-Santos, W .; McGeoch, C .; Ланзагорта, М. (2018). «Междисциплинарное введение в алгоритмы на основе квантового отжига». Современная физика. 59 (2): 174–196. arXiv:1803.03372. Bibcode:2018ConPh..59..174V. Дои:10.1080/00107514.2018.1450720. S2CID  118974781.

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