Адиабатические квантовые вычисления

Адиабатические квантовые вычисления ( AQC ) — это форма квантовых вычислений , которая основана на адиабатической теореме для выполнения вычислений. ^[1] и тесно связано с квантовым отжигом . ^[2]^[3]^[4]^[5]

Описание [ править ]

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

Временная сложность адиабатического алгоритма — это время, необходимое для завершения адиабатической эволюции, которое зависит от разрыва в собственных значениях энергии (спектрального разрыва) гамильтониана. В частности, если система должна оставаться в основном состоянии, энергетическая щель между основным состоянием и первым возбужденным состоянием $H(t)$ обеспечивает верхнюю границу скорости, с которой гамильтониан может развиваться за время $t$ . ^[7] Когда спектральная щель мала, гамильтониан должен развиваться медленно. Время выполнения всего алгоритма может быть ограничено:

$T=O\left({\frac {1}{g_{min}^{2}}}\right)$

где $g_{min}$ – минимальная спектральная щель для $H(t)$ .

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

Результаты универсальности в адиабатической модели связаны с квантовой сложностью и QMA -трудными проблемами. k-локальный гамильтониан является QMA-полным при k ≥ 2. ^[8] Результаты QMA-твердости известны для физически реалистичных решетчатых моделей кубитов , таких как ^[9]

$H=\sum _{i}h_{i}Z_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}$

где $Z,X$ представляют матрицы Паули $\sigma _{z},\sigma _{x}$ . Такие модели используются для универсальных адиабатических квантовых вычислений. Гамильтонианы для QMA-полной задачи также можно ограничить действием на двумерную сетку кубитов. ^[10] или линия квантовых частиц с 12 состояниями на частицу. ^[11] Если окажется, что такие модели физически реализуемы, их тоже можно будет использовать для формирования строительных блоков универсального адиабатического квантового компьютера.

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

квантовые вычисления в выполнимости задачах Адиабатические

Адиабатические квантовые вычисления решают проблемы выполнимости и другие проблемы комбинаторного поиска. В частности, такого рода задачи ищут состояние, которое удовлетворяет $C_{1}\wedge C_{2}\wedge \cdots \wedge C_{M}$ . Это выражение содержит выполнимость предложений M, для которых предложение $C_{i}$ имеет значение True или False и может включать n бит. Каждый бит является переменной $x_{j}\in \{0,1\}$ такой, что $C_{i}$ является булевой функцией значения $x_{1},x_{2},\dots ,x_{n}$ . QAA решает такого рода проблемы, используя квантовую адиабатическую эволюцию. Он начинается с начального гамильтониана $H_{B}$ :

$H_{B}=H_{B_{1}}+H_{B_{2}}+\dots +H_{B_{M}}$

где $H_{B_{i}}$ показывает гамильтониан, соответствующий предложению $C_{i}$ . Обычно выбор $H_{B_{i}}$ не будет зависеть от разных предложений, поэтому имеет значение только общее количество раз, когда каждый бит задействован во всех предложениях. Далее он проходит адиабатическую эволюцию, заканчивающуюся проблемным гамильтонианом. $H_{P}$ :

$H_{P}=\sum \limits _{C}^{}H_{P,C}$

где $H_{P,C}$ является удовлетворяющим гамильтонианом пункта C.

Он имеет собственные значения:

$h_{C}(z_{1C},z_{2C}\dots z_{nC})={\begin{cases}0&{\mbox{clause }}C{\mbox{ satisfied}}\\1&{\mbox{clause }}C{\mbox{ violated}}\end{cases}}$

Для простого пути адиабатической эволюции со временем работы T рассмотрим:

$H(t)=(1-t/T)H_{B}+(t/T)H_{P}$

и пусть $s=t/T$ . Это приводит к:

${\tilde {H}}(s)=(1-s)H_{B}+sH_{P}$ , который является гамильтонианом адиабатической эволюции алгоритма.

