Paseo cuántico en tiempo continuo

Paseo aleatorio cuántico dictado por una matriz unitaria variable en el tiempo que se basa en el hamiltoniano

Un paseo cuántico de tiempo continuo (CTQW) es un paseo cuántico en un gráfico (simple) dado que está dictado por una matriz unitaria variable en el tiempo que se basa en el hamiltoniano del sistema cuántico y la matriz de adyacencia . Se cree que el concepto de un CTQW fue considerado por primera vez para la computación cuántica por Edward Farhi y Sam Gutmann; ^[1] dado que muchos algoritmos clásicos se basan en paseos aleatorios (clásicos) , el concepto de CTQW se consideró originalmente para ver si podría haber análogos cuánticos de estos algoritmos con, por ejemplo, mejor complejidad temporal que sus contrapartes clásicas. En tiempos recientes, problemas como decidir qué gráficos admiten propiedades como la transferencia de estado perfecta con respecto a sus CTQW han sido de particular interés.

Definiciones

Supongamos que es un gráfico sobre vértices, y que . ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle t\in \mathbb {R} }$

Paseos cuánticos en tiempo continuo

El paseo cuántico en el tiempo continuo en el tiempo se define como: siendo , denotando la matriz de adyacencia de . ${\displaystyle U(t)\in \operatorname {Mat} _{n\times n}(\mathbb {C} )}$ ${\displaystyle G}$ ${\displaystyle t}$ $${\displaystyle U(t):=e^{itA}}$$ ${\displaystyle A}$ ${\displaystyle G}$

También es posible definir de manera similar un recorrido cuántico de tiempo continuo en relación con su matriz laplaciana ; aunque, a menos que se indique lo contrario, un CTQW en un gráfico significará un CTQW en relación con su matriz de adyacencia durante el resto de este artículo. ${\displaystyle G}$

Matrices de mezcla

La matriz de mezcla de un momento se define como . ${\displaystyle M(t)\in \operatorname {Mat} _{n\times n}(\mathbb {R} )}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle M(t):=U(t)\circ U(-t)}$

Las matrices de mezcla son matrices doblemente estocásticas simétricas obtenidas a partir de CTQW en gráficos: da la probabilidad de transición a en el tiempo para cualquier vértice y v en . ${\displaystyle {M(t)}_{u,v}}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle G}$

Vértices periódicos

Se dice que un vértice en es periódico en el tiempo si . ${\displaystyle u}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle {M(t)}_{u,u}=1}$

Transferencia de estado perfecta

Se dice que vértices distintos y en admiten una transferencia de estado perfecta en el tiempo si . ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle M(t)_{u,v}=1}$

Si un par de vértices en admite transferencia de estado perfecta en el tiempo t, entonces se dice que en sí mismo admite transferencia de estado perfecta (en el tiempo t). ${\displaystyle G}$ ${\displaystyle G}$

Se dice que un conjunto de pares de vértices distintos en admite una transferencia de estado perfecta (en el tiempo ) si cada par de vértices en admite una transferencia de estado perfecta en el tiempo . ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle S}$ ${\displaystyle t}$

Se dice que un conjunto de vértices en admite transferencia de estado perfecta (en el tiempo ) si para todo hay un tal que y admite transferencia de estado perfecta en el tiempo . ${\displaystyle S}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle u\in S}$ ${\displaystyle v\in S}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle t}$

Gráficas periódicas

Se dice que un gráfico es periódico si hay un tiempo tal que todos sus vértices son periódicos en el tiempo . ${\displaystyle G}$ ${\displaystyle t\neq 0}$ ${\displaystyle t}$

Un gráfico es periódico si y sólo si sus valores propios (distintos de cero) son todos múltiplos racionales entre sí. ^[2]

Además, un gráfico regular es periódico si y sólo si es un gráfico integral .

Transferencia de estado perfecta

Condiciones necesarias

Si un par de vértices y en un gráfico admiten una transferencia de estado perfecta en el tiempo , entonces ambos y son periódicos en el tiempo . ^[3] ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle 2t}$

Transferencia de estado perfecta en productos de grafos

Considere gráficos y . ${\displaystyle G}$ ${\displaystyle H}$

Si ambos admiten una transferencia de estado perfecta en el tiempo , entonces su producto cartesiano admite una transferencia de estado perfecta en el tiempo . ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle t}$ ${\displaystyle G\,\square \,H}$ ${\displaystyle t}$

Si cualquiera de los dos admite una transferencia de estado perfecta en el tiempo , entonces su unión disjunta admite una transferencia de estado perfecta en el tiempo . ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle t}$ ${\displaystyle G\sqcup H}$ ${\displaystyle t}$

Transferencia de estado perfecta en grafos regulares de recorrido

Si un grafo regular admite una transferencia de estado perfecta, entonces todos sus valores propios son números enteros.

Si es un grafo en un álgebra coherente homogénea que admite transferencia de estado perfecta en el tiempo , como por ejemplo un grafo transitivo de vértices o un grafo en un esquema de asociación , entonces todos los vértices en admiten transferencia de estado perfecta en el tiempo . Además, un grafo debe tener una correspondencia perfecta que admita transferencia de estado perfecta si admite transferencia de estado perfecta entre un par de vértices adyacentes y es un grafo en un álgebra coherente homogénea. ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle G}$ ${\displaystyle t}$ ${\displaystyle G}$

Un grafo transitivo de aristas regular no puede admitir una transferencia de estado perfecta entre un par de vértices adyacentes, a menos que sea una unión disjunta de copias del grafo completo . ${\displaystyle G}$ ${\displaystyle K_{2}}$

Un grafo fuertemente regular admite transferencia de estado perfecta si y sólo si es el complemento de la unión disjunta de un número par de copias de . ${\displaystyle K_{2}}$

El único grafo cúbico regular de distancia que admite una transferencia de estado perfecta es el grafo cúbico .

Referencias

1. Farhi, Edward; Gutmann, Sam (1 de agosto de 1998). "Computación cuántica y árboles de decisión". Physical Review A . 58 (2). American Physical Society (APS): 915–928. arXiv : quant-ph/9706062 . Código Bibliográfico :1998PhRvA..58..915F. doi :10.1103/physreva.58.915. ISSN  1050-2947. S2CID  1439479.
2. Godsil, Chris (26 de enero de 2011). "Gráficos periódicos". Revista Electrónica de Combinatoria . 18 (1): P23. doi : 10.37236/510 . ISSN  1077-8926. S2CID  6955634.
3. Zhan, Harmony; Godsil, Chris. "Vértices periódicos | Introducción". math.uwaterloo.ca . Consultado el 30 de agosto de 2017 .

Enlaces externos

• Paseo cuántico en arxiv.org
• CTQW sobre demostraciones de Wolfram
• Paseo cuántico