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

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

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

Мотивация

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

Отношение к классическим случайным блужданиям

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

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

Основная статья: Квантовый ход в непрерывном времени

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

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

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

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

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

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

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

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

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

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

Квантовые прогулки в дискретном времени ${\displaystyle \mathbb {Z} }$

Распределение вероятностей в результате одномерных случайных блужданий с дискретным временем. Квантовая прогулка, созданная с помощью Монета Адамара нанесен (красный) против классической прогулки (синий) через 50 временных шагов.

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

${\displaystyle |\Psi \rangle =|s\rangle \otimes |\psi \rangle }$

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

${\displaystyle |s\rangle \in {\mathcal {H}}_{C}=\{|{\uparrow }\rangle ,|{\downarrow }\rangle \}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Это очень похоже на Ричард Фейнман Модель электрона в 1 (одном) пространственном и 1 (одном) временном измерении. Он суммировал зигзагообразные траектории, при этом сегменты, движущиеся влево, соответствуют одному вращению (или монете), а сегменты вправо - другому. Увидеть Шахматная доска Фейнмана Больше подробностей.

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

Смотрите также

• Формулировка интеграла по путям

использованная литература

1. А. М. Чайлдс, Р. Клив, Э. Деотто, Э. Фархи, С. Гутманн и Д. А. Шпильман, Экспоненциально-алгоритмическое ускорение квантовым блужданием, Proc. 35-й симпозиум ACM по теории вычислений, стр. 59–68, 2003 г., Quant-ph / 0209131.
2. А. М. Чайлдс, Л. Дж. Шульман и У. В. Вазирани, Квантовые алгоритмы для скрытых нелинейных структур, Тр. 48-й симпозиум IEEE по основам компьютерных наук, стр. 395–404, 2007 г., arXiv: 0705.2784.
3. Андрис Амбайнис, Алгоритм квантового блуждания для определения различимости элементов, SIAM J. Comput. 37 (2007), нет. 1, 210–239, г. arXiv:Quant-ph / 0311001, предварительная версия в FOCS 2004.
4. Ф. Магниес, М. Санта и М. Сегеди, Квантовые алгоритмы для задачи треугольника, Тр. 16-й симпозиум ACM-SIAM по дискретным алгоритмам, стр. 1109–1117, 2005 г., Quant-ph / 0310134.
5. Э. Фархи, Дж. Голдстоун, и С. Гутманн, Квантовый алгоритм для гамильтонова дерева И-НЕ, Теория вычислений 4 (2008), вып. 1, 169–190, Quant-ph / 0702144
6. Эндрю М. Чайлдс, «Универсальные вычисления квантовым ходом».
7. Кемпе, Юлия (1 июля 2003 г.). «Квантовые случайные блуждания - вводный обзор». Современная физика. 44 (4): 307–327. arXiv:Quant-ph / 0303081. Bibcode:2003ConPh..44..307K. Дои:10.1080/00107151031000110776. ISSN  0010-7514.
8. Т. Сунада и Т. Тейт, Асимптотическое поведение квантовых блужданий на линии, Journal of Functional Analysis 262 (2012) 2608–2645.

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

• Юлия Кемпе (2003). «Квантовые случайные блуждания - вводный обзор». Современная физика. 44 (4): 307–327. arXiv:Quant-ph / 0303081. Bibcode:2003ConPh..44..307K. Дои:10.1080/00107151031000110776.
• Андрис Амбайнис (2003). «Квантовые прогулки и их алгоритмические приложения». Международный журнал квантовой информации. 1 (4): 507–518. arXiv:Quant-ph / 0403120. Дои:10.1142 / S0219749903000383.
• Миклош Санта (2008). «Алгоритмы поиска на основе квантового блуждания». Теория и приложения моделей вычислений (TAMC), Сиань, апрель, LNCS 4978. 5 (8): 31–46. arXiv:0808.0059. Bibcode:2008arXiv0808.0059S.
• Сальвадор Э. Венегас-Андрака (2012). «Квантовые прогулки: всесторонний обзор». Квантовая обработка информации. 11 (5): 1015–1106. arXiv:1201.4780. Дои:10.1007 / s11128-012-0432-5.
• Сальвадор Э. Венегас-Андрака. «Квантовые прогулки для компьютерных ученых». Получено 16 октября 2008.

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

• Международный семинар по математическим и физическим основам квантового блуждания в дискретном времени
• Квантовая прогулка