Квантовая прогулка

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

Как и классические случайные блуждания, квантовые блуждания допускают формулировки как в дискретном, так и в непрерывном времени . ^[1]

Мотивация

Квантовые блуждания мотивированы широким использованием классических случайных блужданий при разработке рандомизированных алгоритмов и являются частью нескольких квантовых алгоритмов . Для некоторых пророческих задач квантовые блуждания обеспечивают экспоненциальное ускорение по сравнению с любым классическим алгоритмом. ^[2]^[3] Квантовые блуждания также дают полиномиальное ускорение по сравнению с классическими алгоритмами для многих практических задач, таких как проблема различимости элементов . ^[4] треугольника задача нахождения , ^[5] и оценка деревьев NAND. ^[6] Известный алгоритм поиска Гровера также можно рассматривать как алгоритм квантового блуждания.

Связь с классическими случайными блужданиями

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

Непрерывное время

Квантовые блуждания в непрерывном времени возникают, когда в уравнении Шрёдингера заменяется непрерывная пространственная область дискретным множеством. То есть вместо того, чтобы квантовая частица распространялась в континууме, мы ограничиваем набор возможных состояний положения набором вершин. $V$ какого-то графа $G=(V,E)$ которое может быть как конечным, так и счетным. При определенных условиях квантовые блуждания в непрерывном времени могут стать моделью универсальных квантовых вычислений . ^[7]

Связь с нерелятивистской динамикой Шредингера

Рассмотрим динамику нерелятивистской бесспиновой свободной квантовой частицы с массой $m$ распространяющийся в бесконечной одномерной пространственной области. Движение частицы полностью описывается ее волновой функцией $\psi :\mathbb {R} \times \mathbb {R} _{\geq 0}\to \mathbb {C}$ которое удовлетворяет одномерному уравнению Шредингера для свободных частиц

{\textbf {i}}\hbar {\frac {\partial \psi }{\partial t}}=-{\frac {\hbar ^{2}}{2m}}{\frac {\partial ^{2}\psi }{\partial x^{2}}}

где ${\textbf {i}}={\sqrt {-1}}$ и $\hbar$ – приведенная постоянная Планка. Теперь предположим, что дискретизирована только пространственная часть области: $\mathbb {R}$ заменяется на $\mathbb {Z} _{\Delta x}\equiv \{\ldots ,-2\,\Delta x,-\Delta x,0,\Delta x,2\,\Delta x,\ldots \}$ где $\Delta x$ — расстояние между пространственными местами, которые может занимать частица. Волновая функция становится картой $\psi :\mathbb {Z} _{\Delta x}\times \mathbb {R} _{\geq 0}\to \mathbb {C}$ а вторая пространственная частная производная становится дискретным лапласианом

{\frac {\partial ^{2}\psi }{\partial x^{2}}}\to {\frac {L_{\mathbb {Z} }\psi (j\,\Delta x,t)}{\Delta x^{2}}}\equiv {\frac {\psi \left((j+1)\,\Delta x,t\right)-2\psi \left(j\,\Delta x,t\right)+\psi \left((j-1)\,\Delta x,t\right)}{\Delta x^{2}}}

Уравнение эволюции квантового блуждания в непрерывном времени по $\mathbb {Z} _{\Delta x}$ таким образом

{\textbf {i}}{\frac {\partial \psi }{\partial t}}=-\omega _{\Delta x}L_{\mathbb {Z} }\psi

где $\omega _{\Delta x}\equiv \hbar /2m\,\Delta x^{2}$ является характеристической частотой. Эта конструкция естественным образом обобщается на случай, когда дискретизированная пространственная область представляет собой произвольный граф. $G=(V,E)$ и дискретный лапласиан $L_{\mathbb {Z} }$ заменяется графом Лапласа $L_{G}\equiv D_{G}-A_{G}$ где $D_{G}$ и $A_{G}$ – матрица степеней и матрица смежности соответственно. Обычным выбором графов, которые появляются при изучении квантовых блужданий в непрерывном времени, являются d -мерные решетки. $\mathbb {Z} ^{d}$ , графики циклов $\mathbb {Z} /N\mathbb {Z}$ , d -мерные дискретные торы $(\mathbb {Z} /N\mathbb {Z} )^{d}$ , d -мерный гиперкуб $\mathbb {Q} ^{d}$ и случайные графики.

Дискретное время

Квантовые блуждания в дискретном времени $\mathbb {Z}$

