Algoritmus odhadu kvantové fáze - Quantum phase estimation algorithm - Wikipedia

The Algoritmus odhadu kvantové fáze (označovaný také jako algoritmus odhadu kvantové vlastní hodnoty), je kvantový algoritmus odhadnout fázi (nebo vlastní hodnotu) vlastního vektoru jednotného operátoru. Přesněji řečeno, vzhledem k unitární matice ${ displaystyle U}$ a a kvantový stav ${ displaystyle | psi rangle}$ takhle ${ displaystyle U | psi rangle = e ^ {2 pi i theta} | psi rangle}$ , algoritmus odhaduje hodnotu ${ displaystyle theta}$ s vysokou pravděpodobností v rámci aditivní chyby ${ displaystyle varepsilon}$ , použitím ${ displaystyle O ( log (1 / varepsilon))}$ qubits (bez započítání těch, které se používají ke kódování stavu vlastního vektoru) a ${ displaystyle O (1 / varepsilon)}$ řízené-U operace.

Odhad fáze se často používá jako podprogram v jiných kvantových algoritmech, jako je například Shorův algoritmus^[1]^:131 a kvantový algoritmus pro lineární systémy rovnic.

Problém

Nechat U být nečleněný operátor který operuje m qubits s vlastní vektor ${ displaystyle | psi rangle,}$ takhle ${ Displaystyle U | psi rangle = e ^ {2 pi i theta} left | psi right rangle, 0 leq theta <1}$ .

Chtěli bychom najít vlastní číslo ${ displaystyle e ^ {2 pi i theta}}$ z ${ displaystyle | psi rangle}$ , což v tomto případě odpovídá odhadu fáze ${ displaystyle theta}$ , na konečnou úroveň přesnosti. Vlastní hodnotu můžeme napsat do formuláře ${ displaystyle e ^ {2 pi i theta}}$ protože U je unitární operátor nad komplexním vektorovým prostorem, takže jeho vlastní čísla musí být komplexní čísla s absolutní hodnotou 1.

Algoritmus

Obvod pro odhad kvantové fáze

Založit

Vstup se skládá ze dvou registry (jmenovitě dvě části): horní ${ displaystyle n}$ qubits zahrnují první registracea nižší ${ displaystyle m}$ qubits jsou druhý registr.

Vytvořte superpozici

Počáteční stav systému je:

{ displaystyle | 0 rangle ^ { mnohokrát n} | psi rangle.}

Po aplikaci n-bit Provoz brány Hadamard ${ displaystyle H ^ { další krát}}$ v prvním registru se stát stává:

{ displaystyle { frac {1} {2 ^ { frac {n} {2}}}} (| 0 rangle + | 1 rangle) ^ { otimes n} | psi rangle}

.

Použijte řízené jednotkové operace

Nechat ${ displaystyle U}$ být jednotným operátorem s vlastním vektorem ${ displaystyle | psi rangle}$ takhle ${ displaystyle U | psi rangle = e ^ {2 pi i theta} | psi rangle,}$ tím pádem

{ displaystyle U ^ {2 ^ {j}} | psi rangle = U ^ {2 ^ {j} -1} U | psi rangle = U ^ {2 ^ {j} -1} e ^ { 2 pi i theta} | psi rangle = cdots = e ^ {2 pi i2 ^ {j} theta} | psi rangle}

.

${ displaystyle C-U}$ je řízené-U brána, která používá jednotný pohon ${ displaystyle U}$ na druhém registru, pouze pokud je jeho odpovídající řídicí bit (z prvního registru) ${ displaystyle | 1 rangle}$ .

Za předpokladu jasnosti se předpokládá, že řízené brány jsou aplikovány postupně, po aplikaci ${ displaystyle C-U ^ {2 ^ {0}}}$ do ${ displaystyle n ^ {th}}$ qubit prvního registru a druhého registru se stát stává

{ displaystyle { frac {1} {2 ^ { frac {1} {2}}}} spodní výztuha { left (| 0 rangle | psi rangle + | 1 rangle e ^ {2 pi i2 ^ {0} theta} | psi rangle right)} _ {n ^ {th} qubit a second register} otimes { frac {1} {2 ^ { frac {n- 1} {2}}}} underbrace { left (| 0 rangle + | 1 rangle right) ^ { otimes ^ {n-1}}} _ {qubits 1 ^ {st} to n-1 ^ {th}} = { frac {1} {2 ^ { frac {1} {2}}}} left (| 0 rangle | psi rangle + e ^ {2 pi i2 ^ {0} theta} | 1 rangle | psi rangle right) otimes { frac {1} {2 ^ { frac {n-1} {2}}}} left (| 0 rangle + | 1 rangle right) ^ { otimes ^ {n-1}}}

