Genlik amplifikasyonu - Amplitude amplification

Genlik amplifikasyonu , Grover'ın arama algoritmasının arkasındaki fikri genelleştiren ve bir kuantum algoritmaları ailesine yol açan kuantum hesaplamada bir tekniktir . Bu tarafından keşfedildi Gilles Brassard ve Peter Hoyer 1997 yılında, bağımsız ve yeniden keşfedilen Lov Grover 1998 yılında.

Bir kuantum bilgisayarda, birkaç klasik algoritma üzerinde ikinci dereceden bir hızlanma elde etmek için genlik amplifikasyonu kullanılabilir.

algoritma

Burada sunulan türetme kabaca içinde verileni takip eder. Kuantum sistemimizin durum uzayını temsil eden , ortonormal hesaplama temelli durumlar tarafından yayılan N-boyutlu bir Hilbert uzayımız olduğunu varsayalım . Ayrıca bir Hermitian izdüşüm operatörümüz olduğunu varsayalım . Alternatif olarak, bir Boolean oracle işlevi ve bir ortonormal işlem temeli cinsinden verilebilir , bu durumda ${\görüntüleme stili {\matematiksel {H}}}$${\displaystyle B:=\{|k\rangle \}_{k=0}^{N-1}}$ ${\displaystyle P\colon {\mathcal {H}}\to {\mathcal {H}}}$${\görüntüleme stili P}$${\displaystyle \chi \colon \mathbb {Z} \to \{0,1\}}$${\displaystyle B_{\text{op}}:=\{|\omega _{k}\rangle \}_{k=0}^{N-1}}$

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

${\görüntüleme stili P}$iki karşılıklı ortogonal alt uzayın, iyi alt uzayın ve kötü alt uzayın doğrudan toplamına bölmek için kullanılabilir : ${\görüntüleme stili {\matematiksel {H}}}$${\displaystyle {\mathcal {H}}_{1}}$${\displaystyle {\mathcal {H}}_{0}}$

Başka bir deyişle, projektör aracılığıyla " iyi bir alt uzay " tanımlıyoruz . Algoritmanın amacı bir başlangıç durumunu gelişmeye daha sonra ait bir duruma . ${\displaystyle {\mathcal {H}}_{1}}$${\görüntüleme stili P}$${\displaystyle |\psi \rangle \in {\mathcal {H}}}$${\displaystyle {\mathcal {H}}_{1}}$

Her iki alt uzayla sıfırdan farklı bir örtüşme ile normalleştirilmiş bir durum vektörü verildiğinde , onu benzersiz bir şekilde şu şekilde ayrıştırabiliriz: ${\displaystyle |\psi \rangle \in {\mathcal {H}}}$

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

nerede , ve ve sırasıyla altuzayların normalize izdüşümleridir ve , . Bu ayrıştırma, iki boyutlu bir alt uzay tanımlayan vektörler tarafından yayılmış, ve . Ölçüldüğünde sistemin iyi durumda bulunma olasılığı . ${\displaystyle \theta =\arcsin \left(\left|P|\psi \rangle \right|\right)\in [0,\pi /2]}$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{0}\rangle }$${\ Displaystyle |\psi \rangle }$${\displaystyle {\mathcal {H}}_{1}}$${\displaystyle {\mathcal {H}}_{0}}$${\ Displaystyle {\Mathcal {H}}_{\psi }}$${\displaystyle |\psi _{0}\rangle }$${\displaystyle |\psi _{1}\rangle }$${\displaystyle \sin ^{2}(\theta )}$

Üniter bir operatör tanımlayın , burada ${\displaystyle Q(\psi ,P):=-S_{\psi }S_{P}\,\!}$

${\displaystyle {\begin{aligned}S_{\psi }&=I-2|\psi \rangle \langle \psi |\quad {\text{and}}\\S_{P}&=I-2P. \end{hizalanmış}}}$

${\ Displaystyle S_{P}}$iyi altuzaydaki durumların fazını çevirirken, ilk durumun fazını çevirir . ${\ Displaystyle S_{\psi }}$${\ Displaystyle |\psi \rangle }$

Bu operatörün eylemi şu şekilde verilir: ${\ Displaystyle {\Mathcal {H}}_{\psi }}$

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

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

Böylece alt uzayda açı ile bir dönüşe karşılık gelir : ${\ Displaystyle {\Mathcal {H}}_{\psi }}$${\görüntüleme stili Q}$${\ekran stili 2\teta\,\!}$

${\displaystyle Q={\başlangıç{pmatrix}\cos(2\teta )&-\sin(2\teta )\\\sin(2\teta )&\cos(2\teta )\son{pmatrix}} }$.

Uygulama devlet zamanları verir ${\görüntüleme stili Q}$ ${\görüntüleme stili n}$${\ Displaystyle |\psi \rangle }$

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

durumu iyi ve kötü alt uzaylar arasında döndürmek . Yinelemelerden sonra sistemi iyi durumda bulma olasılığı . Seçersek olasılık maksimize edilir ${\görüntüleme stili n}$${\displaystyle \sin ^{2}((2n+1)\theta )\,\!}$