Эволюция квантового блуждания в дискретном времени определяется произведением двух унитарных операторов: (1) оператора «подбрасывания монеты» и (2) оператора условного сдвига, которые применяются неоднократно. Здесь поучителен следующий пример. ^[8] Представьте себе частицу со спином 1/2 степени свободы, распространяющуюся по линейному массиву дискретных узлов. Если число таких узлов счетно бесконечно, мы отождествляем пространство состояний с $\mathbb {Z}$ . Состояние частицы тогда можно описать состоянием продукта

|\Psi \rangle =|s\rangle \otimes |\psi \rangle

состоящее из внутреннего спинового состояния

|s\rangle \in {\mathcal {H}}_{C}=\left\{a_{\uparrow }|{\uparrow }\rangle +a_{\downarrow }|{\downarrow }\rangle :a_{\uparrow /\downarrow }\in \mathbb {C} \right\}

и состояние позиции

|\psi \rangle \in {\mathcal {H}}_{P}=\left\{\sum _{x\in \mathbb {Z} }\alpha _{x}|x\rangle :\sum _{x\in \mathbb {Z} }|\alpha _{x}|^{2}<\infty \right\}

где ${\mathcal {H}}_{C}=\mathbb {C} ^{2}$ это «пространство монет» и ${\mathcal {H}}_{P}=\ell ^{2}(\mathbb {Z} )$ — это пространство состояний физического квантового положения. Продукт $\otimes$ в этой настройке является произведением Кронекера (тензорным). Оператор условного сдвига для квантового блуждания по прямой имеет вид

S=|{\uparrow }\rangle \langle {\uparrow }|\otimes \sum \limits _{i}|i+1\rangle \langle i|+|{\downarrow }\rangle \langle {\downarrow }|\otimes \sum \limits _{i}|i-1\rangle \langle i|,

т.е. частица прыгает вправо, если она имеет вращение вверх, и влево, если оно имеет вращение вниз. Явно оператор условного сдвига действует на состояния продукта в соответствии с

S(|{\uparrow }\rangle \otimes |i\rangle )=|{\uparrow }\rangle \otimes |i+1\rangle

S(|{\downarrow }\rangle \otimes |i\rangle )=|{\downarrow }\rangle \otimes |i-1\rangle

Если мы сначала повернём спин с помощью некоторого унитарного преобразования $C:{\mathcal {H}}_{C}\to {\mathcal {H}}_{C}$ а затем применить $S$ , мы получим нетривиальное квантовое движение на $\mathbb {Z}$ . Популярным выбором для такого преобразования являются ворота Адамара. $C=H$ , который относительно стандартного спинового базиса z -компоненты имеет матричное представление

H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&\;\;1\\1&-1\end{pmatrix}}

Когда этот выбор делается для оператора подбрасывания монеты, сам оператор называется «монетой Адамара», а результирующее квантовое блуждание называется «блужданием Адамара». Если ходун инициализируется в начале координат и в состоянии раскрутки, один временной шаг прогулки Адамара $\mathbb {Z}$ является

|{\uparrow }\rangle \otimes |0\rangle \;\,{\overset {H}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle +|{\downarrow }\rangle )\otimes |0\rangle \;\,{\overset {S}{\longrightarrow }}\;\,{\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle \otimes |1\rangle +|{\downarrow }\rangle \otimes |{-1}\rangle ).

Измерение состояния системы в этой точке выявило бы вращение вверх в положении 1 или вращение вниз в положении -1, оба с вероятностью 1/2. Повторение процедуры соответствовало бы классическому простому случайному блужданию по $\mathbb {Z}$ . Чтобы наблюдать неклассическое движение, состояние в этой точке не измеряется (и, следовательно, не вызывает коллапс волновой функции). Вместо этого повторите процедуру вращения вращения с помощью оператора подбрасывания монеты и условного прыжка с помощью $S$ . Таким образом, квантовые корреляции сохраняются, и различные состояния положения могут мешать друг другу. Это дает совершенно другое распределение вероятностей, чем классическое случайное блуждание (распределение Гаусса), как показано на рисунке справа. Пространственно видно, что распределение не симметрично: даже несмотря на то, что монета Адамара дает как вверх, так и вниз с равной вероятностью, распределение имеет тенденцию смещаться вправо, когда начальный спин равен $|{\uparrow }\rangle$ . Эта асимметрия целиком обусловлена тем, что монета Адамара изображает $|{\uparrow }\rangle$ и $|{\downarrow }\rangle$ государство асимметрично. Симметричное распределение вероятностей возникает, если начальное состояние выбрано

