Kvantový konečný automat - Quantum finite automaton - Wikipedia

v kvantové výpočty, kvantové konečné automaty (QFA) nebo kvantové stavové stroje jsou kvantovým analogem pravděpodobnostní automaty nebo a Markovův rozhodovací proces. Poskytují matematickou abstrakci reálného světa kvantové počítače. Lze definovat několik typů automatů, včetně měřit jednou a měřit mnoho automaty. Kvantové konečné automaty lze také chápat jako kvantování podřazení konečného typu, nebo jako kvantování Markovovy řetězy. QFA jsou zase speciální případy geometrické konečné automaty nebo topologické konečné automaty.

Automaty fungují přijímáním konečné délky tětiva ${ displaystyle sigma = ( sigma _ {0}, sigma _ {1}, cdots, sigma _ {k})}$ písmen ${ displaystyle sigma _ {i}}$ z konečného abeceda ${ displaystyle Sigma}$a přiřazení ke každému takovému řetězci a pravděpodobnost ${ displaystyle operatorname {Pr} ( sigma)}$ označující pravděpodobnost, že automat bude v přijmout stát; tj. označující, zda automat řetězec přijal nebo odmítl.

The jazyky přijaty QFA nejsou běžné jazyky z deterministické konečné automaty, ani nejsou stochastické jazyky z pravděpodobnostní konečné automaty. Studie o nich kvantové jazyky zůstává aktivní oblastí výzkumu.

Neformální popis

Existuje jednoduchý a intuitivní způsob porozumění kvantovým konečným automatům. Jeden začíná a graf-teoretický interpretace deterministické konečné automaty (DFA). DFA může být reprezentován jako směrovaný graf se stavy jako uzly v grafu a šipkami představujícími přechody stavu. Každá šipka je označena možným vstupním symbolem, takže při daném konkrétním stavu a vstupním symbolu šipka ukazuje na další stav. Jedním ze způsobů znázornění takového grafu je pomocí sady matice sousedství, s jednou maticí pro každý vstupní symbol. V tomto případě je seznam možných stavů DFA zapsán jako vektor sloupce. U daného vstupního symbolu označuje matice sousedství, jak se kterýkoli daný stav (řádek ve vektoru stavu) přepne do dalšího stavu; přechod stavu je dán vztahem násobení matic.

Jeden potřebuje odlišnou matici sousedství pro každý možný vstupní symbol, protože každý vstupní symbol může mít za následek jiný přechod. Položky v matici sousedství musí být nula a jedna. Pro libovolný daný sloupec v matici může být nenulová pouze jedna položka: toto je položka, která označuje další (jedinečný) přechod stavu. Podobně je stav systému sloupcový vektor, ve kterém je pouze jedna položka nenulová: tato položka odpovídá aktuálnímu stavu systému. Nechat ${ displaystyle Sigma}$ označuje sadu vstupních symbolů. Pro daný vstupní symbol ${ displaystyle alpha in Sigma}$, psát si ${ displaystyle U _ { alpha}}$ jako matice sousedství, která popisuje vývoj DFA do dalšího stavu. Sada ${ displaystyle {U _ { alfa} | alfa v Sigma }}$ pak úplně popisuje funkci přechodu stavu DFA. Nechat Q představují množinu možných stavů DFA. Pokud existují N uvádí v Q, pak každá matice ${ displaystyle U _ { alpha}}$ je N podle N-dimenzionální. Počáteční stav ${ displaystyle q_ {0} v Q}$ odpovídá vektoru sloupce s jedním v q₀'házet. Obecný stav q je pak vektor sloupce s jedním v q 'házet. Podle zneužití notace, nechť q₀ a q také označte tyto dva vektory. Poté po přečtení vstupních symbolů ${ displaystyle alpha beta gamma cdots}$ ze vstupní pásky bude stav DFA dán vztahem ${ displaystyle q = cdots U _ { gamma} U _ { beta} U _ { alpha} q_ {0}.}$ Stavové přechody jsou dány obyčejnými násobení matic (to znamená znásobit q₀ podle ${ displaystyle U _ { alpha}}$, atd.); pořadí aplikace je „obrácené“ pouze proto, že se řídíme standardní notací lineární algebry.

