Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Для использования в других целях, см Отжиг (значения) .

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

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

Сравнение с моделированием отжига [ править ]

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

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

Quant-annl.jpg

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

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

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

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

Реализации D-Wave [ править ]

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

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

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

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

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

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

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

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

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

Ссылки [ править ]

  1. ^ a b Ray, P .; Чакрабарти, Б.К .; Чакрабарти, Арунава (1989). «Модель Шеррингтона-Киркпатрика в поперечном поле: отсутствие нарушения реплики симметрии из-за квантовых флуктуаций». Physical Review B . 39 (16): 11828–11832. Bibcode : 1989PhRvB..3911828R . DOI : 10.1103 / PhysRevB.39.11828 . PMID  9948016 .
  2. ^ Аполлони, Бруно; Чеза-Бьянки, Николо; Де Фалько, Диего (июль 1988 г.). «Численная реализация квантового отжига» . Стохастические процессы, физика и геометрия, Труды конференции Аскона-Локарно.
  3. ^ Аполлони, Бруно; Карвалью, Мария Ч .; Де Фалько, Диего (1989). «Квантовая стохастическая оптимизация» . Stoc. Proc. Appl . 33 (2): 233–244. DOI : 10.1016 / 0304-4149 (89) 90040-9 .
  4. ^ Kadowaki, T .; Нисимори, Х. (1998). «Квантовый отжиг в поперечной модели Изинга» . Phys. Rev. E . 58 (5): 5355. arXiv : cond-mat / 9804280 . Bibcode : 1998PhRvE..58.5355K . DOI : 10.1103 / PhysRevE.58.5355 . S2CID 36114913 . 
  5. ^ Finnila, AB; Гомес, Массачусетс; Себеник, Ц .; Стенсон, С .; Долл, JD (1994). «Квантовый отжиг: новый метод минимизации многомерных функций». Письма по химической физике . 219 (5–6): 343–348. arXiv : chem-ph / 9404003 . Bibcode : 1994CPL ... 219..343F . DOI : 10.1016 / 0009-2614 (94) 00117-0 . S2CID 97302385 . 
  6. ^ Фархи, E .; Goldstone, J .; Gutmann, S .; Lapan, J .; Ludgren, A .; Преда, Д. (2001). «Алгоритм квантовой адиабатической эволюции, применяемый к случайным экземплярам NP-Complete задачи» . Наука . 292 (5516): 472–5. arXiv : квант-ph / 0104129 . Bibcode : 2001Sci ... 292..472F . DOI : 10.1126 / science.1057726 . PMID 11313487 . S2CID 10132718 .  
  7. ^ Э. Кроссон, Э. Фархи, CY-Y. Lin, HH. Лин и П. Шор, "Различные стратегии оптимизации с использованием квантового адиабатического алгоритма" arXiv : 1401.7320
  8. ^ Д. Мутукришнан, Т. Альбаш, и Д.А. Лидар, «Когда диабатический эффект превосходит адиабатический при квантовой оптимизации» arXiv : 1505.01249
  9. ^ Брук, Дж .; Битко, Д .; Розенбаум, Т.Ф .; Эппли, Г. (1999). «Квантовый отжиг неупорядоченного магнита» . Наука . 284 (5415): 779–81. arXiv : cond-mat / 0105238 . Bibcode : 1999Sci ... 284..779B . DOI : 10.1126 / science.284.5415.779 . PMID 10221904 . S2CID 37564720 .  
  10. ^ Морита, Сатоши; Нисимори, Хидетоши (2008). «Математические основы квантового отжига». Журнал математической физики . 49 (12): 125210. arXiv : 0806.1859 . Bibcode : 2008JMP .... 49l5210M . DOI : 10.1063 / 1.2995837 . S2CID 13992889 . 
  11. ^ GE Santoro и E. Tosatti, " Оптимизация с использованием квантовой механики: квантовый отжиг посредством адиабатической эволюции " J. Phys. А 39 , R393 (2006)
  12. ^ Heim, B .; Рённов, TF; Исаков С.В.; Тройер, М. (2015). «Квантовый отжиг против классического отжига спиновых стекол Изинга» . Наука . 348 (6231): 215–217. arXiv : 1411.5693 . Bibcode : 2015Sci ... 348..215H . DOI : 10.1126 / science.aaa4170 . PMID 25765071 . 
  13. ^ "локальные / глобальные минимумы / максимумы" .
  14. ↑ A. Das, BK Chakrabarti и RB Stinchcombe, " Квантовый отжиг в системе с кинетическими ограничениями ", Phys. Ред. E 72 арт. 026701 (2005)
  15. ^ См., Например, С. Мукерджи и Б.К. Чакрабарти «Многовариантная оптимизация: квантовый отжиг и вычисления», 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 . DOI : 10.1103 / RevModPhys.80.1061 . S2CID 14255125 .   
  17. ^ Ф. Ли; В. Я. Черняк; Н.А. Синицын (2018). «Квантовый отжиг и термализация: выводы из интегрируемости». Письма с физическим обзором . 121 (19): 190601. arXiv : 1804.00371 . Bibcode : 2018arXiv180400371L . DOI : 10.1103 / PhysRevLett.121.190601 . PMID 30468584 . S2CID 53594139 .  
  18. ^ Джонсон, MW; и другие. (2011). «Квантовый отжиг с изготовленными спинами» . Природа . 473 (7346): 194–8. Bibcode : 2011Natur.473..194J . DOI : 10,1038 / природа10012 . PMID 21562559 . S2CID 205224761 .  
  19. ^ "Учимся программировать D-Wave One" . Проверено 11 мая 2011 года .
  20. ^ "D-Wave Systems продает свою первую систему квантовых вычислений корпорации Lockheed Martin" . 2011-05-25 . Проверено 30 мая 2011 .
  21. ^ Джонс, Н. (2013). «Google и НАСА скупают квантовый компьютер» . Новости природы . DOI : 10.1038 / nature.2013.12999 . S2CID 57405432 . 
  22. ^ В. Н. Смелянский, Э. Г. Риффель , С. И. Кныш, С. П. Уильямс, М. В. Джонсон, М. К. Том, У. Г. Макреди, К. Л. Пуденц, "Подход к краткосрочным квантовым вычислениям для сложных вычислительных задач в исследовании космоса", arXiv : 1204.2821
  23. ^ Boixo, S .; Рённов, TF; Исаков С.В.; Wang, Z .; Wecker, D .; Лидар Д.А. Мартинис, JM; Тройер, М. (2014). «Доказательства квантового отжига с более чем сотней кубитов» . Физика природы . 10 (3): 218–224. arXiv : 1304.4595 . Bibcode : 2014NatPh..10..218B . DOI : 10.1038 / nphys2900 . S2CID 8031023 . 
  24. ^ «Системы D-Wave для создания экосистемы квантовых приложений, объявляет о партнерстве с DNA-SEQ Alliance и 1QBit» . Системы D-Wave . Проверено 22 июня 2014 .
  25. ^ «1QBit Research» . 1QBit . Архивировано из оригинального 19 июня 2014 года . Проверено 22 июня 2014 .
  26. ^ Т. Лантинг; и другие. (2014-05-29). «Запутанность в процессоре квантового отжига». Physical Review X . 4 (2): 021041. arXiv : 1401.3500 . Bibcode : 2014PhRvX ... 4b1041L . DOI : 10.1103 / PhysRevX.4.021041 . S2CID 19235104 . 
  27. ^ Хельмут Кацграбер, цитируется в ( Cho 2014 ).
  28. ^ Чо, Адриан (20 июня 2014), "Quantum или нет, спорное компьютер не дает ускорение", Science , 344 (6190): 1330-1331, Bibcode : 2014Sci ... 344.1330C , DOI : 10.1126 / science.344.6190. 1330 , PMID 24948715 .
  29. ^ Мохаммад Х. Амин, «Поиск квантового ускорения в квазистатических квантовых отжигателях» arXiv : 1503.04216
  30. ^ Steiger, Дамиан; Хайм, Беттина; Рённов, Троелс; Тройер, Маттиас (22 октября 2015 г.), «Производительность оборудования для квантового отжига», в Хакридже, Дэвид А. Эберт, Рейнхард; Gruneisen, Mark T; Дусек, Милослав; Рарити, Джон Дж. (Ред.), Электрооптические и инфракрасные системы: технологии и приложения XII; and Quantum Information Science and Technology , 9648 , p. 964816, DOI : 10,1117 / 12,2202661 , S2CID 57916974 
  31. ^ "Когда может победить квантовый отжиг?" . Блог исследований . Проверено 21 января 2016 .
  32. ^ Венегас-Андрака, ЮВ; Cruz-Santos, W .; McGeoch, C .; Ланзагорта, М. (2018). «Междисциплинарное введение в алгоритмы на основе квантового отжига». Современная физика . 59 (2): 174–196. arXiv : 1803.03372 . Bibcode : 2018ConPh..59..174V . DOI : 10.1080 / 00107514.2018.1450720 . S2CID 118974781 . 
  33. ^ Аджагекар, Акшай; Скромный, Трэвис; Ты, Фэнци (2020-01-04). «Стратегии гибридного решения на основе квантовых вычислений для крупномасштабных задач дискретно-непрерывной оптимизации» . Компьютеры и химическая инженерия . 132 : 106630. DOI : 10.1016 / j.compchemeng.2019.106630 . ISSN 0098-1354 . 

Дальнейшее чтение [ править ]

  • Венегас-Андрака, Сальвадор, Э .; Крус-Сантос, Уильям; МакГеоч, Кэтрин; Ланзагорта, Марко (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 . Cite journal requires |journal= (help); Отсутствует или пусто |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 . Cite journal requires |journal= (help).
  • А. Датта, Г. Эппли, Б. К. Чакрабарти, У. Дивакаран, Т. Ф. Розенбаум и Д. Сен, «Квантовые фазовые переходы в моделях поперечного спина: от статистической физики к квантовой информации» , Издательство Кембриджского университета, Кембридж и Дели (2015).
  • С. Танака, Р. Тамура и Б.К. Чакрабарти, Квантовые спиновые стекла, отжиг и вычисления , Cambridge University Press, Кембридж и Дели (2017).
  • Индийская ассоциация научных новостей, специальный выпуск журнала «Наука и культура» о «Квантовом скачке в вычислениях» , Vol. 85 (5-6), май-июнь (2019)