[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/bernstein-vazirani-algorithm-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki19\/bernstein-vazirani-algorithm-wikipedia\/","headline":"Bernstein\u2013Vazirani algorithm – Wikipedia","name":"Bernstein\u2013Vazirani algorithm – Wikipedia","description":"From Wikipedia, the free encyclopedia Quantum algorithm The Bernstein\u2013Vazirani algorithm, which solves the Bernstein\u2013Vazirani problem, is a quantum algorithm invented","datePublished":"2022-03-23","dateModified":"2022-03-23","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki19\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/1\/15\/Bernstein-Vazirani_quantum_circuit.png\/220px-Bernstein-Vazirani_quantum_circuit.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/1\/15\/Bernstein-Vazirani_quantum_circuit.png\/220px-Bernstein-Vazirani_quantum_circuit.png","height":"84","width":"220"},"url":"https:\/\/wiki.edu.vn\/en\/wiki19\/bernstein-vazirani-algorithm-wikipedia\/","wordCount":6453,"articleBody":"From Wikipedia, the free encyclopediaQuantum algorithm  The Bernstein\u2013Vazirani algorithm, which solves the Bernstein\u2013Vazirani problem,  is a quantum algorithm invented by Ethan Bernstein and Umesh Vazirani in 1992.[1] It is a restricted version of the Deutsch\u2013Jozsa algorithm  where instead of distinguishing between two different classes of functions, it tries to learn a string encoded in a function.[2]  The Bernstein\u2013Vazirani algorithm was designed to prove an oracle separation between complexity classes BQP and BPP.[1]Problem statement[edit]Given an oracle that implements a function f:{0,1}n\u2192{0,1}{displaystyle fcolon {0,1}^{n}rightarrow {0,1}} in which f(x){displaystyle f(x)} is promised to be the dot product between x{displaystyle x} and a secret string s\u2208{0,1}n{displaystyle sin {0,1}^{n}} modulo 2, f(x)=x\u22c5s=x1s1\u2295x2s2\u2295\u22ef\u2295xnsn{displaystyle f(x)=xcdot s=x_{1}s_{1}oplus x_{2}s_{2}oplus cdots oplus x_{n}s_{n}}, find s{displaystyle s}.Algorithm[edit]Classically, the most efficient method to find the secret string is by evaluating the function n{displaystyle n} times with the input values x=2i{displaystyle x=2^{i}} for all i\u2208{0,1,...,n\u22121}{displaystyle iin {0,1,…,n-1}}:[2]f(1000\u22ef0n)=s1f(0100\u22ef0n)=s2f(0010\u22ef0n)=s3\u22eef(0000\u22ef1n)=sn{displaystyle {begin{aligned}f(1000cdots 0_{n})&=s_{1}\\f(0100cdots 0_{n})&=s_{2}\\f(0010cdots 0_{n})&=s_{3}\\&,,,vdots \\f(0000cdots 1_{n})&=s_{n}\\end{aligned}}}In contrast to the classical solution which needs at least n{displaystyle n} queries of the function to find s{displaystyle s}, only one query is needed using quantum computing. The quantum algorithm is as follows: [2]Apply a Hadamard transform to the n{displaystyle n} qubit state |0\u27e9\u2297n{displaystyle |0rangle ^{otimes n}} to get12n\u2211x=02n\u22121|x\u27e9.{displaystyle {frac {1}{sqrt {2^{n}}}}sum _{x=0}^{2^{n}-1}|xrangle .}Next, apply the oracle Uf{displaystyle U_{f}} which transforms |x\u27e9\u2192(\u22121)f(x)|x\u27e9{displaystyle |xrangle to (-1)^{f(x)}|xrangle }. This can be simulated through the standard oracle that transforms |b\u27e9|x\u27e9\u2192|b\u2295f(x)\u27e9|x\u27e9{displaystyle |brangle |xrangle to |boplus f(x)rangle |xrangle } by applying this oracle to |0\u27e9\u2212|1\u27e92|x\u27e9{displaystyle {frac {|0rangle -|1rangle }{sqrt {2}}}|xrangle }. (\u2295{displaystyle oplus } denotes addition mod two.) This transforms the superposition into12n\u2211x=02n\u22121(\u22121)f(x)|x\u27e9.{displaystyle {frac {1}{sqrt {2^{n}}}}sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|xrangle .}Another Hadamard transform is applied to each qubit which makes it so that for qubits where si=1{displaystyle s_{i}=1}, its state is converted from |\u2212\u27e9{displaystyle |-rangle } to |1\u27e9{displaystyle |1rangle } and for qubits where si=0{displaystyle s_{i}=0}, its state is converted from |+\u27e9{displaystyle |+rangle } to |0\u27e9{displaystyle |0rangle }. To obtain s{displaystyle s}, a measurement in the standard basis ({|0\u27e9,|1\u27e9}{displaystyle {|0rangle ,|1rangle }}) is performed on the qubits.Graphically, the algorithm may be represented by the following diagram, where H\u2297n{displaystyle H^{otimes n}} denotes the Hadamard transform on n{displaystyle n} qubits:|0\u27e9n\u2192H\u2297n12n\u2211x\u2208{0,1}n|x\u27e9\u2192Uf12n\u2211x\u2208{0,1}n(\u22121)f(x)|x\u27e9\u2192H\u2297n12n\u2211x,y\u2208{0,1}n(\u22121)f(x)+x\u22c5y|y\u27e9=|s\u27e9{displaystyle |0rangle ^{n}xrightarrow {H^{otimes n}} {frac {1}{sqrt {2^{n}}}}sum _{xin {0,1}^{n}}|xrangle xrightarrow {U_{f}} {frac {1}{sqrt {2^{n}}}}sum _{xin {0,1}^{n}}(-1)^{f(x)}|xrangle xrightarrow {H^{otimes n}} {frac {1}{2^{n}}}sum _{x,yin {0,1}^{n}}(-1)^{f(x)+xcdot y}|yrangle =|srangle }The reason that the last state is |s\u27e9{displaystyle |srangle } is because, for a particular y{displaystyle y},12n\u2211x\u2208{0,1}n(\u22121)f(x)+x\u22c5y=12n\u2211x\u2208{0,1}n(\u22121)x\u22c5s+x\u22c5y=12n\u2211x\u2208{0,1}n(\u22121)x\u22c5(s\u2295y)=1\u00a0if\u00a0s\u2295y=0\u2192,0\u00a0otherwise.{displaystyle {frac {1}{2^{n}}}sum _{xin {0,1}^{n}}(-1)^{f(x)+xcdot y}={frac {1}{2^{n}}}sum _{xin {0,1}^{n}}(-1)^{xcdot s+xcdot y}={frac {1}{2^{n}}}sum _{xin {0,1}^{n}}(-1)^{xcdot (soplus y)}=1{text{ if }}soplus y={vec {0}},,0{text{ otherwise}}.}Since s\u2295y=0\u2192{displaystyle soplus y={vec {0}}} is only true when s=y{displaystyle s=y}, this means that the only non-zero amplitude is on |s\u27e9{displaystyle |srangle }. So, measuring the output of the circuit in the computational basis yields the secret string s{displaystyle s}.See also[edit]References[edit]  "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki19\/bernstein-vazirani-algorithm-wikipedia\/#breadcrumbitem","name":"Bernstein\u2013Vazirani algorithm – Wikipedia"}}]}]