Výše uvedený popis DFA, pokud jde o lineární operátory a vektory, téměř prosí o zobecnění, nahrazením stavového vektoru q nějakým obecným vektorem a maticemi ${ displaystyle {U _ { alpha} }}$ některými obecnými operátory. To je v podstatě to, co QFA dělá: nahrazuje q podle a amplituda pravděpodobnosti a ${ displaystyle {U _ { alpha} }}$ podle unitární matice. Zřejmé jsou také další podobné zobecnění: vektor q může být nějaký rozdělení na potrubí; sada přechodových matic se stane automorfismy potrubí; to definuje topologický konečný automat. Podobně lze matice brát jako automorfismy a homogenní prostor; to definuje geometrický konečný automat.

Než přejdeme k formálnímu popisu QFA, je třeba zmínit a pochopit dvě pozoruhodná zevšeobecnění. První je nedeterministický konečný automat (NFA). V tomto případě vektor q je nahrazen vektorem, který může mít více než jednu položku, která je nenulová. Takový vektor pak představuje prvek napájecí sada z Q; je to jen funkce indikátoru na Q. Podobně matice přechodu stavu ${ displaystyle {U _ { alpha} }}$ jsou definovány takovým způsobem, že daný sloupec může obsahovat několik nenulových položek. Ekvivalentně by operace vícenásobného přidání prováděné během násobení matic po jednotlivých komponentách měly být nahrazeny logickými operacemi a nebo operacemi, tedy tak, že jeden pracuje s a prsten z charakteristika 2.

Známá věta uvádí, že pro každou DFA existuje ekvivalentní NFA a naopak. To znamená, že soubor jazyky které mohou být rozpoznány DFA a NFA jsou stejné; tohle jsou běžné jazyky. Při generalizaci na QFA se bude sada rozpoznaných jazyků lišit. Popis této sady je jedním z vynikajících výzkumných problémů v teorii QFA.

Další zobecnění, které by mělo být okamžitě zřejmé, je použití a stochastická matice pro přechodové matice a vektor pravděpodobnosti pro stát; toto dává pravděpodobnostní konečný automat. Aby mohl být stavový vektor interpretován jako pravděpodobnost, musí být ve vektoru stavu reálná čísla, kladná a součet jedna. Přechodové matice musí tuto vlastnost zachovat: proto musí být stochastické. Každý stavový vektor by měl být představen jako určující bod v a simplexní; jedná se tedy o topologický automat, přičemž simplex je varietou a stochastické matice jsou lineárními automorfizmy simplexu na sebe. Jelikož každý přechod je (v podstatě) nezávislý na předchozím (pokud si nevšímáme rozdílu mezi přijímanými a odmítnutými jazyky), stává se PFA v podstatě jakýmsi Markovův řetězec.

Naproti tomu v QFA je potrubí složitý projektivní prostor ${ displaystyle mathbb {C} P ^ {N}}$a přechodové matice jsou jednotkové matice. Každý bod v ${ displaystyle mathbb {C} P ^ {N}}$ odpovídá kvantově-mechanické amplituda pravděpodobnosti nebo čistý stav; jednotné matice lze považovat za řízení časového vývoje systému (viz v Schrödingerův obrázek ). Zobecnění z čistých stavů na smíšené státy by měl být přímočarý: Smíšený stav je prostě a míra-teoretická rozdělení pravděpodobnosti na ${ displaystyle mathbb {C} P ^ {N}}$.

