Kvantová procházka - Quantum walk

Kvantové procházky jsou kvantové analogy klasických náhodných procházek . Na rozdíl od klasické náhodné chůze, kdy chodec zaujímá určité stavy a náhodnost vzniká v důsledku stochastických přechodů mezi stavy , v kvantových procházkách náhodnost vzniká prostřednictvím: (1) kvantové superpozice stavů, (2) nenáhodné, reverzibilní jednotkové evoluce a (3) zhroucení vlnové funkce v důsledku měření stavu .

Stejně jako u klasických náhodných procházek, i kvantové procházky připouštějí formulace v diskrétním i kontinuálním čase .

Motivace

Kvantové procházky jsou motivovány rozšířeným používáním klasických náhodných procházek při návrhu randomizovaných algoritmů a jsou součástí několika kvantových algoritmů . U některých věšteckých problémů poskytují kvantové pochody exponenciální zrychlení oproti jakémukoli klasickému algoritmu. Kvantové procházky také dávají polynomiální zrychlení oproti klasickým algoritmům pro mnoho praktických problémů, jako je problém odlišnosti prvků, problém s nalezením trojúhelníku a hodnocení stromů NAND. Známý vyhledávací algoritmus Grover lze také chápat jako algoritmus kvantové chůze.

Vztah ke klasickým náhodným procházkám

Kvantové procházky vykazují velmi odlišné rysy od klasických náhodných procházek. Zejména se nekonvergují k omezujícím distribucím a díky síle kvantové interference se mohou šířit výrazně rychleji nebo pomaleji než jejich klasické ekvivalenty.

Nepřetržitý čas

Kvantové procházky kontinuálního času vznikají, když nahradíme prostorovou doménu kontinua ve Schrödingerově rovnici diskrétní sadou. To znamená, že namísto množení kvantové částice v kontinuu je možné omezit množinu možných stavů polohy na množinu vrcholů nějakého grafu, který může být konečný nebo spočetně nekonečný. Za určitých podmínek mohou kvantové procházky v nepřetržitém čase poskytnout model pro univerzální kvantový výpočet . ${\ displaystyle V}$${\ displaystyle G = (V, E)}$

Vztah k nerelativistické Schrödingerově dynamice

Uvažujme o dynamice nerelativistické kvantové částice bez rotace bez hmoty s množením hmoty na nekonečné jednorozměrné prostorové doméně. Pohyb částice je zcela popsán její vlnovou funkcí, která splňuje jednorozměrnou Schrödingerovu rovnici volných částic ${\ displaystyle m}$${\ displaystyle \ psi: \ mathbb {R} \ krát \ mathbb {R} _ {\ geq 0} \ do \ mathbb {C}}$

${\ displaystyle {\ textbf {i}} \ hbar {\ frac {\ částečné \ psi} {\ částečné t}} = - {\ frac {\ hbar ^ {2}} {2m}} {\ frac {\ částečné ^ {2} \ psi} {\ částečné x ^ {2}}}}$

kde a je redukovaná Planckova konstanta. Nyní předpokládejme, že je diskretizována pouze prostorová část domény, která bude nahrazena tím, kde je separace mezi prostorovými místy, které může částice zaujímat. Vlnová funkce se stává mapou a druhou prostorovou parciální derivací se stává diskrétní laplacian ${\ displaystyle {\ textbf {i}} = {\ sqrt {-1}}}$${\ displaystyle \ hbar}$${\ displaystyle \ mathbb {R}}$${\ displaystyle \ mathbb {Z} _ {\ Delta x} \ equiv \ {\ ldots, -2 \, \ Delta x, - \ Delta x, 0, \ Delta x, 2 \, \ Delta x, \ ldots \ }}$${\ displaystyle \ Delta x}$${\ displaystyle \ psi: \ mathbb {Z} _ {\ Delta x} \ krát \ mathbb {R} _ {\ geq 0} \ do \ mathbb {C}}$