{ displaystyle = { frac {1} {2 ^ { frac {1} {2}}}} vlevo (| 0 rangle + e ^ {2 pi i2 ^ {0} theta} | 1 rangle right) | psi rangle otimes { frac {1} {2 ^ { frac {n-1} {2}}}} left (| 0 rangle + | 1 rangle right) ^ { otimes ^ {n-1}} = { frac {1} {2 ^ { frac {n} {2}}}} underbrace { left (| 0 rangle + e ^ {2 pi i2 ^ {0} theta} | 1 rangle right)} _ {n ^ {th} qubit} otimes left (| 0 rangle + | 1 rangle right) ^ { otimes ^ {n- 1}} | psi rangle,}

kde používáme:

{ displaystyle | 0 rangle | psi rangle + | 1 rangle otimes e ^ {2 pi i2 ^ {j} theta} | psi rangle = (| 0 rangle + e ^ {2 pi i2 ^ {j} theta} | 1 rangle) | psi rangle, forall j.}

Po použití všech zbývajících ${ displaystyle n-1}$ řízené operace ${ displaystyle C-U ^ {2 ^ {j}}}$ s ${ Displaystyle 1 leq j leq n-1,}$ jak je vidět na obrázku, stav první registrace lze popsat jako

{ displaystyle { frac {1} {2 ^ { frac {n} {2}}}} spodní výztuha { left (| 0 rangle + e ^ {2 pi i2 ^ {n-1} theta } | 1 rangle right)} _ {1 ^ {st} qubit} otimes cdots otimes underbrace { left (| 0 rangle + e ^ {2 pi i2 ^ {1} theta} | 1 rangle right)} _ {n-1 ^ {th} qubit} otimes underbrace { left (| 0 rangle + e ^ {2 pi i2 ^ {0} theta} | 1 rangle right)} _ {n ^ {th} qubit} = { frac {1} {2 ^ { frac {n} {2}}}} sum _ {k = 0} ^ {2 ^ { n} -1} e ^ {2 pi i theta k} | k rangle,}

kde ${ displaystyle | k rangle}$ označuje binární vyjádření ${ displaystyle k}$ , tj. je to ${ displaystyle k ^ {th}}$ výpočetní základ a stav druhý registr je fyzicky nezměněn na ${ displaystyle | psi rangle}$ .

Použijte inverzní Kvantová Fourierova transformace

Použití inverzní Kvantová Fourierova transformace na

{ displaystyle { frac {1} {2 ^ { frac {n} {2}}}} součet _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 pi i theta k} | k rangle}

výnosy

{ displaystyle { frac {1} {2 ^ { frac {n} {2}}}} součet _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 pi i theta k} { frac {1} {2 ^ { frac {n} {2}}}} sum _ {x = 0} ^ {2 ^ {n} -1} e ^ { frac {-2 pi ikx} {2 ^ {n}}} | x rangle = { frac {1} {2 ^ {n}}} sum _ {x = 0} ^ {2 ^ {n} -1} součet _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 pi i theta k} e ^ { frac {-2 pi ikx} {2 ^ {n}}} | x rangle = { frac {1} {2 ^ {n}}} sum _ {x = 0} ^ {2 ^ {n} -1} sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {- { frac {2 pi ik} {2 ^ {n}}} left (x-2 ^ {n} theta right)} | x rangle.}

Stav obou registrů dohromady je

{ displaystyle { frac {1} {2 ^ {n}}} součet _ {x = 0} ^ {2 ^ {n} -1} součet _ {k = 0} ^ {2 ^ {n} -1} e ^ {- { frac {2 pi ik} {2 ^ {n}}} left (x-2 ^ {n} theta right)} | x rangle otimes | psi zvonit.}

Reprezentace fázové aproximace

Můžeme přiblížit hodnotu ${ displaystyle theta v [0,1]}$ zaokrouhlením ${ displaystyle 2 ^ {n} theta}$ na nejbližší celé číslo. Tohle znamená tamto ${ displaystyle 2 ^ {n} theta = a + 2 ^ {n} delta,}$ kde ${ displaystyle a}$ je nejbližší celé číslo ${ displaystyle 2 ^ {n} theta,}$ a rozdíl ${ displaystyle 2 ^ {n} delta}$ splňuje ${ displaystyle 0 leqslant | 2 ^ {n} delta | leqslant { tfrac {1} {2}}}$ .

Nyní můžeme zapsat stav prvního a druhého registru následujícím způsobem:

{ displaystyle { frac {1} {2 ^ {n}}} součet _ {x = 0} ^ {2 ^ {n} -1} součet _ {k = 0} ^ {2 ^ {n} -1} e ^ {- { frac {2 pi ik} {2 ^ {n}}} left (xa right)} e ^ {2 pi i delta k} | x rangle otimes | psi rangle.}

Měření

Provedení a měření ve výpočetním základě na prvním registru přináší výsledek ${ displaystyle | a rangle}$ s pravděpodobností

