Квантовый ход в непрерывном времени

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

Определения [ править ]

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

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

Непрерывного квант времени ходить по во время определяется как:${\ Displaystyle U (т) \ in \ OperatorName {Mat} _ {п \ раз п} (\ mathbb {C})}$${\ displaystyle G}$${\ displaystyle t}$

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

${\ displaystyle A}$

${\ displaystyle G}$

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

Матрицы смешивания [ править ]

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

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

Периодические вершины [ править ]

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

Совершенный перенос состояния [ править ]

Говорят, что отдельные вершины и on допускают совершенную передачу состояния во время if .${\displaystyle u}$${\displaystyle v}$${\displaystyle G}$${\displaystyle t}$${\displaystyle M(t)_{u,v}=1}$

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

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

Говорят, что множество вершин на допускает совершенную передачу состояния (во времени ), если для всех существует такая, и допускает совершенную передачу состояния во времени .${\displaystyle S}$${\displaystyle G}$${\displaystyle t}$${\displaystyle u\in S}$${\displaystyle v\in S}$${\displaystyle u}$${\displaystyle v}$${\displaystyle t}$

Периодические графики [ править ]

Сам граф называется периодическим, если существует время , в котором все его вершины периодичны .${\displaystyle G}$${\displaystyle t\neq 0}$${\displaystyle t}$

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

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

Совершенный перенос состояния [ править ]

Необходимые условия [ править ]

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

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

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

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

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

Перенос идеального состояния на регулярных графах [ править ]

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

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

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

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

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

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

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

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