${\ displaystyle {\ frac {\ částečné ^ {2} \ psi} {\ částečné x ^ {2}}} \ až {\ frac {L _ {\ mathbb {Z}} \ psi (j \, \ Delta x, t)} {\ Delta x ^ {2}}} \ equiv {\ frac {\ psi \ vlevo ((j + 1) \, \ Delta x, t \ vpravo) -2 \ psi \ vlevo (j \, \ Delta x, t \ right) + \ psi \ left ((j-1) \, \ Delta x, t \ right)} {\ Delta x ^ {2}}}}$

Evoluční rovnice pro kontinuální časovou kvantovou chůzi je tedy ${\ displaystyle \ mathbb {Z} _ {\ Delta x}}$

${\ displaystyle {\ textbf {i}} {\ frac {\ částečné \ psi} {\ částečné t}} = - \ omega _ {\ Delta x} L _ {\ mathbb {Z}} \ psi}$

kde je charakteristická frekvence. Tato konstrukce přirozeně zobecňuje případ, že diskretizovaná prostorová doména je libovolný graf a diskrétní laplacian je nahrazen grafem Laplacian, kde a jsou matice stupňů a matice sousedství . Běžnou volbou grafů, které se objevují při studiu kontinuálních časových kvantových procházek, jsou d -dimenzionální mřížky , cyklické grafy , d -dimenzionální diskrétní tori , d -dimenzionální hyperkrychle a náhodné grafy. ${\ displaystyle \ omega _ {\ Delta x} \ ekviv \ 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}}$

Diskrétní čas

Kvantum v diskrétním čase jde dál ${\ displaystyle \ mathbb {Z}}$

Rozdělení pravděpodobnosti vyplývající z jednorozměrných diskrétních časových procházek. Kvantová procházka vytvořená pomocí Hadamardovy mince je vynesena ( červená ) proti klasické procházce ( modrá ) po 50 časových krocích.

Vývoj kvantové chůze v diskrétním čase je specifikován součinem dvou unitárních operátorů: (1) operátor „převrácení mince“ a (2) operátor podmíněného posunu, které se používají opakovaně. Následující příklad je zde poučný. Představte si částici se spin-1/2 stupněm svobody šířící se na lineárním poli diskrétních míst. Pokud je počet takových stránek počítatelně nekonečný, identifikujeme stavový prostor s . Stav částice lze potom popsat stavem produktu ${\ displaystyle \ mathbb {Z}}$

${\ displaystyle | \ Psi \ rangle = | s \ rangle \ otimes | \ psi \ rangle}$

skládající se z vnitřního stavu rotace

${\ displaystyle | s \ rangle \ in {\ mathcal {H}} _ {C} = \ left \ {a _ {\ uparrow} | {\ uparrow} \ rangle + a _ {\ downarrow} | {\ downarrow} \ rangle : a _ {\ uparrow / \ downarrow} \ in \ mathbb {C} \ right \}}$

a stav polohy

${\ 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 \}}$

kde je „prostor pro mince“ a je prostor stavů fyzické kvantové polohy. Produkt v tomto nastavení je produkt Kronecker (tensor). Operátor podmíněného posunu pro kvantovou chůzi na trati je dán vztahem ${\ displaystyle {\ mathcal {H}} _ {C} = \ mathbb {C} ^ {2}}$${\ displaystyle {\ mathcal {H}} _ {P} = \ ell ^ {2} (\ mathbb {Z})}$${\ displaystyle \ otimes}$

${\ displaystyle S = | {\ uparrow} \ rangle \ langle {\ uparrow} | \ otimes \ sum \ limity _ {i} | i + 1 \ rangle \ langle i | + | {\ downarrow} \ rangle \ langle { \ downarrow} | \ otimes \ sum \ limits _ {i} | i-1 \ rangle \ langle i |,}$

tj. částice skočí doprava, pokud se točí nahoru, a doleva, pokud se točí dolů. Explicitně operátor podmíněného posunu působí na stavy produktu podle

${\ displaystyle S (| {\ uparrow} \ rangle \ otimes | i \ rangle) = | {\ uparrow} \ rangle \ otimes | i + 1 \ rangle}$

${\ displaystyle S (| {\ downarrow} \ rangle \ otimes | i \ rangle) = | {\ downarrow} \ rangle \ otimes | i-1 \ rangle}$