В соответствии с адиабатической теоремой начнем с основного состояния гамильтониана $H_{B}$ вначале протекает адиабатический процесс и заканчивается в основном состоянии гамильтониана задачи $H_{P}$ .

Затем измерьте z-компоненту каждого из n спинов в конечном состоянии. Это создаст строку $z_{1},z_{2},\dots ,z_{n}$ что, скорее всего, является результатом проблемы выполнимости. Время выполнения T должно быть достаточно большим, чтобы гарантировать правильность результата. Согласно адиабатической теореме, T составляет около $\varepsilon /g_{\mathrm {min} }^{2}$ , где $g_{\mathrm {min} }=\min _{0\leq s\leq 1}(E_{1}(s)-E_{0}(s))$ — минимальная энергетическая щель между основным состоянием и первым возбужденным состоянием. ^[12]

вентилей на основе Сравнение с квантовыми вычислениями

Адиабатические квантовые вычисления эквивалентны по мощности стандартным квантовым вычислениям на основе вентилей, которые реализуют произвольные унитарные операции. Однако задача отображения на квантовых устройствах на основе вентилей существенно отличается от квантовых отжигов, поскольку логические переменные сопоставляются только с отдельными кубитами, а не с цепочками. ^[13]

процессоры D Wave - Квантовые

D -Wave One — устройство канадской компании D-Wave Systems , которая утверждает, что использует квантовый отжиг для решения задач оптимизации. ^[14]^[15] 25 мая 2011 года Lockheed-Martin приобрела D-Wave One примерно за 10 миллионов долларов США. ^[15] В мае 2013 года Google приобрела процессор D-Wave Two на 512 кубитов . ^[16]

Вопрос о том, обеспечивают ли процессоры D-Wave ускорение по сравнению с классическими процессорами, до сих пор остается без ответа. Тесты, проведенные исследователями из Лаборатории квантового искусственного интеллекта ( НАСА ), Университета Южной Калифорнии , ETH Zurich и Google, показывают, что по состоянию на 2015 год не существует никаких доказательств квантового преимущества. ^[17]^[18]^[19]

Примечания [ править ]

