# Bernstein-Vazarani

### 問題

我們已知一個布林函數(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$$ 的加速。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chiwei955201314.gitbook.io/quantum/bernstein-vazarani.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.