Hodným bodem k zamyšlení je distribuce, která je výsledkem na potrubí během zadávání jazyka. Aby byl automat „efektivní“ v rozpoznávání jazyka, měla by být tato distribuce „co nejjednotnější“. Tato potřeba jednotnosti je základním principem metody maximální entropie: jednoduše zaručují ostrý a kompaktní provoz automatu. Jinými slovy, strojové učení metody používané k trénování skryté Markovovy modely zobecnit také na QFA: Viterbiho algoritmus a algoritmus dopředu-dozadu snadno zobecnit na QFA.

Ačkoli byla studie QFA popularizována v dílech Kondacse a Watrousa v roce 1997^[1] a později Moore a Crutchfeld,^[2] byly popsány již v roce 1971 autorem Ion Baianu.^[3][4]

Měřte jednorázové automaty

Míra, kdy byly automaty zavedeny uživatelem Cris Moore a James P. Crutchfield.^[2] Mohou být formálně definovány následovně.

Jako s obyčejným konečný automat, má se za to, že kvantový automat má ${ displaystyle N}$ možné vnitřní stavy, představované v tomto případě znakem ${ displaystyle N}$-Stát qubit ${ displaystyle | psi rangle}$. Přesněji řečeno ${ displaystyle N}$-státní qubit ${ displaystyle | psi rangle in mathbb {C} P ^ {N}}$ je prvek ${ displaystyle N}$-dimenzionální složitý projektivní prostor, nesoucí vnitřní produkt ${ displaystyle Vert cdot Vert}$ toto je Fubini – metrika studia.

The přechody stavu, přechodové matice nebo de Bruijn grafy jsou zastoupeny sbírkou ${ displaystyle N krát N}$ unitární matice ${ displaystyle U _ { alpha}}$, s jednou jednotnou maticí pro každé písmeno ${ displaystyle alpha in Sigma}$. To znamená, že dostal vstupní písmeno ${ displaystyle alpha}$, unitární matice popisuje přechod automatu z jeho aktuálního stavu ${ displaystyle | psi rangle}$ do dalšího stavu ${ displaystyle | psi ^ { prime} rangle}$:

${ displaystyle | psi ^ { prime} rangle = U _ { alpha} | psi rangle}$

Tedy trojnásobný ${ displaystyle ( mathbb {C} P ^ {N}, Sigma, {U _ { alpha} ; vert ; alpha in Sigma })}$ tvoří a kvantová poloautomatizace.

The přijmout stát automatu je dán znakem ${ displaystyle N krát N}$ projekční matice ${ displaystyle P}$, takže, vzhledem k tomu, ${ displaystyle N}$-dimenzionální kvantový stav ${ displaystyle | psi rangle}$, pravděpodobnost ${ displaystyle | psi rangle}$ být ve stavu přijetí je

${ displaystyle langle psi | P | psi rangle = Vert P | psi rangle Vert ^ {2}}$

Pravděpodobnost, že stavový stroj přijme daný konečný vstupní řetězec ${ displaystyle sigma = ( sigma _ {0}, sigma _ {1}, cdots, sigma _ {k})}$ darováno

${ displaystyle operatorname {Pr} ( sigma) = Vert PU _ { sigma _ {k}} cdots U _ { sigma _ {1}} U _ { sigma _ {0}} | psi rangle Vert ^ {2}}$

Tady vektor ${ displaystyle | psi rangle}$ Rozumí se, že představuje počáteční stav automatu, tj. stav, ve kterém byl automat před přijetím vstupu řetězce. Prázdný řetězec ${ displaystyle varnothing}$ se rozumí pouze matice jednotek, takže

${ displaystyle operatorname {Pr} ( varnothing) = Vert P | psi rangle Vert ^ {2}}$

je jen pravděpodobnost, že počáteční stav bude přijat.

Protože levá akce ${ displaystyle U _ { alpha}}$ na ${ displaystyle | psi rangle}$ obrátí pořadí písmen v řetězci ${ displaystyle sigma}$, není neobvyklé, že jsou QFA definovány pomocí správné akce na Hermitian transponovat uvádí, jednoduše proto, aby pořadí písmen zůstalo stejné.