^ Фархи, Э.; Голдстоун, Джеффри ; Гутманн, С.; Сипсер, М. (2000). «Квантовые вычисления путем адиабатической эволюции». arXiv : Quant-ph/0001106v1 .
^ Кадоваки, Т.; Нисимори, Х. (1 ноября 1998 г.). «Квантовый отжиг в поперечной модели Изинга». Физический обзор E . 58 (5): 5355. arXiv : cond-mat/9804280 . Бибкод : 1998PhRvE..58.5355K . дои : 10.1103/PhysRevE.58.5355 . S2CID 36114913 .
^ Финилла, АБ; Гомес, Массачусетс; Себеник, К.; Кукла, диджей (18 марта 1994 г.). «Квантовый отжиг: новый метод минимизации многомерных функций». Письма по химической физике . 219 (5): 343–348. arXiv : chem-ph/9404003 . Бибкод : 1994CPL...219..343F . дои : 10.1016/0009-2614(94)00117-0 . S2CID 97302385 .
^ Санторо, GE; Тосатти, Э. (8 сентября 2006 г.). «Оптимизация с использованием квантовой механики: квантовый отжиг посредством адиабатической эволюции». Журнал физики А. 39 (36): 393 ранда. Бибкод : 2006JPhA...39R.393S . дои : 10.1088/0305-4470/39/36/R01 . S2CID 116931586 .
^ Дас, А.; Чакрабарти, Б.К. (5 сентября 2008 г.). «Коллоквиум: квантовый отжиг и аналоговые квантовые вычисления». Обзоры современной физики . 80 (3): 1061. arXiv : 0801.2193 . Бибкод : 2008РвМП...80.1061Д . дои : 10.1103/RevModPhys.80.1061 . S2CID 14255125 .
^ Ааронов, Дорит ; ван Дам, Вим; Кемпе, Джулия ; Ландау, Зеф; Ллойд, Сет (1 апреля 2007 г.). «Адиабатические квантовые вычисления эквивалентны стандартным квантовым вычислениям». SIAM Journal по вычислительной технике . 37 : 166. arXiv : quant-ph/0405098 . дои : 10.1137/s0097539705447323 .
^ ван Дам, Вим; ван Моска, Мишель; Вазирани, Умеш. «Насколько мощны адиабатические квантовые вычисления?». Материалы 42-го ежегодного симпозиума по основам информатики : 279.
^ Кемпе, Дж .; Китаев А.; Регев О. (27 июля 2006 г.). «Сложность локальной гамильтоновой проблемы». SIAM Journal по вычислительной технике . 35 (5): 1070–1097. arXiv : Quant-ph/0406180v2 . дои : 10.1137/S0097539704445226 . ISSN 1095-7111 .
^ Биамонте, доктор медицинских наук; Лав, Пи Джей (28 июля 2008 г.). «Реализуемые гамильтонианы для универсальных адиабатических квантовых компьютеров». Физический обзор А. 78 (1): 012352. arXiv : 0704.1287 . Бибкод : 2008PhRvA..78a2352B . дои : 10.1103/PhysRevA.78.012352 . S2CID 9859204 .
^ Оливейра, Р.; Терхал, Б.М. (1 ноября 2008 г.). «Сложность квантовых спиновых систем на двумерной квадратной решетке». Квантовая информация и вычисления . 8 (10): 09:00–09:24. arXiv : Quant-ph/0504050 . Бибкод : 2005quant.ph..4050O . дои : 10.26421/QIC8.10-2 . S2CID 3262293 .
^ Ахаронов Д.; Готтесман, Д.; Ирани, С.; Кемпе, Дж. (1 апреля 2009 г.). «Сила квантовых систем на линии». Связь в математической физике . 287 (1): 41–65. arXiv : 0705.4077 . Бибкод : 2009CMaPh.287...41A . дои : 10.1007/s00220-008-0710-3 . S2CID 1916001 .
^ Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм; Сипсер, Майкл (28 января 2000 г.). «Квантовые вычисления путем адиабатической эволюции». arXiv : Quant-ph/0001106 .
^ Збинден, Стефани (15 июня 2020 г.). «Алгоритмы внедрения квантовых отжигателей с топологиями соединения Химера и Пегас». Высокопроизводительные вычисления . Конспекты лекций по информатике. Том. 12151. стр. 187–206. дои : 10.1007/978-3-030-50743-5_10 . ISBN 978-3-030-50742-8 .
^ Джонсон, М.; Амин, М. (11 мая 2011 г.). «Квантовый отжиг с искусственными спинами» . Природа . 473 (7346): 194–198. Бибкод : 2011Natur.473..194J . дои : 10.1038/nature10012 . ПМИД 21562559 . S2CID 205224761 . Проверено 12 февраля 2021 г. Некоторые из авторов являются сотрудниками D-Wave Systems Inc.
^ Jump up to: Перейти обратно: ^а ^б Кэмпбелл, Макгрегор (1 июня 2011 г.). «Квантовый компьютер продан высокопоставленному клиенту» . Новый учёный . Проверено 12 февраля 2021 г.
^ Джонс, Никола (20 июня 2013 г.). «Вычисления: квантовая компания» . Природа . 498 (7454): 286–288. Бибкод : 2013Natur.498..286J . дои : 10.1038/498286a . ПМИД 23783610 .
^ Бойшо, С.; Рённов, ТФ; Исаков С.В.; Ван, З.; Векер, Д.; Лидар, ДА; Мартинис, Дж. М.; Тройер, М. (28 февраля 2014 г.). «Доказательства квантового отжига с более чем ста кубитами». Физика природы . 10 (3): 218–224. arXiv : 1304.4595 . Бибкод : 2014NatPh..10..218B . дои : 10.1038/nphys2900 . S2CID 8031023 .
^ Роннов, Т.Ф.; Ван, З.; Джоб, Дж.; Бойшо, С.; Исаков С.В.; Векер, Д.; Мартинис, Дж. М.; Лидар, ДА; Тройер, М. (25 июля 2014 г.). «Определение и обнаружение квантового ускорения». Наука . 345 (6195): 420–424. arXiv : 1401.2910 . Бибкод : 2014Sci...345..420R . дои : 10.1126/science.1252319 . ПМИД 25061205 . S2CID 5596838 .
^ Вентурелли, Д.; Мандра, С.; Кныш, С.; О'Горман, Б.; Бисвас, Р.; Смелянский В. (18 сентября 2015 г.). «Квантовая оптимизация полносвязных спиновых стекол». Физический обзор X . 5 (3): 031040. arXiv : 1406.7553 . Бибкод : 2015PhRvX...5c1040V . дои : 10.1103/PhysRevX.5.031040 . S2CID 118622447 .