{ displaystyle Pr (a) = left | left langle a underbrace { left | { frac {1} {2 ^ {n}}} sum _ {x = 0} ^ {2 ^ { n} -1} sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {{ frac {-2 pi ik} {2 ^ {n}}} (xa)} e ^ {2 pi i delta k} right | x} _ { text {Stav prvního registru}} right rangle right | ^ {2} = { frac {1} {2 ^ {2n} }} left | sum _ {k = 0} ^ {2 ^ {n} -1} e ^ {2 pi i delta k} right | ^ {2} = { begin {cases} 1 & delta = 0 & { frac {1} {2 ^ {2n}}} left | { frac {1- {e ^ {2 pi i2 ^ {n} delta}}} {1 - {e ^ {2 pi i delta}}}} vpravo | ^ {2} & delta neq 0 end {cases}}}

Pro ${ displaystyle delta = 0}$ aproximace je tedy přesná ${ displaystyle a = 2 ^ {n} theta}$ a ${ displaystyle Pr (a) = 1.}$ V tomto případě vždy měříme přesnou hodnotu fáze.^[2]^:157^[3]^:347 Stav systému po měření je ${ displaystyle | 2 ^ {n} theta rangle otimes | psi rangle}$ .^[1]^:223

Pro ${ displaystyle delta neq 0}$ od té doby ${ displaystyle | delta | leqslant { tfrac {1} {2 ^ {n + 1}}}}$ algoritmus poskytuje správný výsledek s pravděpodobností ${ displaystyle Pr (a) geqslant { frac {4} { pi ^ {2}}} přibližně 0,405}$ . Dokazujeme to takto: ^[2]^:157 ^[3]^:348

{ displaystyle { begin {aligned} Pr (a) & = { frac {1} {2 ^ {2n}}} left | { frac {1- {e ^ {2 pi i2 ^ {n } delta}}} {1- {e ^ {2 pi i delta}}}} doprava | ^ {2} && { text {for}} delta neq 0 [6pt] & = { frac {1} {2 ^ {2n}}} left | { frac {2 sin left ( pi 2 ^ {n} delta right)} {2 sin ( pi delta) }} right | ^ {2} && left | 1-e ^ {2ix} right | ^ {2} = 4 left | sin (x) right | ^ {2} [6pt] & = { frac {1} {2 ^ {2n}}} { frac { left | sin left ( pi 2 ^ {n} delta right) right | ^ {2}} {| sin ( pi delta) | ^ {2}}} [6pt] & geqslant { frac {1} {2 ^ {2n}}} { frac { left | sin left ( pi 2 ^ {n} delta right) right | ^ {2}} {| pi delta | ^ {2}}} && | sin ( pi delta) | leqslant | pi delta | { text {for}} | delta | leqslant { frac {1} {2 ^ {n + 1}}} [6pt] & geqslant { frac {1} {2 ^ {2n}} } { frac {| 2 cdot 2 ^ {n} delta | ^ {2}} {| pi delta | ^ {2}}} && | 2 cdot 2 ^ {n} delta | leqslant | sin ( pi 2 ^ {n} delta) | { text {for}} | delta | leqslant { frac {1} {2 ^ {n + 1}}} [6pt] & geqslant { frac {4} { pi ^ {2}}} end {zarovnáno}}}

Tento výsledek ukazuje, že změříme nejlepší n-bitový odhad ${ displaystyle theta}$ s vysokou pravděpodobností. Zvýšením počtu qubitů o ${ displaystyle O ( log (1 / epsilon))}$ a ignorováním těchto posledních qubits můžeme zvýšit pravděpodobnost ${ displaystyle 1- epsilon}$ .^[3]

Viz také

Reference

^ ^A ^b Nielsen, Michael A. & Isaac L. Chuang (2001). Kvantové výpočty a kvantové informace (Repr. Ed.). Cambridge [u.a.]: Cambridge Univ. Lis. ISBN 978-0521635035.
^ ^A ^b Benenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principy kvantového výpočtu a informací (Přetištěno, ed.). New Jersey [USA]: World Scientific. ISBN 978-9812388582.
^ ^A ^b ^C Cleve, R .; Ekert, A .; Macchiavello, C .; Mosca, M. (8. ledna 1998). "Kvantové algoritmy znovu navštíveny". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969). arXiv:quant-ph / 9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098 / rspa.1998.0164.

Kitaev, A. Yu. (1995). „Kvantová měření a Abelianův stabilizátorový problém“. arXiv:quant-ph / 9511026.

[nielchuan-1] A ^b Nielsen, Michael A. & Isaac L. Chuang (2001). Kvantové výpočty a kvantové informace (Repr. Ed.). Cambridge [u.a.]: Cambridge Univ. Lis. ISBN 978-0521635035.

[benet-2] A ^b Benenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principy kvantového výpočtu a informací (Přetištěno, ed.). New Jersey [USA]: World Scientific. ISBN 978-9812388582.

[ekert-3] A ^b ^C Cleve, R .; Ekert, A .; Macchiavello, C .; Mosca, M. (8. ledna 1998). "Kvantové algoritmy znovu navštíveny". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969). arXiv:quant-ph / 9708016. Bibcode:1998RSPSA.454..339C. doi:10.1098 / rspa.1998.0164.

[1]

[2]

[3]