> For the complete documentation index, see [llms.txt](https://chiwei955201314.gitbook.io/quantum/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://chiwei955201314.gitbook.io/quantum/bernstein-vazarani.md).

# Bernstein-Vazarani

本章節將了解 Berstein-Vazarani algorithm的問題以及算法

### 問題

我們已知一個布林函數(boolean function)：

$$
f:\left{0,1\right}^n\rightarrow\left{0,1\right}\tag{1}
$$

布林函數的形式如下：

$$
f(x)=s\cdot x\ mod\ 2\tag{2}
$$

$$x$$ 為任意n-bit的輸入， $$s$$為 "secret string"， 函數 $$f$$ 會先將 $$s$$字串 和 $$x$$字串內積後，再mod 2，並輸出結果，而問題就是，請找出字串 $$s$$ 

### 經典算法

經典算法中，我們需要n次的query，舉例如下(假設n = 4)：

$$
f(1000) = s\_1\\
f(0100) = s\_2\\
f(0010) = s\_3\\
f(0001) = s\_4
$$

而顯而易見的，完整的字串 $$s$$ 就是 $$s\_1s\_2s\_3s\_4$$ ，在此經典算法中，其時間複雜度為

$$
O(n)
$$

並且， $$n$$ query已經是經典算法的lower bound，很簡單就能證明， $$s$$ 總共有 $$2^n$$ 個可能，而每次的query，都能將這個空間一分為二，所以很明顯要 $$n$$ 次才能得出最終結果。

然而量子算法(Bernstein-Vazarani algorithm)卻能加速到

$$
O(1)
$$

現在就讓我們來看看是如何做到的！

### 量子算法(Bernstein-Vazarani algorithm)

下圖是Bernstein-Vazarani算法的結構：

![](https://3865886813-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LpMm0E0vvjg46Qr8IPS%2F-LpfKldr-iP8xkPhafrO%2F-LpfOYaC-X6UwgcuDY6d%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202019-09-26%20%E4%B8%8A%E5%8D%8810.28.10.png?alt=media\&token=d14e7b74-8584-4f62-ab1c-a0050733ab1c)

我們先準備n-qbits，並且初始化在 $$|0\rangle^{\otimes n}$$ 經過Hadamard gate後，query 函數 $$f$$ ，再經過一次Hadamard gate後，就能觀測到正確答案，接下來證明一下其正確性：

$$
\begin{aligned}
|0\rangle^{\otimes n}
&\xrightarrow{H}\frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}|x\rangle\\
&\xrightarrow{f}\frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}(-1)^{f(x)}|x\rangle\\
&\ =\ \ \frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}(-1)^{s\cdot x}|x\rangle\\
&\ =\ \ \frac{1}{\sqrt{2^n}}\sum\_{x\in\left{0,1\right}^n}(-1)^{s\_1\cdot x\_1}\cdots(-1)^{s\_n\cdot x\_n}|x\rangle\\
\end{aligned}
$$

緊接著，在對每個qbit做一次Hadamard transform，如果 $$s\_i = 1$$ ，該qbit會從 $$|-\rangle\to|1\rangle$$ ，反之亦然。

Berstein-Vazarni只需要query一次就能得到答案，相較於經典版本，是 $$n\to1$$ 的加速。