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

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

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

Мотивация

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

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

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

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

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

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

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

я ℏ ∂ ψ ∂ т = − ℏ 2 2 м ∂ 2 ψ ∂ х 2 {\displaystyle {\textbf {i}}\hbar {\frac {\partial \psi }{\partial t}}=-{\frac {\hbar ^{2}}{2m}}{\frac {\partial ^{2}\psi }{\partial x^{2}}}}

где и — приведенная постоянная Планка. Теперь предположим, что дискретизирована только пространственная часть домена, заменяемая на где — расстояние между пространственными позициями, которые может занимать частица. Волновая функция становится картой , а вторая пространственная частная производная становится дискретным лапласианом я = − 1 {\displaystyle {\textbf {i}}={\sqrt {-1}}} ℏ {\displaystyle \hbar} Р {\displaystyle \mathbb {R} } З Δ х ≡ { … , − 2 Δ х , − Δ х , 0 , Δ х , 2 Δ х , … } {\displaystyle \mathbb {Z} _{\Delta x}\equiv \{\ldots ,-2\,\Delta x,-\Delta x,0,\Delta x,2\,\Delta x,\ldots \}} Δ х {\displaystyle \Дельта х} ψ : З Δ х × Р ≥ 0 → С {\displaystyle \psi :\mathbb {Z} _{\Delta x}\times \mathbb {R} _{\geq 0}\to \mathbb {C} }

∂ 2 ψ ∂ х 2 → Л З ψ ( дж Δ х , т ) Δ х 2 ≡ ψ ( ( дж + 1 ) Δ х , т ) − 2 ψ ( дж Δ х , т ) + ψ ( ( дж − 1 ) Δ х , т ) Δ х 2 {\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- мерный гиперкуб и случайные графы. ω Δ х ≡ ℏ / 2 м Δ х 2 {\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}}

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

Дискретные квантовые блуждания по времени З {\displaystyle \mathbb {Z} }

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

Эволюция квантового блуждания в дискретном времени задается произведением двух унитарных операторов: (1) оператора «подбрасывания монеты» и (2) оператора условного сдвига, которые применяются многократно. Следующий пример здесь поучителен. [8] Представьте себе частицу со степенью свободы спина 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\}}

и положение государства

| ψ ⟩ ∈ ЧАС П = { ∑ х ∈ З α х | х ⟩ : ∑ х ∈ З | α х | 2 < ∞ } {\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\}}

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

С = | ↑ ⟩ ⟨ ↑ | ⊗ ∑ я | я + 1 ⟩ ⟨ я | + | ↓ ⟩ ⟨ ↓ | ⊗ ∑ я | я − 1 ⟩ ⟨ я | , {\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|,}

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

С ( | ↑ ⟩ ⊗ | я ⟩ ) = | ↑ ⟩ ⊗ | я + 1 ⟩ {\displaystyle S(|{\uparrow}\rangle \otimes |i\rangle) = |{\uparrow }\rangle \otimes |i+1\rangle }
С ( | ↓ ⟩ ⊗ | я ⟩ ) = | ↓ ⟩ ⊗ | я − 1 ⟩ {\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 С=Н}

ЧАС = 1 2 ( 1 1 1 − 1 ) {\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&\;\;1\\1&-1\end{pmatrix}}}

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

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

| Ψ 0 symm ⟩ = 1 2 ( | ↑ ⟩ − i | ↓ ⟩ ) ⊗ | 0 ⟩ {\displaystyle |\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]

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

