# 格罗弗算法

## 設定

${\displaystyle {\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega \\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega \end{cases}}}}$

${\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle }$

${\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle }$

{\displaystyle {\begin{aligned}U_{f}|x\rangle |-\rangle &=U_{f}|x\rangle \left[{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\right]\\&={\begin{cases}{\frac {1}{\sqrt {2}}}(|x\rangle |1\rangle -|x\rangle |0\rangle )&{\text{for }}x=\omega \\{\frac {1}{\sqrt {2}}}(|x\rangle |0\rangle -|x\rangle |1\rangle )&{\text{for }}x\neq \omega \end{cases}}\\&=(-1)^{f(x)}|x\rangle |-\rangle \end{aligned}}}

## 算法步驟

1. 构建量子叠加态
${\displaystyle |s\rangle =H^{\otimes N}|0\rangle ^{\otimes N}={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle }$
2. 做${\displaystyle p(N)}$次“格罗弗迭代”，具体操作如下
• ${\displaystyle U_{\omega }}$作用在${\displaystyle |s\rangle }$
• ${\displaystyle U_{s}=2|s\rangle \langle s|-I}$ 作用在${\displaystyle |s\rangle }$

3. 测量${\displaystyle |s\rangle }$，得到求得的结果

## 正确性证明

##### 代数证明

${\displaystyle |s\rangle =a|\omega \rangle +b|x\rangle }$

${\displaystyle U_{s}:a|\omega \rangle +b|x\rangle \mapsto [|\omega \rangle \,|x\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.}$
${\displaystyle U_{\omega }:a|\omega \rangle +b|x\rangle \mapsto [|\omega \rangle \,|x\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.}$

${\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}$

${\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}$ where ${\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}$

${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}$

${\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}.}$

${\displaystyle [|\omega \rangle \,|x\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|x\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|x\rangle {\frac {\sin(t)}{\cos(t)}}.}$

## 參考資料

1. ^ Bennett C.H.; Bernstein E.; Brassard G.; Vazirani U. The strengths and weaknesses of quantum computation. . 1997, 26 (5): 1510–1523 [2019-06-12]. . doi:10.1137/s0097539796300933. （原始内容存档于2016-03-06）.
2. ^ Aaronson, Scott. Quantum Computing and Hidden Variables (PDF). （原始内容存档 (PDF)于2020-12-03）.
3. ^ Daniel J. Bernstein. Grover vs. McEliece (PDF). 2010-03-03 [2019-06-12]. （原始内容 (PDF)存档于2010-10-10）.