Amplitudové zesílení - Amplitude amplification - Wikipedia

Amplitudové zesílení je technika v kvantové výpočty což zobecňuje myšlenku Groverův vyhledávací algoritmus, a vede k rodiněkvantové algoritmy Bylo objeveno Gilles Brassard aPeter Høyer v roce 1997,^[1]a nezávisle znovu objevený uživatelem Lov Grover v roce 1998.^[2]

V kvantovém počítači lze amplitudovou amplifikaci použít k získání aquadratického zrychlení pomocí několika klasických algoritmů.

Algoritmus

Zde uvedená derivace zhruba následuje derivaci uvedenou v.^[3]Předpokládejme, že máme N-dimenzionální Hilbertův prostor ${ displaystyle { mathcal {H}}}$zastupující státní prostor našeho kvantového systému, překlenutého normálním stavem výpočetní báze ${ displaystyle B: = {| k rangle } _ {k = 0} ^ {N-1}}$Dále předpokládejme, že máme Hermitian operátor projekce ${ displaystyle P colon { mathcal {H}} do { mathcal {H}}}$.Alternativně, ${ displaystyle P}$ mohou být uvedeny v termínech aBoolean věštec funkce${ displaystyle chi tlustého střeva mathbb {Z} do {0,1 }}$a ortonormální provozní základ${ displaystyle B _ { text {op}}: = {| omega _ {k} rangle } _ {k = 0} ^ {N-1}}$,v jakém případě

${ displaystyle P: = sum _ { chi (k) = 1} | omega _ {k} rangle langle omega _ {k} |}$.

${ displaystyle P}$ lze použít k rozdělení${ displaystyle { mathcal {H}}}$ do přímého součtu dvou vzájemně ortogonálních podprostorů, dobrý podprostor ${ displaystyle { mathcal {H}} _ {1}}$ a špatný podprostor ${ displaystyle { mathcal {H}} _ {0}}$:

Jinými slovy, definujeme „dobrý podprostor" ${ displaystyle { mathcal {H}} _ {1}}$ prostřednictvím projektoru ${ displaystyle P}$. Cílem algoritmu je pak vyvinout nějaký počáteční stav ${ displaystyle | psi rangle in { mathcal {H}}}$ do státu patřícího ${ displaystyle { mathcal {H}} _ {1}}$.

Vzhledem k normalizovanému vektoru stavu ${ displaystyle | psi rangle in { mathcal {H}}}$ s nenulovým překrytím s oběma podprostory jej můžeme jednoznačně rozložit jako

${ displaystyle | psi rangle = sin ( theta) | psi _ {1} rangle + cos ( theta) | psi _ {0} rangle}$,

kde ${ displaystyle theta = arcsin left ( left | P | psi rangle right | right) in [0, pi / 2]}$,a${ displaystyle | psi _ {1} rangle}$ a ${ displaystyle | psi _ {0} rangle}$ jsou pak normalizované projekce ${ displaystyle | psi rangle}$ do těchto prostorů ${ displaystyle { mathcal {H}} _ {1}}$ a ${ displaystyle { mathcal {H}} _ {0}}$Tento rozklad definuje dvourozměrný podprostor${ displaystyle { mathcal {H}} _ { psi}}$, překlenutý vektory${ displaystyle | psi _ {0} rangle}$ a ${ displaystyle | psi _ {1} rangle}$Pravděpodobnost nalezení systému v a dobrý stav při měření ${ displaystyle sin ^ {2} ( theta)}$.

Definujte jednotný operátor${ displaystyle Q ( psi, P): = - S _ { psi} S_ {P} , !}$,kde

${ displaystyle { begin {aligned} S _ { psi} & = I-2 | psi rangle langle psi | quad { text {and}} S_ {P} & = I-2P. end {zarovnáno}}}$

${ displaystyle S_ {P}}$ převrátí fázi stavů v dobrý podprostor, zatímco${ displaystyle S _ { psi}}$ převrátí fázi počátečního stavu ${ displaystyle | psi rangle}$.

Akce tohoto operátora na ${ displaystyle { mathcal {H}} _ { psi}}$ darováno

