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

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

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

Мотивация [ править ]

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

Отношение к классическим случайным блужданиям [ править ]

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

Непрерывное время [ править ]

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

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

Рассмотрим динамику нерелятивистской бесспиновой квантовой частицы с массой, распространяющейся в бесконечной одномерной пространственной области. Движение частицы полностью описывается ее волновой функцией, которая удовлетворяет одномерному уравнению Шредингера для свободной частицы${\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 }$

где - характерная частота. Эта конструкция , естественно , обобщается на случай , что дискретизируется пространственная область представляет собой произвольный граф , а дискретный лапласиан заменяются граф лапласиана , где и являются матрица степени и матрица смежности , соответственно. При изучении квантовых блужданий с непрерывным временем обычно выбирают графы : d -мерные решетки , циклические графы , d -мерные дискретные торы , d -мерный гиперкуб и случайные графы.${\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}}$${\displaystyle \mathbb {Z} ^{d}}$${\displaystyle \mathbb {Z} /N\mathbb {Z} }$${\displaystyle (\mathbb {Z} /N\mathbb {Z} )^{d}}$${\displaystyle \mathbb {Q} ^{d}}$

Дискретное время [ править ]

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Декабрь 2009 г. )

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

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

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

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

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

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

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

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

${\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]

См. Также [ править ]

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

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

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

Внешние ссылки [ править ]

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