Ссылки

  1. ^ Млодинов, Леонард; Брун, Тодд А. (30 апреля 2018 г.). «Дискретное пространство-время, квантовые прогулки и релятивистские волновые уравнения». Physical Review A. 97 ( 4): 042131. arXiv : 1802.03910 . doi : 10.1103/PhysRevA.97.042131.
  2. ^ AM Childs, R. Cleve , E. Deotto, E. Farhi , S. Gutmann и DA Spielman , Экспоненциальное алгоритмическое ускорение с помощью квантового блуждания, Proc. 35th ACM Symposium on Theory of Computing, стр. 59–68, 2003, arXiv :quant-ph/0209131.
  3. ^ AM Childs, LJ Schulman и UV Vazirani , Квантовые алгоритмы для скрытых нелинейных структур, Труды 48-го симпозиума IEEE по основам компьютерной науки, стр. 395–404, 2007, arXiv :0705.2784.
  4. ^ Андрис Амбаинис , Алгоритм квантового блуждания для различимости элементов, SIAM J. Comput. 37 (2007), № 1, 210–239, arXiv :quant-ph/0311001, предварительная версия в FOCS 2004.
  5. ^ Ф. Магниес, М. Санта и М. Сегеди , Квантовые алгоритмы для задачи треугольника, Труды 16-го симпозиума ACM-SIAM по дискретным алгоритмам, стр. 1109–1117, 2005, quant-ph/0310134.
  6. ^ E. Farhi, J. Goldstone и S. Gutmann, Квантовый алгоритм для гамильтонова дерева NAND, Теория вычислений 4 (2008), № 1, 169–190, quant-ph/0702144
  7. ^ Эндрю М. Чайлдс, «Универсальные вычисления с помощью квантового блуждания».
  8. ^ Кемпе, Джулия (1 июля 2003 г.). «Квантовые случайные блуждания – вводный обзор». Contemporary Physics . 44 (4): 307–327. arXiv : quant-ph/0303081 . Bibcode : 2003ConPh..44..307K. doi : 10.1080/00107151031000110776. ISSN  0010-7514. S2CID  17300331.
  9. ^ Т. Сунады и Т. Тейта, Асимптотическое поведение квантовых блужданий на линии, Журнал функционального анализа 262 (2012) 2608–2645
  10. ^ ab Khazali, Mohammadsadegh (3 марта 2022 г.). "Дискретное время квантового блуждания и топологические изоляторы Флоке с помощью дистанционного селективного взаимодействия Ридберга". Quantum . 6 : 664. arXiv : 2101.11412 . Bibcode : 2022Quant...6..664K. doi : 10.22331/q-2022-03-03-664 . ISSN  2521-327X. S2CID  246635019.

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

  • Julia Kempe (2003). «Квантовые случайные блуждания – вводный обзор». Contemporary Physics . 44 (4): 307–327. arXiv : quant-ph/0303081 . Bibcode : 2003ConPh..44..307K. doi : 10.1080/00107151031000110776. S2CID  17300331.
  • Андрис Амбаинис (2003). «Квантовые прогулки и их алгоритмические приложения». Международный журнал квантовой информации . 1 (4): 507–518. arXiv : quant-ph/0403120 . doi :10.1142/S0219749903000383. S2CID  10324299.
  • Санта, Миклош (2008). «Квантовые алгоритмы поиска на основе обхода». Теория и применение моделей вычислений . Конспект лекций по информатике. Том 4978. С. 31–46. arXiv : 0808.0059 . doi :10.1007/978-3-540-79228-4_3. ISBN 978-3-540-79227-7.
  • Сальвадор Э. Венегас-Андрака (2012). «Квантовые прогулки: всесторонний обзор». Квантовая обработка информации . 11 (5): 1015–1106. arXiv : 1201.4780 . doi :10.1007/s11128-012-0432-5. S2CID  27676690.
  • Сальвадор Э. Венегас-Андрака (2008). Квантовые прогулки для компьютерных ученых . Издательство Morgan & Claypool. ISBN 978-1598296563.
  • Киа Манучехри, Джингбо Ван (2014). Физическая реализация квантовых прогулок . Springer. ISBN 978-3-642-36014-5.
  • Международный семинар по математическим и физическим основам дискретного квантового блуждания во времени
  • Квантовая прогулка
  • Реализации дискретных квантовых блужданий с Classiq
Retrieved from "https://en.wikipedia.org/w/index.php?title=Quantum_walk&oldid=1249354707"