Kvantová chůze v nepřetržitém čase - Continuous-time quantum walk
A kontinuální kvantová chůze (CTQW) je kvantová chůze na dané (jednoduchý) graf která je diktována časově proměnnou jednotnou maticí, která se opírá o Hamiltonian kvantového systému a matice sousedství. Předpokládá se, že koncept CTQW byl poprvé považován za kvantový výpočet pomocí Edward Farhi a Sam Gutmann;[1] protože mnoho klasických algoritmů je založeno na (klasických) náhodné procházky, původně se uvažovalo o konceptu CTQW, aby se zjistilo, zda by mohly existovat kvantové analogy těchto algoritmů s např. lepší časová složitost než jejich klasické protějšky. V poslední době byly obzvláště zajímavé problémy, jako je rozhodování o tom, jaké grafy připouštějí vlastnosti, jako je přenos dokonalého stavu s ohledem na jejich CTQW.
Definice
Předpokládejme to je graf na vrcholy, a to .
Kvantové procházky v nepřetržitém čase
Kvantová chůze v nepřetržitém čase na v čase je definován jako:
Je také možné podobně definovat kontinuální kvantovou chůzi vzhledem k jeho Laplaciánská matice; ačkoli, pokud není uvedeno jinak, CTQW v grafu bude znamenat CTQW vzhledem k jeho matici sousedství pro zbytek tohoto článku.
Míchání matric
Míchací matice z v čase je definován jako .
Směšovací matice jsou symetrické dvojnásobně stochastické matice získané z CTQW v grafech: dává pravděpodobnost přechod na v čase pro všechny vrcholy a v .
Periodické vrcholy
Vrchol na se říká, že periodické v čase -li .
Dokonalý přenos stavu
Zřetelné vrcholy a na se říká, že připouštějí dokonalý přenos stavu v čase -li .
Pokud je pár vrcholů pak připustit dokonalý přenos stavu v čase t sám o sobě říká, že připouští dokonalý přenos stavu (v čase t).
Sada párů odlišných vrcholů na se říká, že připouští dokonalý přenos stavu (v čase ) pokud každý pár vrcholů v připouští dokonalý přenos stavu v čase .
Sada vrcholů na se říká, že připouští dokonalý přenos stavu (v čase ) pokud pro všechny tady je takhle a připustit dokonalý přenos stavu v čase .
Periodické grafy
Graf sama o sobě se říká, že je periodická, pokud je čas takže všechny jeho vrcholy jsou periodické v čase .
Graf je periodický právě tehdy, je-li (nenulový) vlastní čísla jsou navzájem racionálními násobky.[2]
Navíc, a běžný graf je periodický právě tehdy, pokud se jedná o integrální graf.
Dokonalý přenos stavu
Nezbytné podmínky
Pokud dvojice vrcholů a na grafu připustit dokonalý přenos stavu v čase , pak oba a jsou periodické v čase .[3]
Dokonalý přenos stavu na produkty grafů
Zvažte grafy a .
Pokud obojí a připustit dokonalý přenos stavu v čase , pak jejich kartézský součin připouští dokonalý přenos stavu v čase .
Pokud ano nebo připouští dokonalý přenos stavu v čase , pak jejich disjunktní unie připouští dokonalý přenos stavu v čase .
Dokonalý přenos stavu na grafech s pravidelným procházením
Pokud běžný graf připouští dokonalý přenos stavu, pak jsou všechny jeho vlastní hodnoty celá čísla.
Li je homogenní graf koherentní algebra který připouští dokonalý přenos stavu v čase , jako je např. A vrchol-tranzitivní graf nebo graf v asociační schéma, pak všechny vrcholy připustit dokonalý přenos stavu v čase . Navíc graf musí mít perfektní shoda který připouští přenos dokonalého stavu, pokud připouští přenos dokonalého stavu mezi dvojicí sousedních vrcholů a jedná se o graf v homogenní koherentní algebře.
Pravidelný hranový tranzitivní graf nemůže připustit dokonalý přenos stavu mezi dvojicí sousedních vrcholů, pokud se nejedná o disjunktní spojení kopií celého grafu .
A silně pravidelný graf připouští dokonalý přenos stavu právě tehdy, když se jedná o doplněk disjunktního spojení sudého počtu kopií .
Jediný krychlový vzdálenost-pravidelný graf který připouští dokonalý přenos stavu je krychlový graf.
Reference
- ^ Farhi, Edward; Gutmann, Sam (1. srpna 1998). "Kvantové výpočty a rozhodovací stromy". Fyzický přehled A. Americká fyzická společnost (APS). 58 (2): 915–928. arXiv:quant-ph / 9706062. doi:10.1103 / physreva.58.915. ISSN 1050-2947.
- ^ Godsil, Chris (26. ledna 2011). „Periodické grafy“. Electronic Journal of Combinatorics. 18 (1): P23. ISSN 1077-8926.
- ^ Zhan, Harmony; Godsil, Chris. "Periodické vrcholy | Úvod". www.math.uwaterloo.ca. Citováno 30. srpna 2017.