A běžný jazyk je přijímán s pravděpodobností ${ displaystyle p}$ kvantovým konečným automatem, pokud pro všechny věty ${ displaystyle sigma}$ v jazyce (a daném pevném počátečním stavu ${ displaystyle | psi rangle}$), jeden má ${ displaystyle p < operatorname {Pr} ( sigma)}$.

Příklad

Zvažte klasiku deterministický konečný automat dané tabulka přechodu stavu

Státní přechodová tabulka Vstup Stát 1 0 S1 S1 S2 S2 S2 S1

Stavový diagram

Kvantový stav je vektor v braketová notace

${ displaystyle | psi rangle = a_ {1} | S_ {1} rangle + a_ {2} | S_ {2} rangle = { begin {bmatrix} a_ {1} a_ {2} konec {bmatrix}}}$

s komplexní čísla ${ displaystyle a_ {1}, a_ {2}}$ normalizováno tak

${ displaystyle { begin {bmatrix} a_ {1} ^ {*} ; ; a_ {2} ^ {*} end {bmatrix}} { begin {bmatrix} a_ {1} a_ {2 } end {bmatrix}} = a_ {1} ^ {*} a_ {1} + a_ {2} ^ {*} a_ {2} = 1}$

Jednotné přechodové matice jsou

${ displaystyle U_ {0} = { begin {bmatrix} 0 & 1 1 & 0 end {bmatrix}}}$

a

${ displaystyle U_ {1} = { begin {bmatrix} 1 & 0 0 & 1 end {bmatrix}}}$

Brát ${ displaystyle S_ {1}}$ stav přijetí je projekční matice

${ displaystyle P = { begin {bmatrix} 1 & 0 0 & 0 end {bmatrix}}}$

Jak by mělo být snadno patrné, pokud je počátečním stavem čistý stav ${ displaystyle | S_ {1} rangle}$ nebo ${ displaystyle | S_ {2} rangle}$, pak bude výsledek chodu stroje přesně totožný s klasickým deterministickým strojem s konečným stavem. Zejména existuje automat přijímaný tímto automatem s pravděpodobností jeden pro tyto počáteční stavy a je totožný s běžný jazyk pro klasický DFA a je dán regulární výraz:

${ displaystyle (1 ^ {*} (01 ^ {*} 0) ^ {*}) ^ {*} , !}$

K neklasickému chování dochází, pokud obojí ${ displaystyle a_ {1}}$ a ${ displaystyle a_ {2}}$ jsou nenulové. Jemnější chování nastane, když matice ${ displaystyle U_ {0}}$ a ${ displaystyle U_ {1}}$ nejsou tak jednoduché; viz například de Rhamova křivka jako příklad kvantového konečného stavového stroje působícího na množinu všech možných konečných binárních řetězců.

Změřte mnoho automatů

V roce 1997 zavedli Kondacs a Watrous mnoho automatů.^[1] Obecný rámec se podobá systému jednorázového automatu, až na to, že místo jedné projekce je na konci projekce nebo kvantové měření, provedeno po přečtení každého písmene. Následuje formální definice.

The Hilbertův prostor ${ displaystyle { mathcal {H}} _ {Q}}$ je rozložen na tři ortogonální podprostory

${ displaystyle { mathcal {H}} _ {Q} = { mathcal {H}} _ { text {přijmout}} oplus { mathcal {H}} _ { text {odmítnout}} oplus { mathcal {H}} _ { text {non-stopting}}}$

V literatuře jsou tyto ortogonální podprostory obvykle formulovány z hlediska množiny ${ displaystyle Q}$ ortogonálních bazálních vektorů pro Hilbertův prostor ${ displaystyle { mathcal {H}} _ {Q}}$. Tato sada základních vektorů je rozdělena do podskupin ${ displaystyle Q _ { text {acc}} podmnožina Q}$ a ${ displaystyle Q _ { text {rej}} podmnožina Q}$, takový, že

${ displaystyle { mathcal {H}} _ { text {accept}} = operatorname {span} {| q rangle: | q rangle v Q _ { text {acc}} }}$

