查看“︁格罗弗算法”︁的源代码

{{multiple issues|
{{expand english|time=2019-06-12T09:13:41+00:00}}
{{original research|time=2019-06-12T09:13:41+00:00}}
{{refimprove|time=2019-06-12T09:13:41+00:00}}
}}
{{NoteTA
|G1 = IT
}}
'''格罗弗算法'''（{{lang-en|Grover's algorithm}}）是一種量子算法，於1996年由電腦科學家[[洛夫·格罗弗]]提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數<math>O(\sqrt{N})</math>次，其中<math>N</math>為此未知函數的[[定义域]]的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。

同樣的問題在經典運算下，需要至少做 <math>O(N)</math> 次測試（因為在最壞的情況下，可能第<math>N</math>個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, Brassard, 和 Vazirani 在相近的時間證明了，任何量子算法解決此問題都最少需要對此未知的函數做 <math>\Omega(\sqrt{N})</math> 次測試，因此格罗弗算法是[[渐进最优]]的。<ref name=bennett_1997>{{cite journal
 |title        = The strengths and weaknesses of quantum computation
 |author1      = Bennett C.H.
 |author2      = Bernstein E.
 |author3      = Brassard G.
 |author4      = Vazirani U.
 |journal      = {{tsl|en|SIAM Journal on Computing||SIAM Journal on Computing}}
 |date         = 1997
 |volume       = 26
 |issue        = 5
 |pages        = 1510&ndash;1523
 |url          = http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps
 |doi          = 10.1137/s0097539796300933
 |arxiv        = quant-ph/9701001
 |access-date  = 2019-06-12
 |archive-date = 2016-03-06
 |archive-url  = https://web.archive.org/web/20160306060334/http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps
 |dead-url     = no
}}</ref>

非局域隱變量量子計算機已經被證明可以在最多 <math>O(\sqrt[3]{N})</math> 步內實現在N個條目的數據庫裡的搜索，這比格罗弗算法的 <math>O(\sqrt{N})</math> 還快，然而這些搜索算法並不能使量子計算機在多項式時間內解決NP-Complete 問題。<ref>{{Cite web|url=http://www.scottaaronson.com/papers/qchvpra.pdf|title=Quantum Computing and Hidden Variables|last=Aaronson|first=Scott|date=|website=|archive-url=https://web.archive.org/web/20201203231041/https://www.scottaaronson.com/papers/qchvpra.pdf|archive-date=2020-12-03|dead-url=no|access-date=}}</ref>

不像其他的量子算法可能會比相應的經典算法有指數級的加快，格罗弗算法二次方的加快，不過當<math>N</math>很大時二次方的加快也相當可觀。格罗弗算法可以在大約 2<sup>64</sup>次迭代內窮舉破解一個128比特的對稱密鑰，在大約 2<sup>128</sup>次迭代內窮舉破解一個256比特的密鑰。因此，有人提倡對稱密鑰的長度應該加倍以因應未來的量子攻擊。<ref name="djb-groverr">{{cite journal |date=2010-03-03 |author=[[Daniel J. Bernstein]] |title=Grover vs. McEliece |url=http://cr.yp.to/codes/grovercode-20100303.pdf |access-date=2019-06-12 |archive-date=2010-10-10 |archive-url=https://web.archive.org/web/20101010222754/http://cr.yp.to/codes/grovercode-20100303.pdf |dead-url=yes }}</ref>

像其他的量子算法一樣，格罗弗算法是概率性的，意味著這個算法以小於1的概率給出正確答案。雖然實際上對於需要多少次重複才能給出正確的答案並沒有一個上界，但是期望的重複次數並不隨<math>N</math>成長。在格罗弗發表此算法的原始論文中稱此算法為數據庫搜索算法，此說法至今仍普遍。此處數據庫相當於是一張存有未知函數的所有輸出值的表，以對應的輸入值為索引。

==應用==
雖然格罗弗算法的用處一直被認為是數據庫搜索，但是它也可以被認為是函數取反。

==設定==
考虑一个有N个元素的无序数据集，我们设函数<math>{\displaystyle f:\{0,1,\ldots ,N-1\}\to \{0,1\}}</math>。我们假设，在所有的下标x中，有且仅有一个下标x有<math>f(x)=1</math>，我们记这个下标x为<math>\omega</math>，并且称<math>\omega</math>为这个搜索问题的解。而格罗弗算法的目标便是找到下标<math>\omega</math>。为此，我们构建一个酉算子<math>U_\omega</math>，如下

<math>{\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}}}</math>

或者可以简写为

<math>U_\omega|x\rang=(-1)^{f(x)}|x\rang</math>

事实上，我们一般构建另一种酉算子<math>U_f</math>，如下所示

<math>U_f|x\rang|y\rang=|x\rang|y\oplus f(x)\rang</math>

我们一般将<math>U_f</math>作用在态矢量和<math>|-\rang</math>的叠加态上，以实现相回传(Phase Kickback)，具体流程如下

<math>\begin{align}
    U_f|x\rang|-\rang&=U_f|x\rang\left[\frac{|0\rang-|1\rang}{\sqrt{2}}\right]\\
    &={\begin{cases} \frac{1}{\sqrt{2}}(|x\rang|1\rang-|x\rang|0\rang) &{\text{for }}x=\omega\\
    \frac{1}{\sqrt{2}}(|x\rang|0\rang-|x\rang|1\rang) &{\text{for }}x\neq \omega\end{cases}}\\
    &=(-1)^{f(x)}|x\rang|-\rang
\end{align}</math>

与一般的<math>U_\omega</math>相比，<math>U_f</math>使用了一个辅助的qubit。

==算法步驟==
[[File:Grovers algorithm.svg|500px|thumb|right|格罗弗算法的[[量子电路]]表示]]
格罗弗算法的步骤如下

# 构建量子叠加态
:<math>|s\rangle = H^{\otimes N}|0\rang^{\otimes N} = \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle</math>
:2. 做<math>p(N)</math>次“格罗弗迭代”，具体操作如下
:* 将<math>U_\omega</math>作用在<math>|s\rang</math>上
:* 将<math> U_s = 2 |s\rangle \langle s| - I</math> 作用在<math>|s\rang</math>上
:其中，<math>U_s</math>被称为格罗弗扩散算子
:3. 测量<math>|s\rang</math>，得到求得的结果
一般而言，<math>p(N)</math>的值会很大程度上影响得到正确结果的概率，且并不是<math>p(N)</math>越大得到正确结果的概率越大。分析表明最优的<math>p(N)</math>有<math>p(N) \leq \Big\lceil\frac{\pi}{4}\sqrt{N}\Big\rceil</math>，因而格罗弗算法的复杂度为<math>\mathcal{O}(\sqrt{N})</math>

== 正确性证明 ==

===== 几何直观证明 =====
格罗弗算法使用的技巧为振幅减枝(Amplitude amplification)，实则是通过将其他态的振幅转移为解的振幅，而是在测量时使得坍塌为解的概率增加。具体如下

===== 代数证明 =====
考虑，我们将态矢量改为以<math>|x\rang,|\omega\rang</math>为基，其中<math>\omega</math>为解。写作

<math>|s\rang=a|\omega\rang+b|x\rang</math>

在这种表示下，我们可以将<math>U_s</math>和<math>U_\omega</math>表示为

: <math> U_s : a |\omega \rang + b |x \rang \mapsto [|\omega \rang \, | x \rang] \begin{bmatrix}
-1 & 0 \\
2/\sqrt{N} & 1 \end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}.</math>
: <math> U_\omega : a |\omega \rang + b |x \rang \mapsto [|\omega \rang \, | x \rang] \begin{bmatrix}
-1 & -2/\sqrt{N} \\
0 & 1 \end{bmatrix}\begin{bmatrix}a\\b\end{bmatrix}.</math>

<math> U_sU_\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}.</math>

我们可以通过设<math>t = \arcsin(1/\sqrt{N})</math>，将上式改写为（所谓Jordan form）

<math> U_sU_\omega = M \begin{bmatrix} e^{2it} & 0 \\ 0 & e^{-2it}\end{bmatrix} M^{-1}</math> where <math>M = \begin{bmatrix}-i & i \\ e^{it} & e^{-it} \end{bmatrix}.</math>

作用r次<math>U_s</math><math>U_\omega</math>则将得到

<math> (U_sU_\omega)^r = M \begin{bmatrix} e^{2rit} & 0 \\ 0 & e^{-2rit}\end{bmatrix} M^{-1}.</math>

注意到，我们的目的是区别解以及其他一般的数据，而为了达到这个目的，我们使<math>|x\rang,|\omega\rang</math>的振幅差别越大越好，换言之，要使得2''rt''和−2''rt''的差别足够大，便有<math>2rt \approx \pi/2</math>, 或 <math>r = \pi/4t = \pi/4\arcsin(1/\sqrt{N}) \approx \pi\sqrt{N}/4</math>. 这样以来，就有

<math> (U_sU_\omega)^r = M \begin{bmatrix} i & 0 \\ 0 & -i\end{bmatrix} M^{-1}.</math>

作用在初始态上将会有

<math> [|\omega \rang \, | x \rang] (U_sU_\omega)^r \begin{bmatrix}0\\1\end{bmatrix} \approx [|\omega \rang \, | x \rang] M \begin{bmatrix} i & 0 \\ 0 & -i\end{bmatrix} M^{-1} \begin{bmatrix}0\\1\end{bmatrix} = | \omega \rang \frac{1}{\cos(t)} - |x \rang \frac{\sin(t)}{\cos(t)}.</math>

简短的计算表明，格罗弗算法将具有<math>O\left (\frac{1}{N} \right)</math>量级的误差.

==参见==
* {{tsl|en|Amplitude amplification||Amplitude amplification}}
* [[秀爾演算法]]

== 參考資料 ==
{{Reflist|2}}

==外部链接==
{{Wikiquote}}
* {{cite web
 |url          = http://davy.wtf/quantum/?example=Grover%27s%20Algorithm
 |title        = Quantum Circuit Simulator
 |author       = Davy Wybiral
 |access-date  = 2017-01-13
 |archive-url  = https://web.archive.org/web/20170116155032/http://davy.wtf/quantum/?example=Grover%27s%20Algorithm
 |archive-date = 2017-01-16
 |dead-url     = yes
 |df           = 
}}
* {{cite web
| url=http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm
| title=Grover’s Quantum Search Algorithm
| author=Craig Gidney
| date=2013-03-05
| accessdate=2019-06-12
| archive-date=2020-11-17
| archive-url=https://web.archive.org/web/20201117095032/http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm
| dead-url=no
}}
* {{cite web
| url=http://people.irisa.fr/Francois.Schwarzentruber/mit1_algo2_2013/grover_s_algorithm/
| title=Grover's algorithm
| author=François Schwarzentruber
| date=2013-05-18
| accessdate=2019-06-12
| archive-date=2020-11-16
| archive-url=https://web.archive.org/web/20201116165125/http://people.irisa.fr/Francois.Schwarzentruber/mit1_algo2_2013/grover_s_algorithm/
| dead-url=no
}}
* {{cite web
| url=http://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/
| title=Quantum Circuit Implementing Grover's Search Algorithm
| author=Alexander Prokopenya
| publisher=[[Wolfram Alpha]]
| accessdate=2019-06-12
| archive-date=2020-11-20
| archive-url=https://web.archive.org/web/20201120031050/https://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/
| dead-url=no
}}
* {{springer|title=Quantum computation, theory of|id=p/q130020}}
* {{cite web
| url=https://github.com/rmaestre/quantumSystem
| title=Grover's Algorithm implemented in R and C
| author=Roberto Maestre
| date=2018-05-11
| access-date=2019-06-12
| archive-date=2021-10-17
| archive-url=https://web.archive.org/web/20211017105042/https://github.com/rmaestre/quantumSystem
| dead-url=no
}}

{{量子信息}}

[[Category:量子演算法]]
[[Category:搜尋演算法]]
[[Category:后量子密码学]]