${\displaystyle n=\sol\lzemin {\frac {\pi }{4\theta }}\sağ\rkat }$.

Bu noktaya kadar her yineleme, iyi durumların genliğini artırır , dolayısıyla tekniğin adı.

Uygulamalar

N elemanlı sıralanmamış bir veritabanımız ve basitlik için aradığımız iyi girdileri tanıyabilen bir oracle fonksiyonumuz olduğunu varsayalım . ${\görüntüleme stili \chi }$${\displaystyle B_{\text{op}}=B}$

Varsa iyi toplamda veritabanındaki girdileri, o zaman başlatılıyor bunları bulabilirsiniz kuantum kayıt ile qubits nereye içine düzgün bir süperpozisyon tüm veritabanı öğelerinin öyle ki ${\görüntüleme stili G}$ ${\ Displaystyle |\psi \rangle }$${\görüntüleme stili n}$ ${\ Displaystyle 2^{n}=N}$${\görüntüleme stili N}$

${\displaystyle |\psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}|k\rangle}$

ve yukarıdaki algoritmayı çalıştırıyor. Bu durumda, ilk durumun iyi alt uzay ile örtüşmesi , veritabanındaki iyi girişlerin sıklığının kareköküne eşittir , . Eğer , gerekli yineleme sayısını şu şekilde tahmin edebiliriz: ${\displaystyle \sin(\theta )=|P|\psi \rangle |={\sqrt {G/N}}}$${\displaystyle \sin(\theta )\ll 1}$

${\displaystyle n=\sol\lzemin {\frac {\pi }{4\theta }}\sağ\rzemin \yaklaşık \sol\lzemin {\frac {\pi }{4\sin(\theta )}}\ right\rfloor =\left\lfloor {\frac {\pi }{4}}{\sqrt {\frac {N}{G}}}\right\rfloor =O({\sqrt {N}}).}$

Durumu ölçmek, şimdi yüksek olasılıkla iyi girişlerden birini verecektir . Her uygulama tek bir oracle sorgusu gerektirdiğinden (oracle'ın bir kuantum geçidi olarak uygulandığını varsayarsak ), sadece oracle sorgularıyla iyi bir giriş bulabilir , böylece mümkün olan en iyi klasik algoritma üzerinde ikinci dereceden bir hızlanma elde edebiliriz. (Veritabanında arama yapmak için klasik yöntem, bir çözüm bulunana kadar sorguyu her biri için yapmak ve böylece sorguları maliyetlendirmek olacaktır .) Ayrıca sorguları kullanarak tüm çözümleri bulabiliriz . ${\ Displaystyle S_{P}}$${\displaystyle O({\sqrt {N}})}$${\displaystyle e\in \{0,1,\dots ,N-1\}}$${\görüntüleme stili O(N)}$${\görüntüleme stili G}$${\displaystyle O({\sqrt {GN}})}$

Kümenin boyutunu bir olarak ayarlarsak , yukarıdaki senaryo esasen orijinal Grover aramasına indirgenir . ${\görüntüleme stili G}$

Kuantum Sayma

İyi girişlerin sayısının bilinmediğini varsayalım . Küçük için öyle bir tahminde bulunmayı hedefliyoruz . Kuantum fazı tahmin algoritmasını üniter operatöre uygulayarak çözebiliriz . ${\görüntüleme stili {\tilde {G}}}$${\displaystyle (1-\delta )G\leq {\tilde {G}}\leq (1+\delta )G}$${\görüntüleme stili \delta >0}$${\görüntüleme stili {\tilde {G}}}$${\görüntüleme stili Q}$

Yana ve sadece iki özdeğerler vardır , biz bunlara karşılık gelen özvektörler olalım olabilir ve . Biz özdeğer bulabilirsiniz arasında bu durumda faz tahmin eşdeğerdir, . Bu, kuantum fazı tahmin algoritmasında açıklandığı gibi Fourier dönüşümleri ve kontrollü üniter işlemler uygulanarak yapılabilir. Tahminle , tahmin edebiliriz , bu da tahmin eder . ${\görüntüleme stili e^{i2\theta}}$${\displaystyle e^{i(2\pi -2\theta )}}$${\görüntüleme stili Q}$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{2}\rangle }$${\displaystyle e^{2\pi i\theta }}$${\ Displaystyle |\psi \rangle }$${\görüntüleme stili\teta }$${\displaystyle {\tilde {\theta }}}$${\displaystyle \sin {\ teta }}$${\görüntüleme stili G}$

Özvektörler ve yerine keyfi başlangıç ​​durumu ile tahmin yapmak istediğimizi varsayalım . Biz çürüyen yapabilirsiniz doğrusal bir kombinasyonu içine ve ve sonra faz tahmin algoritması uygulanması. ${\görüntüleme stili\teta }$${\displaystyle |s\range }$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{2}\rangle }$${\displaystyle |s\range }$${\displaystyle |\psi _{1}\rangle }$${\displaystyle |\psi _{2}\rangle }$

Referanslar