je lineární rozpětí základních vektorů v akceptační sadě. Odmítnutý prostor je definován analogicky a zbývající prostor je označen jako nezastavující se podprostor. K dispozici jsou tři projekční matice, ${ displaystyle P _ { text {acc}}}$, ${ displaystyle P _ { text {rej}}}$ a ${ displaystyle P _ { text {non}}}$, každý vyčnívající do příslušného podprostoru:

${ displaystyle P _ { text {acc}}: { mathcal {H}} _ {Q} na { mathcal {H}} _ { text {přijmout}}}$

a tak dále. Analýza vstupního řetězce probíhá následovně. Zvažte automat ve stavu ${ displaystyle | psi rangle}$. Po přečtení vstupního písmene ${ displaystyle alpha}$, automat bude ve stavu

${ displaystyle | psi ^ { prime} rangle = U _ { alpha} | psi rangle}$

V tomto okamžiku se provede měření stavu ${ displaystyle | psi ^ { prime} rangle}$pomocí operátorů projekce ${ displaystyle P}$, kdy se jeho vlnová funkce zhroutí do jednoho ze tří podprostorů ${ displaystyle { mathcal {H}} _ { text {přijmout}}}$ nebo ${ displaystyle { mathcal {H}} _ { text {odmítnout}}}$ nebo ${ displaystyle { mathcal {H}} _ { text {non-zastavení}}}$. Pravděpodobnost kolapsu je dána vztahem

${ displaystyle operatorname {Pr} _ { text {acc}} ( sigma) = Vert P _ { text {acc}} | psi ^ { prime} rangle Vert ^ {2}}$

pro podprostor „přijmout“ a analogicky pro další dva prostory.

Pokud se vlnová funkce zhroutila do podprostoru „přijmout“ nebo „odmítnout“, pak se další zpracování zastaví. Jinak zpracování pokračuje, přičemž další písmeno je načteno ze vstupu a použito na to, co musí být vlastním stavem ${ displaystyle P _ { text {non}}}$. Zpracování pokračuje, dokud se nenačte celý řetězec nebo dokud se stroj nezastaví. Často další symboly ${ displaystyle kappa}$ a $ jsou připojeny k abecedě, aby fungovaly jako levé a pravé koncové značky řetězce.

V literatuře je automat měření mnoha označován n-ticí ${ displaystyle (Q; Sigma; delta; q_ {0}; Q _ { text {acc}}; Q _ { text {rej}})}$. Tady, ${ displaystyle Q}$, ${ displaystyle Sigma}$, ${ displaystyle Q _ { text {acc}}}$ a ${ displaystyle Q _ { text {rej}}}$ jsou definovány výše. Počáteční stav je označen ${ displaystyle | psi rangle = | q_ {0} rangle}$. Jednotkové transformace jsou označeny mapou ${ displaystyle delta}$,

${ displaystyle delta: Q krát Sigma krát Q až mathbb {C}}$

aby

${ displaystyle U _ { alpha} | q_ {1} rangle = sum _ {q_ {2} v Q} delta (q_ {1}, alpha, q_ {2}) | q_ {2} zvonit}$

Vztah ke kvantovému výpočtu

Od roku 2019 většina kvantové počítače jsou implementace jednorázových kvantových konečných automatů a softwarové systémy pro jejich programování odhalují stavovou přípravu ${ displaystyle | psi rangle}$, měření ${ displaystyle P}$ a výběr jednotkových transformací ${ displaystyle U _ { alpha}}$, jako je řízená NOT brána, Hadamardova transformace a další kvantové logické brány přímo programátorovi.

Primárním rozdílem mezi kvantovými počítači v reálném světě a výše uvedeným teoretickým rámcem je, že příprava počátečního stavu nemůže nikdy vyústit v bodový čistý stav, nelze také přesně použít unitární operátory. Počáteční stav tedy musíme brát jako a smíšený stav

