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算法的結構：

我們先準備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$ 的加速。