Квантовый ход в непрерывном времени - Continuous-time quantum walk

А квантовое блуждание в непрерывном времени (CTQW) это квантовая прогулка на данном (простой) график что продиктовано изменяющейся во времени унитарной матрицей, которая опирается на Гамильтониан квантовой системы и матрица смежности. Считается, что концепция CTQW была впервые рассмотрена для квантовых вычислений Эдвард Фархи и Сэм Гутманн;^[1] поскольку многие классические алгоритмы основаны на (классических) случайные прогулки, концепция CTQW изначально рассматривалась, чтобы увидеть, могут ли быть квантовые аналоги этих алгоритмов, например, лучше временная сложность чем их классические аналоги. В последнее время особый интерес вызывают такие проблемы, как определение того, какие графы допускают такие свойства, как идеальная передача состояния по отношению к их CTQW.

Определения

Предположим, что ${displaystyle G}$ это график на ${displaystyle n}$ вершины, и что ${displaystyle tin mathbb {R} }$.

Квантовые прогулки в непрерывном времени

Квантовое блуждание в непрерывном времени ${displaystyle U(t)in operatorname {Mat} _{n imes n}(mathbb {C} )}$ на ${displaystyle G}$ вовремя ${displaystyle t}$ определяется как:

$${displaystyle U(t):=e^{itA}}$$

позволяя ${displaystyle A}$ обозначим матрицу смежности ${displaystyle G}$.

Также можно аналогичным образом определить квантовое блуждание в непрерывном времени на ${displaystyle G}$ относительно его Матрица лапласа; хотя, если не указано иное, CTQW на графе будет означать CTQW относительно его матрицы смежности в оставшейся части этой статьи.

Матрицы для смешивания

Матрица смешивания ${displaystyle M(t)in operatorname {Mat} _{n imes n}(mathbb {R} )}$ из ${displaystyle G}$ вовремя ${displaystyle t}$ определяется как ${displaystyle M(t):=U(t)circ U(-t)}$.

Матрицы смешения симметричны дважды стохастические матрицы полученные из CTQW на графиках: ${displaystyle {M(t)}_{u,v}}$ дает вероятность ${displaystyle u}$ переход к ${displaystyle v}$ вовремя ${displaystyle t}$ для любых вершин ${displaystyle u}$ и v на ${displaystyle G}$.

Периодические вершины

Вершина ${displaystyle u}$ на ${displaystyle G}$ называется периодическим во времени ${displaystyle t}$ если ${displaystyle {M(t)}_{u,u}=1}$.

Совершенный государственный перевод

Четкие вершины ${displaystyle u}$ и ${displaystyle v}$ на ${displaystyle G}$ говорят, что допускают совершенный переход состояния ${displaystyle t}$ если ${displaystyle M(t)_{u,v}=1}$.

Если пара вершин на ${displaystyle G}$ допускают совершенную передачу состояния в момент времени t, то ${displaystyle G}$ сам по себе допускает совершенную передачу состояния (в момент времени t).

Множество ${displaystyle S}$ пар различных вершин на ${displaystyle G}$ говорят, что допускает совершенный переход состояния (во время ${displaystyle t}$), если каждая пара вершин из ${displaystyle S}$ допускает безупречный переход состояния во время ${displaystyle t}$.

Множество ${displaystyle S}$ вершин на ${displaystyle G}$ говорят, что допускает совершенный переход состояния (во время ${displaystyle t}$) если для всех ${displaystyle uin S}$ Существует ${displaystyle vin S}$ такой, что ${displaystyle u}$ и ${displaystyle v}$ допускать безупречный государственный перевод во время ${displaystyle t}$.

Периодические графики

График ${displaystyle G}$ сам называется периодическим, если есть время ${displaystyle teq 0}$ такое, что все его вершины периодичны в момент времени ${displaystyle t}$.

Граф периодичен тогда и только тогда, когда его (ненулевое) собственные значения все рационально кратны друг другу.^[2]

Более того, регулярный график является периодическим тогда и только тогда, когда это интегральный график.

Совершенный государственный перевод

Необходимые условия

Если пара вершин ${displaystyle u}$ и ${displaystyle v}$ на графике ${displaystyle G}$ допускать безупречный государственный перевод во время ${displaystyle t}$, то оба ${displaystyle u}$ и ${displaystyle v}$ периодические во времени ${displaystyle 2t}$.^[3]

Передача идеального состояния на произведениях графов

Рассмотрим графики ${displaystyle G}$ и ${displaystyle H}$.

Если оба ${displaystyle G}$ и ${displaystyle H}$ допускать безупречный государственный перевод во время ${displaystyle t}$, то их Декартово произведение ${displaystyle G,square ,H}$ допускает безупречный переход состояния во время ${displaystyle t}$.

Если либо ${displaystyle G}$ или ${displaystyle H}$ допускает безупречный переход состояния во время ${displaystyle t}$, то их несвязный союз ${displaystyle Gsqcup H}$ допускает безупречный переход состояния во время ${displaystyle t}$.

Передача совершенного состояния на регулярных графах

Если регулярный граф допускает совершенную передачу состояния, то все его собственные значения являются целыми числами.

Если ${displaystyle G}$ является графом в однородном когерентная алгебра который допускает совершенный переход состояния во время ${displaystyle t}$, например, а вершинно-транзитивный граф или график в схема ассоциации, то все вершины на ${displaystyle G}$ допускать безупречный государственный перевод во время ${displaystyle t}$. Кроме того, график ${displaystyle G}$ должен иметь идеальное соответствие который допускает совершенный перенос состояния, если он допускает совершенный перенос состояния между парой смежных вершин, и является графом в однородной когерентной алгебре.

Обычный реберно-транзитивный граф ${displaystyle G}$ не может допускать совершенную передачу состояния между парой смежных вершин, если только это не является несвязным объединением копий полного графа ${displaystyle K_{2}}$.

А сильно регулярный граф допускает совершенный переход состояния тогда и только тогда, когда это дополнять несвязного объединения четного числа копий ${displaystyle K_{2}}$.

Единственный кубический дистанционно регулярный граф который допускает совершенный переход состояния, является кубический график.

Рекомендации

1. Фархи, Эдвард; Гутманн, Сэм (1 августа 1998 г.). «Квантовые вычисления и деревья решений». Физический обзор A. Американское физическое общество (APS). 58 (2): 915–928. arXiv:Quant-ph / 9706062. Дои:10.1103 / Physreva.58.915. ISSN  1050-2947.
2. Годсил, Крис (26 января 2011 г.). «Периодические графики». Электронный журнал комбинаторики. 18 (1): P23. ISSN  1077-8926.
3. Жан, Гармония; Годсил, Крис. «Периодические вершины | Введение». www.math.uwaterloo.ca. Получено 30 августа 2017.

внешняя ссылка

• Квантовая прогулка на arxiv.org
• CTQW о демонстрациях Wolfram
• Квантовая прогулка