Pokud nejprve rotujeme rotaci s nějakou jednotnou transformací a poté použijeme , dostaneme netriviální kvantový pohyb . Populární volbou pro takovou transformaci je Hadamardova brána , která má vzhledem ke standardnímu základu rotace z- komponenty maticovou reprezentaci ${\ displaystyle C: {\ mathcal {H}} _ {C} \ až {\ mathcal {H}} _ {C}}$${\ displaystyle S}$${\ displaystyle \ mathbb {Z}}$${\ displaystyle C = H}$

${\ displaystyle H = {\ frac {1} {\ sqrt {2}}} {\ begin {pmatrix} 1 & \; \; 1 \\ 1 & -1 \ end {pmatrix}}}$

Když je tato volba provedena pro operátora převrácení mince, samotný operátor se nazývá „Hadamardova mince“ a výsledná kvantová procházka se nazývá „Hadamardova procházka“. V případě, že chodec se inicializuje na počátku a na spin-up stavu, jeden časový krok Hadamard procházku na je ${\ displaystyle \ mathbb {Z}}$

${\ 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).}$

Měření stavu systému v tomto bodě by odhalilo rotaci nahoru v poloze 1 nebo dolů rotaci v poloze -1, obojí s pravděpodobností 1/2. Opakování postupu by odpovídalo klasickému prostému náhodnému pochodu . Aby bylo možné pozorovat neklasický pohyb, v tomto bodě se neprovádí žádné měření stavu (a proto nevynucuje kolaps vlnové funkce). Místo toho opakujte postup otáčení rotace pomocí operátoru hodu mincí a podmíněného skákání pomocí . Tímto způsobem jsou zachovány kvantové korelace a různé stavy pozic se mohou navzájem rušit. To dává drasticky odlišné rozdělení pravděpodobnosti než klasická náhodná chůze (Gaussovo rozdělení), jak je vidět na obrázku vpravo. Prostorově lze vidět, že rozdělení není symetrické: i když Hadamardova mince dává se stejnou pravděpodobností jak nahoru, tak dolů spin, má distribuce tendenci driftovat doprava, když je počáteční spin . Tato asymetrie je zcela způsobena skutečností, že Hadamardova mince zachází s a asymetricky. Symetrické rozdělení pravděpodobnosti vzniká, pokud je zvolen počáteční stav ${\ displaystyle \ mathbb {Z}}$${\ displaystyle S}$${\ displaystyle | {\ uparrow} \ rangle}$${\ displaystyle | {\ uparrow} \ rangle}$${\ displaystyle | {\ downarrow} \ rangle}$

${\ displaystyle | \ Psi _ {0} ^ {\ text {symm}} \ rangle = {\ frac {1} {\ sqrt {2}}} (| {\ uparrow} \ rangle + {\ textbf {i} } | {\ downarrow} \ rangle) \ otimes | 0 \ rangle}$

Diracova rovnice

Zvažte, co se stane, když diskretizujeme masivního Diracova operátora v jedné prostorové dimenzi . Při absenci hromadného termínu máme hybné síly a hybné síly. Lze je charakterizovat vnitřním stupněm volnosti , „točením“ nebo „mincí“. Když zapneme hromadný člen, odpovídá to rotaci v tomto vnitřním „mince“ prostoru. Kvantová chůze odpovídá opakování iterace operátorů posunu a mince.

Je to velmi podobné modelu elektronu Richarda Feynmana v 1 (jedné) prostorové a 1 (jedné) časové dimenzi. Shrnul klikaté cesty, segmenty pohybující se doleva odpovídají jednomu otočení (nebo minci) a segmenty pohybující se doprava druhému. Další podrobnosti najdete na šachovnici Feynman .

Pravděpodobnost přechodu pro 1-dimenzionální kvantovou chůzi se chová jako Hermitovy funkce, které (1) asymptoticky oscilují v klasicky povolené oblasti, (2) je aproximována funkcí Airy kolem stěny potenciálu a (3) exponenciálně klesá v klasicky skrytá oblast.

Viz také

• Integrální formulace cesty

Reference

Další čtení

externí odkazy

• Mezinárodní workshop o matematických a fyzikálních základech diskrétní kvantové procházky časem
• Kvantová chůze