|\Psi _{0}^{\text{symm}}\rangle ={\frac {1}{\sqrt {2}}}(|{\uparrow }\rangle -{\textbf {i}}|{\downarrow }\rangle )\otimes |0\rangle

Уравнение Дирака

Рассмотрим, что происходит, когда мы дискретизируем массивный оператор Дирака по одному пространственному измерению . В отсутствие массового термина мы имеем левых и правых. ^{[ нужны разъяснения ]} Их можно охарактеризовать внутренней степенью свободы , «вращением» или «монеткой». Когда мы включаем массовый член, это соответствует вращению в этом внутреннем «монетном» пространстве. Квантовое блуждание соответствует многократному повторению операторов сдвига и монеты.

Это очень похоже на Ричарда Фейнмана модель электрона в 1 (одном) пространственном и 1 (одном) временном измерениях. Он суммировал зигзагообразные пути: сегменты, движущиеся влево, соответствуют одному вращению (или монете), а сегменты, движущиеся вправо, — другому. см . в разделе «Шахматная доска Фейнмана» Более подробную информацию .

Вероятность перехода для одномерного квантового блуждания ведет себя подобно функциям Эрмита, которые (1) асимптотически осциллируют в классически разрешенной области,(2) аппроксимируется функцией Эйри вокруг стенки потенциала: ^{[ нужны разъяснения ]} и(3) экспоненциальное затухание в классически скрытой области. ^[9]

Реализация

Атомная решетка является ведущей квантовой платформой с точки зрения масштабируемости. Квантовое блуждание в дискретном времени в монетах и без них может быть реализовано в атомной решетке посредством дистанционно-селективного спин-обменного взаимодействия. ^[10] Примечательно, что платформа сохраняет связность пары сотен площадок и шагов в 1, 2 или 3 измерениях пространственного пространства. Дипольное взаимодействие на больших расстояниях позволяет создавать периодические граничные условия, облегчающие создание квантовой ямы на топологических поверхностях. ^[10]

См. также

Ссылки

^ Млодинов, Леонард; Брун, Тодд А. (30 апреля 2018 г.). «Дискретное пространство-время, квантовые блуждания и релятивистские волновые уравнения» . Физический обзор А. 97 (4): 042131. arXiv : 1802.03910 . дои : 10.1103/PhysRevA.97.042131 .
^ А. М. Чайлдс, Р. Клив , Э. Деотто, Э. Фархи , С. Гутманн и Д. А. Спилман , ЭкспоненциальныйАлгоритмическое ускорение с помощью квантового блуждания, Учеб. 35-й симпозиум ACM по теории вычислений, стр. 59–68, 2003 г., arXiv : quant-ph/0209131 .
^ А. М. Чайлдс, Л. Дж. Шульман и У. В. Вазирани , Квантовые алгоритмы для скрытых нелинейных структур, Proc. 48-й симпозиум IEEE по основам информатики, стр. 395–404, 2007 г., arXiv : 0705.2784 .
^ Андрис Амбайнис , Алгоритм квантового блуждания для определения различимости элементов, SIAM J. Comput. 37 (2007), вып. 1, 210–239, arXiv : quant-ph/0311001 , предварительная версия в FOCS 2004.
^ Ф. Маньез, М. Санта и М. Сегеди , Квантовые алгоритмы для задачи треугольника, Proc. 16-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 1109–1117, 2005 г., quant-ph/0310134.
^ Э. Фархи, Дж. Голдстоун и С. Гутманн, Квантовый алгоритм для гамильтонова дерева NAND, Теория вычислений 4 (2008), вып. 1, 169–190, квант-тел/0702144
^ Эндрю М. Чайлдс, «Универсальные вычисления с помощью квантовой прогулки» .
^ Кемпе, Джулия (1 июля 2003 г.). «Квантовые случайные блуждания – вводный обзор». Современная физика . 44 (4): 307–327. arXiv : Quant-ph/0303081 . Бибкод : 2003ConPh..44..307K . дои : 10.1080/00107151031000110776 . ISSN 0010-7514 . S2CID 17300331 .
^ Т. Сунада и Т. Тейт, Асимптотическое поведение квантовых блужданий по прямой, Журнал функционального анализа 262 (2012) 2608–2645
^ Перейти обратно: ^а ^б Хазали, Мохаммадсадек (3 марта 2022 г.). «Квантовое блуждание и топологические изоляторы Флоке в дискретном времени посредством дистанционно-селективного ридберговского взаимодействия» . Квантовый . 6 : 664. arXiv : 2101.11412 . Бибкод : 2022Количество...6..664K . doi : 10.22331/q-2022-03-03-664 . ISSN 2521-327X . S2CID 246635019 .

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