${ displaystyle Q | psi _ {0} rangle = -S _ { psi} | psi _ {0} rangle = (2 cos ^ {2} ( theta) -1) | psi _ { 0} rangle +2 sin ( theta) cos ( theta) | psi _ {1} rangle}$ a

${ displaystyle Q | psi _ {1} rangle = S _ { psi} | psi _ {1} rangle = -2 sin ( theta) cos ( theta) | psi _ {0} rangle + (1-2 sin ^ {2} ( theta)) | psi _ {1} rangle}$.

Tak v ${ displaystyle { mathcal {H}} _ { psi}}$ podprostor ${ displaystyle Q}$odpovídá rotaci o úhel ${ displaystyle 2 theta , !}$:

${ displaystyle Q = { začátek {pmatrix} cos (2 theta) & sin (2 theta) - sin (2 theta) & cos (2 theta) end {pmatrix}} }$.

Přihlašování ${ displaystyle Q}$ ${ displaystyle n}$ krát na stát${ displaystyle | psi rangle}$dává

${ displaystyle Q ^ {n} | psi rangle = cos ((2n + 1) theta) | psi _ {0} rangle + sin ((2n + 1) theta) | psi _ {1} rangle}$,

otáčení stavu mezi dobrý a špatný podprostory ${ displaystyle n}$ iterace pravděpodobnost nalezení systému v a dobrý stát je ${ displaystyle sin ^ {2} ((2n + 1) theta) , !}$.
Pravděpodobnost je maximalizována, pokud se rozhodneme

${ displaystyle n = left lfloor { frac { pi} {4 theta}} right rfloor}$.

Až do tohoto bodu zvyšuje každá iterace amplitudu dobrý uvádí, Henen název techniky.

Aplikace

Předpokládejme, že máme netříděnou databázi s N prvky a funkce Oracle${ displaystyle chi}$ který dokáže rozpoznat dobrý záznamy, které hledáme, a ${ displaystyle B _ { text {op}} = B}$ pro jednoduchost.

Pokud existují ${ displaystyle G}$ dobrý položky v databázi celkem, pak je můžeme najít inicializací a kvantový registr ${ displaystyle | psi rangle}$ s ${ displaystyle n}$ qubits kde ${ displaystyle 2 ^ {n} = N}$ do jednotná superpozice všech prvků databáze ${ displaystyle N}$ takhle

${ displaystyle | psi rangle = { frac {1} { sqrt {N}}} součet _ {k = 0} ^ {N-1} | k rangle}$

a spuštění výše uvedeného algoritmu. V tomto případě se překrytí počátečního stavu s dobrý podprostor se rovná druhé odmocnině frekvence dobrý záznamy v databázi, ${ displaystyle sin ( theta) = | P | psi rangle | = { sqrt {G / N}}}$. Li ${ displaystyle sin ( theta) ll 1}$, můžeme odhadnout počet požadovaných iterací jako

${ displaystyle n = left lfloor { frac { pi} {4 theta}} right rfloor cca left lfloor { frac { pi} {4 sin ( theta)}} right rfloor = left lfloor { frac { pi} {4}} { sqrt { frac {N} {G}}} right rfloor = O ({ sqrt {N}}).}$

Měření stavu nyní dá jeden z dobrý záznamů s vysokou pravděpodobností. Od každé aplikace ${ displaystyle S_ {P}}$ vyžaduje jediný Oracle dotaz (za předpokladu, že Oracle je implementován jako kvantová brána ), můžeme najít a dobrý vstup s pouhým ${ displaystyle O ({ sqrt {N}})}$ Oracle dotazy, čímž se získá kvadratické zrychlení nad nejlepším možným klasickým algoritmem. (Klasickou metodou prohledávání databáze by bylo provést dotaz pro každého ${ displaystyle e in {0,1, tečky, N-1 }}$ dokud není nalezeno řešení, tedy náklady ${ displaystyle O (N)}$ dotazy.)

Pokud nastavíme velikost sady ${ displaystyle G}$ k jedné, výše uvedený scénář se v podstatě redukuje na původní Groverovo hledání.

Reference