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

Тип квантовой обработки информации

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

Описание

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

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

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

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

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

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

${\displaystyle 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}}$

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

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

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

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

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

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

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

где — удовлетворяющий гамильтониан предложения C. ${\displaystyle H_{P,C}}$

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

${\displaystyle 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 рассмотрим:

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

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

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

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

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

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

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

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

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

Вопрос о том, предлагают ли процессоры D-Wave ускорение по сравнению с классическим процессором, до сих пор остается без ответа. Тесты, проведенные исследователями в Лаборатории квантового искусственного интеллекта ( NASA ), USC , ETH Zurich и Google, показывают, что по состоянию на 2015 год нет никаких доказательств квантового преимущества. ^{[17] [18] [19]}

Примечания

1. Фархи, Э.; Голдстоун, Джеффри ; Гутманн, С.; Сипсер, М. (2000). «Квантовые вычисления с помощью адиабатической эволюции». arXiv : quant-ph/0001106v1 .
2. Кадоваки, Т.; Нишимори, Х. (1 ноября 1998 г.). "Квантовый отжиг в поперечной модели Изинга". Physical Review E. 58 ( 5): 5355. arXiv : cond-mat/9804280 . Bibcode : 1998PhRvE..58.5355K. doi : 10.1103/PhysRevE.58.5355. S2CID  36114913.
3. Finilla, AB; Gomez, MA; Sebenik, C.; Doll, DJ (18 марта 1994 г.). «Квантовый отжиг: новый метод минимизации многомерных функций». Chemical Physics Letters . 219 (5): 343–348. arXiv : chem-ph/9404003 . Bibcode : 1994CPL...219..343F. doi : 10.1016/0009-2614(94)00117-0. S2CID  97302385.
4. Санторо, GE; Тосатти, E. (8 сентября 2006 г.). «Оптимизация с использованием квантовой механики: квантовый отжиг через адиабатическую эволюцию». Journal of Physics A. 39 ( 36): R393. Bibcode : 2006JPhA...39R.393S. doi : 10.1088/0305-4470/39/36/R01. S2CID  116931586.
5. Das, A.; Chakrabarti, BK (5 сентября 2008 г.). "Colloquium: Quantum annealing and analog quantum computing". Reviews of Modern Physics . 80 (3): 1061. arXiv : 0801.2193 . Bibcode : 2008RvMP...80.1061D. doi : 10.1103/RevModPhys.80.1061. S2CID  14255125.
6. Ааронов, Дорит ; ван Дам, Вим; Кемпе, Джулия ; Ландау, Зеф; Ллойд, Сет (1 апреля 2007 г.). «Адиабатическое квантовое вычисление эквивалентно стандартному квантовому вычислению». SIAM Journal on Computing . 37 : 166. arXiv : quant-ph/0405098 . doi :10.1137/s0097539705447323.
7. Ван Дам, Вим; Ван Моска, Мишель; Вазирани, Умеш. «Насколько мощны адиабатические квантовые вычисления?». Труды 42-го ежегодного симпозиума по основам компьютерной науки : 279.
8. Kempe, J. ; Kitaev, A.; Regev, O. (27 июля 2006 г.). «Сложность локальной гамильтоновой проблемы». SIAM Journal on Computing . 35 (5): 1070–1097. arXiv : quant-ph/0406180v2 . doi :10.1137/S0097539704445226. ISSN  1095-7111.
9. Biamonte, JD; Love, PJ (28 июля 2008 г.). "Реализуемые гамильтонианы для универсальных адиабатических квантовых компьютеров". Physical Review A. 78 ( 1): 012352. arXiv : 0704.1287 . Bibcode : 2008PhRvA..78a2352B. doi : 10.1103/PhysRevA.78.012352. S2CID  9859204.
10. Оливейра, Р.; Терхал, Б. М. (1 ноября 2008 г.). «Сложность квантовых спиновых систем на двумерной квадратной решетке». Квантовая информация и вычисления . 8 (10): 0900–0924. arXiv : quant-ph/0504050 . Bibcode : 2005quant.ph..4050O. doi : 10.26421/QIC8.10-2. S2CID  3262293.
11. Ахаронов, Д.; Готтесман, Д.; Ирани, С.; Кемпе, Дж. (1 апреля 2009 г.). «Мощность квантовых систем на линии». Communications in Mathematical Physics . 287 (1): 41–65. arXiv : 0705.4077 . Bibcode :2009CMaPh.287...41A. doi :10.1007/s00220-008-0710-3. S2CID  1916001.
12. Фархи, Эдвард; Голдстоун, Джеффри; Гутманн, Сэм; Сипсер, Майкл (28 января 2000 г.). «Квантовые вычисления с помощью адиабатической эволюции». arXiv : quant-ph/0001106 .
13. Збинден, Стефани (15 июня 2020 г.). «Внедрение алгоритмов для квантовых отжигателей с топологиями соединений Chimera и Pegasus». Высокопроизводительные вычисления . Конспект лекций по информатике. Том 12151. С. 187–206. doi : 10.1007/978-3-030-50743-5_10 . ISBN 978-3-030-50742-8.
14. Джонсон, М.; Амин, М. (11 мая 2011 г.). «Квантовый отжиг с изготовленными спинами». Nature . 473 (7346): 194–198. Bibcode :2011Natur.473..194J. doi :10.1038/nature10012. PMID  21562559. S2CID  205224761 . Получено 12 февраля 2021 г. Некоторые из авторов являются сотрудниками D-Wave Systems Inc.
15. Campbell, Macgregor (1 июня 2011 г.). «Квантовый компьютер продан высокопоставленному клиенту». New Scientist . Получено 12 февраля 2021 г.
16. Джонс, Никола (20 июня 2013 г.). «Вычисления: квантовая компания». Nature . 498 (7454): 286–288. Bibcode :2013Natur.498..286J. doi : 10.1038/498286a . PMID  23783610.
17. Boixo, S.; Rønnow, TF; Isakov, SV; Wang, Z.; Wecker, D.; Lidar, DA; Martinis, JM; Troyer, M. (28 февраля 2014 г.). «Доказательства квантового отжига с более чем сотней кубитов». Nature Physics . 10 (3): 218–224. arXiv : 1304.4595 . Bibcode :2014NatPh..10..218B. doi :10.1038/nphys2900. S2CID  8031023.
18. Ronnow, TF; Wang, Z.; Job, J.; Boixo, S.; Isakov, SV; Wecker, D.; Martinis, JM; Lidar, DA; Troyer, M. (25 июля 2014 г.). «Определение и обнаружение квантового ускорения». Science . 345 (6195): 420–424. arXiv : 1401.2910 . Bibcode :2014Sci...345..420R. doi :10.1126/science.1252319. PMID  25061205. S2CID  5596838.
19. Venturelli, D.; Mandra, S.; Knysh, S.; O'Gorman, B.; Biswas, R.; Smelyanskiy, V. (18 сентября 2015 г.). "Quantum Optimization of Fully Connected Spin Glasses". Physical Review X . 5 (3): 031040. arXiv : 1406.7553 . Bibcode :2015PhRvX...5c1040V. doi :10.1103/PhysRevX.5.031040. S2CID  118622447.