${ displaystyle rho = int p (x) | psi _ {x} rangle dx}$

pro nějaké rozdělení pravděpodobnosti ${ displaystyle p (x)}$ charakterizující schopnost strojního zařízení připravit počáteční stav blízký požadovanému počátečnímu čistému stavu ${ displaystyle | psi rangle}$. Tento stav není stabilní, ale trpí určitým množstvím kvantová dekoherence přesčas. Přesná měření také nejsou možná a jedno místo toho používá pozitivní opatření oceňovaná provozovatelem popsat proces měření. A konečně, každá jednotná transformace není jediná, ostře definovaná kvantová logická brána, ale spíše směs

${ displaystyle U _ { alpha, ( rho)} = int p _ { alpha} (x) U _ { alpha, x} dx}$

pro nějaké rozdělení pravděpodobnosti ${ displaystyle p _ { alpha} (x)}$ popisující, jak dobře může strojní zařízení ovlivnit požadovanou transformaci ${ displaystyle U _ { alpha}}$.

V důsledku těchto účinků nelze skutečný časový vývoj stavu brát jako čistý bod s nekonečnou přesností, ovládaný posloupností libovolně ostrých transformací, ale spíše jako ergodický proces, nebo přesněji, a proces míchání který pouze zřetězuje transformace do stavu, ale také časem rozmazává stav.

Neexistuje žádný kvantový analog k zatlačovací automat nebo stohovací stroj. To je způsobeno věta o klonování: neexistuje způsob, jak vytvořit kopii aktuálního stavu stroje, vložit jej do zásobníku pro pozdější použití a potom se do něj vrátit.

Geometrické zobecnění

Výše uvedené konstrukce naznačují, jak lze koncept kvantového konečného automatu zobecnit na libovolný topologické prostory. Jeden může například vzít některé (N-dimenzionální) Riemannův symetrický prostor zaujmout místo ${ displaystyle mathbb {C} P ^ {N}}$. Místo jednotkových matic se používá izometrie Riemannova potrubí, nebo obecněji nějaká sada otevřené funkce vhodné pro daný topologický prostor. Počáteční stav lze považovat za bod v prostoru. Množinu stavů přijetí lze považovat za libovolnou podmnožinu topologického prostoru. Jeden pak říká, že a formální jazyk je tímto přijato topologický automat pokud bod po iteraci homeomorfismem protíná akceptující množinu. Ale samozřejmě to není nic jiného než standardní definice M-automat. Chování topologických automatů je studováno v oblasti topologická dynamika.

Kvantový automat se liší od topologického automatu tím, že místo toho, aby měl binární výsledek (je iterovaný bod v konečné sadě nebo ne?), Má pravděpodobnost. Kvantová pravděpodobnost je (čtverec) počátečního stavu promítaného do nějakého konečného stavu P; to je ${ displaystyle mathbf {Pr} = vert langle P vert psi rangle vert ^ {2}}$. Ale tato amplituda pravděpodobnosti je jen velmi jednoduchá funkce vzdálenosti mezi bodem ${ displaystyle vert P rangle}$ a pointa ${ displaystyle vert psi rangle}$ v ${ displaystyle mathbb {C} P ^ {N}}$, pod dálkou metrický dané Fubini – metrika studia. Stručně řečeno, kvantovou pravděpodobnost přijetí jazyka lze interpretovat jako metriku, přičemž pravděpodobnost přijetí je jednota, pokud je metrická vzdálenost mezi počátečním a konečným stavem nulová a jinak je pravděpodobnost přijetí menší než jedna, pokud je metrická vzdálenost nenulová. Z toho tedy vyplývá, že kvantový konečný automat je jen zvláštním případem a geometrický automat nebo a metrický automat, kde ${ displaystyle mathbb {C} P ^ {N}}$ je zobecněn na některé metrický prostor a míra pravděpodobnosti je nahrazena jednoduchou funkcí metriky v daném prostoru.

Viz také

• Kvantový Markovův řetězec

Poznámky