Bernstein-Vazirani algoritması - Bernstein–Vazirani algorithm

Bernstein-Vazirani algoritması çözer, Bernstein-Vazirani sorununu bir olan kuantum algoritması tarafından icat Ethan Bernstein ve Umesh Vazirani Bu bir yasak versiyonu 1992 yılında Deutsch-Józsa algoritması , bu dener fonksiyonların iki farklı sınıflar arasında ayrım nerede yerine bir işlevde kodlanmış bir dize öğrenmek için. Bernstein-Vazirani algoritma, bir kanıtlamak için tasarlanmıştır torpil ayırma arasında karmaşıklık sınıfları BQP ve BPP .

Sorun bildirimi

Bir Verilen kahin uygular bir işlev olduğunu hangi edilir vaat olmak iççarpım arasında ve gizli bir dize modülo 2, bulmak . ${\displaystyle f\colon \{0,1\}^{n}\rightarrow \{0,1\}}$${\görüntüleme stili f(x)}$${\görüntüleme stili x}$${\displaystyle s\in \{0,1\}^{n}}$ ${\displaystyle f(x)=x\cdot s=x_{1}s_{1}\oplus x_{2}s_{2}\oplus \cdots \oplus x_{n}s_{n}}$${\görüntüleme stili s}$

algoritma

Klasik olarak, gizli diziyi bulmanın en etkili yöntemi, işlev sürelerini tümü için giriş değerleriyle değerlendirmektir : ${\görüntüleme stili n}$${\görüntüleme stili x=2^{i}}$${\displaystyle i\in \{0,1,...,n-1\}}$

${\displaystyle {\begin{aligned}f(1000\cdots 0_{n})&=s_{1}\\f(0100\cdots 0_{n})&=s_{2}\\f(0010\cdots) 0_{n})&=s_{3}\\&\,\,\,\vdots \\f(0000\cdots 1_{n})&=s_{n}\\\end{hizalı}}}$

Bulmak için fonksiyonun en azından sorgularına ihtiyaç duyan klasik çözümün aksine , kuantum hesaplama kullanılarak yalnızca bir sorguya ihtiyaç vardır. Kuantum algoritması aşağıdaki gibidir: ${\görüntüleme stili n}$${\görüntüleme stili s}$

Bir Uygula Hadamard dönüşümü için qubit devlet olsun için ${\görüntüleme stili n}$${\displaystyle |0\menzil ^{\otimes n}}$

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle .}$

Ardından, dönüştüren oracle'ı uygulayın . Bu, bu oracle'ı . ( mod iki eklemeyi belirtir.) Bu, süperpozisyonu şuna dönüştürür: ${\görüntüleme stili U_{f}}$${\displaystyle |x\rangle \to (-1)^{f(x)}|x\rangle }$${\displaystyle |b\rangle |x\rangle \to |b\oplus f(x)\rangle |x\rangle }$${\displaystyle {\frac {|0\rangle -|1\rangle }{\sqrt {2}}}|x\rangle }$${\görüntüleme stili\oplus }$

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)} |x\menzil .}$

Hadamard dönüşüm başka böylece yapan her QuBit uygulanır qubits için , devlet dönüştürülür, için ve qubits için , devlet dönüştürülür, için . elde etmek için, kübitler üzerinde standart bazda ( ) bir ölçüm yapılır. ${\displaystyle s_{i}=1}$${\görüntüleme stili |-\menzil }$${\görüntüleme stili |1\menzil }$${\displaystyle s_{i}=0}$${\görüntüleme stili |+\menzil }$${\görüntüleme stili |0\menzil }$${\görüntüleme stili s}$${\displaystyle \{|0\rangle ,|1\rangle \}}$

Grafiksel olarak, algoritma , kübitler üzerindeki Hadamard dönüşümünü gösteren aşağıdaki diyagram ile temsil edilebilir : ${\ Displaystyle H^{\otimes n}}$${\görüntüleme stili n}$

${\displaystyle |0\rangle ^{n}\xrightarrow {H^{\otimes n}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0 ,1\}^{n}}|x\rangle \xrightarrow {U_{f}} {\frac {1}{\sqrt {2^{n}}}}\sum _{x\in \{0, 1\}^{n}}(-1)^{f(x)}|x\rangle \xrightarrow {H^{\otimes n}} {\frac {1}{2^{n}}}\sum _{x,y\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}|y\rangle =|s\rangle }$

Son durumun olmasının nedeni, belirli bir durum için , ${\displaystyle |s\rangle }$${\görüntüleme stili y}$

${\displaystyle {\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{f(x)+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot s+x\cdot y}={\frac {1}{2^{n}}}\sum _{x\in \{0,1\}^{n}}(-1)^{x\cdot (s\oplus y )}=1{\text{ ise }}s\oplus y={\vec {0}},\,0{\text{ aksi halde}}.}$

Yana sadece doğru olduğunda sadece sıfır olmayan genlik, bu araçlar üzerinde olduğunu . Böylece, devrenin çıktısını hesaplama bazında ölçmek, gizli diziyi verir . ${\displaystyle s\oplus y={\vec {0}}}$${\görüntüleme stili s=y}$${\displaystyle |s\rangle }$${\görüntüleme stili s}$

Ayrıca bakınız

• Gizli Doğrusal İşlev sorunu

Referanslar