[Farhi2000-1] Фархи, Э.; Голдстоун, Джеффри ; Гутманн, С.; Сипсер, М. (2000). «Квантовые вычисления путем адиабатической эволюции». arXiv : Quant-ph/0001106v1 .

[2] Кадоваки, Т.; Нисимори, Х. (1 ноября 1998 г.). «Квантовый отжиг в поперечной модели Изинга». Физический обзор E . 58 (5): 5355. arXiv : cond-mat/9804280 . Бибкод : 1998PhRvE..58.5355K . дои : 10.1103/PhysRevE.58.5355 . S2CID 36114913 .

[3] Финилла, АБ; Гомес, Массачусетс; Себеник, К.; Кукла, диджей (18 марта 1994 г.). «Квантовый отжиг: новый метод минимизации многомерных функций». Письма по химической физике . 219 (5): 343–348. arXiv : chem-ph/9404003 . Бибкод : 1994CPL...219..343F . дои : 10.1016/0009-2614(94)00117-0 . S2CID 97302385 .

[4] Санторо, GE; Тосатти, Э. (8 сентября 2006 г.). «Оптимизация с использованием квантовой механики: квантовый отжиг посредством адиабатической эволюции». Журнал физики А. 39 (36): 393 ранда. Бибкод : 2006JPhA...39R.393S . дои : 10.1088/0305-4470/39/36/R01 . S2CID 116931586 .

[5] Дас, А.; Чакрабарти, Б.К. (5 сентября 2008 г.). «Коллоквиум: квантовый отжиг и аналоговые квантовые вычисления». Обзоры современной физики . 80 (3): 1061. arXiv : 0801.2193 . Бибкод : 2008РвМП...80.1061Д . дои : 10.1103/RevModPhys.80.1061 . S2CID 14255125 .

[6] Ааронов, Дорит ; ван Дам, Вим; Кемпе, Джулия ; Ландау, Зеф; Ллойд, Сет (1 апреля 2007 г.). «Адиабатические квантовые вычисления эквивалентны стандартным квантовым вычислениям». SIAM Journal по вычислительной технике . 37 : 166. arXiv : quant-ph/0405098 . дои : 10.1137/s0097539705447323 .

[7] ван Дам, Вим; ван Моска, Мишель; Вазирани, Умеш. «Насколько мощны адиабатические квантовые вычисления?». Материалы 42-го ежегодного симпозиума по основам информатики : 279.

[8] Кемпе, Дж .; Китаев А.; Регев О. (27 июля 2006 г.). «Сложность локальной гамильтоновой проблемы». SIAM Journal по вычислительной технике . 35 (5): 1070–1097. arXiv : Quant-ph/0406180v2 . дои : 10.1137/S0097539704445226 . ISSN 1095-7111 .