Джулия Кемпе (2003). «Квантовые случайные блуждания – вводный обзор». Современная физика . 44 (4): 307–327. arXiv : Quant-ph/0303081 . Бибкод : 2003ConPh..44..307K . дои : 10.1080/00107151031000110776 . S2CID 17300331 .
Андрис Амбайнис (2003). «Квантовые блуждания и их алгоритмические приложения». Международный журнал квантовой информации . 1 (4): 507–518. arXiv : Quant-ph/0403120 . дои : 10.1142/S0219749903000383 . S2CID 10324299 .
Санта, Миклош (2008). «Алгоритмы поиска на основе квантовых прогулок». Теория и приложения моделей вычислений . Конспекты лекций по информатике. Том. 4978. стр. 31–46. arXiv : 0808.0059 . дои : 10.1007/978-3-540-79228-4_3 . ISBN 978-3-540-79227-7 .
Сальвадор Э. Венегас-Андрака (2012). «Квантовые блуждания: всесторонний обзор». Квантовая обработка информации . 11 (5): 1015–1106. arXiv : 1201.4780 . дои : 10.1007/s11128-012-0432-5 . S2CID 27676690 .
Сальвадор Э. Венегас-Андрака (2008). Квантовые прогулки для ученых-компьютерщиков . Издательство Морган и Клейпул. ISBN 978-1598296563 .
Киа Манучехри, Цзинбо Ван (2014). Физическая реализация квантовых блужданий . Спрингер. ISBN 978-3-642-36014-5 .

Внешние ссылки

[1] Млодинов, Леонард; Брун, Тодд А. (30 апреля 2018 г.). «Дискретное пространство-время, квантовые блуждания и релятивистские волновые уравнения» . Физический обзор А. 97 (4): 042131. arXiv : 1802.03910 . дои : 10.1103/PhysRevA.97.042131 .

[2] А. М. Чайлдс, Р. Клив , Э. Деотто, Э. Фархи , С. Гутманн и Д. А. Спилман , ЭкспоненциальныйАлгоритмическое ускорение с помощью квантового блуждания, Учеб. 35-й симпозиум ACM по теории вычислений, стр. 59–68, 2003 г., arXiv : quant-ph/0209131 .

[3] А. М. Чайлдс, Л. Дж. Шульман и У. В. Вазирани , Квантовые алгоритмы для скрытых нелинейных структур, Proc. 48-й симпозиум IEEE по основам информатики, стр. 395–404, 2007 г., arXiv : 0705.2784 .

[4] Андрис Амбайнис , Алгоритм квантового блуждания для определения различимости элементов, SIAM J. Comput. 37 (2007), вып. 1, 210–239, arXiv : quant-ph/0311001 , предварительная версия в FOCS 2004.

[5] Ф. Маньез, М. Санта и М. Сегеди , Квантовые алгоритмы для задачи треугольника, Proc. 16-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 1109–1117, 2005 г., quant-ph/0310134.

[6] Э. Фархи, Дж. Голдстоун и С. Гутманн, Квантовый алгоритм для гамильтонова дерева NAND, Теория вычислений 4 (2008), вып. 1, 169–190, квант-тел/0702144

[7] Эндрю М. Чайлдс, «Универсальные вычисления с помощью квантовой прогулки» .

[8] Кемпе, Джулия (1 июля 2003 г.). «Квантовые случайные блуждания – вводный обзор». Современная физика . 44 (4): 307–327. arXiv : Quant-ph/0303081 . Бибкод : 2003ConPh..44..307K . дои : 10.1080/00107151031000110776 . ISSN 0010-7514 . S2CID 17300331 .

[9] Т. Сунада и Т. Тейт, Асимптотическое поведение квантовых блужданий по прямой, Журнал функционального анализа 262 (2012) 2608–2645

[:0-10] Перейти обратно: ^а ^б Хазали, Мохаммадсадек (3 марта 2022 г.). «Квантовое блуждание и топологические изоляторы Флоке в дискретном времени посредством дистанционно-селективного ридберговского взаимодействия» . Квантовый . 6 : 664. arXiv : 2101.11412 . Бибкод : 2022Количество...6..664K . doi : 10.22331/q-2022-03-03-664 . ISSN 2521-327X . S2CID 246635019 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]