[9] Биамонте, доктор медицинских наук; Лав, Пи Джей (28 июля 2008 г.). «Реализуемые гамильтонианы для универсальных адиабатических квантовых компьютеров». Физический обзор А. 78 (1): 012352. arXiv : 0704.1287 . Бибкод : 2008PhRvA..78a2352B . дои : 10.1103/PhysRevA.78.012352 . S2CID 9859204 .

[10] Оливейра, Р.; Терхал, Б.М. (1 ноября 2008 г.). «Сложность квантовых спиновых систем на двумерной квадратной решетке». Квантовая информация и вычисления . 8 (10): 09:00–09:24. arXiv : Quant-ph/0504050 . Бибкод : 2005quant.ph..4050O . дои : 10.26421/QIC8.10-2 . S2CID 3262293 .

[11] Ахаронов Д.; Готтесман, Д.; Ирани, С.; Кемпе, Дж. (1 апреля 2009 г.). «Сила квантовых систем на линии». Связь в математической физике . 287 (1): 41–65. arXiv : 0705.4077 . Бибкод : 2009CMaPh.287...41A . дои : 10.1007/s00220-008-0710-3 . S2CID 1916001 .

[12] Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм; Сипсер, Майкл (28 января 2000 г.). «Квантовые вычисления путем адиабатической эволюции». arXiv : Quant-ph/0001106 .

[13] Збинден, Стефани (15 июня 2020 г.). «Алгоритмы внедрения квантовых отжигателей с топологиями соединения Химера и Пегас». Высокопроизводительные вычисления . Конспекты лекций по информатике. Том. 12151. стр. 187–206. дои : 10.1007/978-3-030-50743-5_10 . ISBN 978-3-030-50742-8 .

[14] Джонсон, М.; Амин, М. (11 мая 2011 г.). «Квантовый отжиг с искусственными спинами» . Природа . 473 (7346): 194–198. Бибкод : 2011Natur.473..194J . дои : 10.1038/nature10012 . ПМИД 21562559 . S2CID 205224761 . Проверено 12 февраля 2021 г. Некоторые из авторов являются сотрудниками D-Wave Systems Inc.

[quantanneal-15] Jump up to: Перейти обратно: ^а ^б Кэмпбелл, Макгрегор (1 июня 2011 г.). «Квантовый компьютер продан высокопоставленному клиенту» . Новый учёный . Проверено 12 февраля 2021 г.

[16] Джонс, Никола (20 июня 2013 г.). «Вычисления: квантовая компания» . Природа . 498 (7454): 286–288. Бибкод : 2013Natur.498..286J . дои : 10.1038/498286a . ПМИД 23783610 .

[17] Бойшо, С.; Рённов, ТФ; Исаков С.В.; Ван, З.; Векер, Д.; Лидар, ДА; Мартинис, Дж. М.; Тройер, М. (28 февраля 2014 г.). «Доказательства квантового отжига с более чем ста кубитами». Физика природы . 10 (3): 218–224. arXiv : 1304.4595 . Бибкод : 2014NatPh..10..218B . дои : 10.1038/nphys2900 . S2CID 8031023 .

[18] Роннов, Т.Ф.; Ван, З.; Джоб, Дж.; Бойшо, С.; Исаков С.В.; Векер, Д.; Мартинис, Дж. М.; Лидар, ДА; Тройер, М. (25 июля 2014 г.). «Определение и обнаружение квантового ускорения». Наука . 345 (6195): 420–424. arXiv : 1401.2910 . Бибкод : 2014Sci...345..420R . дои : 10.1126/science.1252319 . ПМИД 25061205 . S2CID 5596838 .

[19] Вентурелли, Д.; Мандра, С.; Кныш, С.; О'Горман, Б.; Бисвас, Р.; Смелянский В. (18 сентября 2015 г.). «Квантовая оптимизация полносвязных спиновых стекол». Физический обзор X . 5 (3): 031040. arXiv : 1406.7553 . Бибкод : 2015PhRvX...5c1040V . дои : 10.1103/PhysRevX.5.031040 . S2CID 118622447 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]