4.4 Grover算法

  什么是搜索算法呢？举一个简单的例子，在下班的高峰期，要从公司回到家里，开车走怎样的路线才能够耗时最短呢？最简单的想法，当然是把所有可能的路线一次一次的计算，根据路况计算每条路线所消耗的时间，最终可以得到用时最短的路线，即为最快路线，这样依次的将每一种路线计算出来，最终对比得到最短路线。搜索的速度与总路线数 \(N\) 相关，记为 \(O(N)\) ，而采用量子搜索算法，则可以以 \(O(sqrt(N))\) 的速度进行搜索，要远快于传统的搜索算法。

  那么怎么实现Grover搜索算法呢？

  首先，先化简一下搜索模型，将所有数据存在数据库中，假设有 \(n\) 个量子比特，用来记录数据库中的每一个数据的索引，一共可以表示 \(2^n\) 个数据，记为 \(N\) 个；希望搜索得到的数据有 \(M\) 个，为了表示一个数据是否是搜索的结果，建立一个函数：

\[\begin{split}f(x)\left\{\begin{array}{l} 0\left(x \neq x_{0}\right) \\ 1\left(x=x_{0}\right) \end{array}\right.\end{split}\]

  其中 \(x_0\) 为搜索目标的索引值，也即是说，当搜索到目标时，函数值 \(f(x)\) 值为 \(1\) ，如果搜索的结果不是目标时， \(f(x)\) 值为 \(0\) 。假设有一个量子Oracle可以识别搜索问题的解，是别的结果通过Oracle的一个量子比特给出。可以将Oracle定义为:

\[|x\rangle|q\rangle \stackrel{\text { Oracle }}{\longrightarrow}|x\rangle|q\oplus f(x)\rangle\]

  其中 \(|q \rangle\) 是一个结果寄存器, ⨁ 是二进制加法。通过Oracle可以实现，当搜索的索引为目标结果时，结果寄存器翻转；反之，结果寄存器值不变；从而可以通过判断结果寄存器的值，来确定搜索的对象是否为目标值。

  Oracle对量子态的具体操作是什么样的呢？同D-J算法相似，先将初态制备在 \(|0\rangle^{\otimes n}\) \(|1\rangle\) 态上， \(|0\rangle^{\otimes n}\) 为查询寄存器， \(|1\rangle\) 为结果寄存器。 经过 Hardmard 门操作后，可以将查询寄存器的量子态，变为所有结果的叠加态；也即是说，经过了 Hardmard 门，就可以得到所有结果的索引，而结果寄存器则变为 \(\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)\) ，再使其通过Oracle，可以对每一个索引都进行一次检验，如果是目标结果，则将结果寄存器的量子态进行 \({0}\) 、 \({1}\) 翻转，即结果寄存器变为：

\[\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)\stackrel{\text { Oracle }}{\longrightarrow}-\frac{1}{\sqrt{2}}(|1\rangle-|0\rangle)\]

  而查询寄存器不变；但当检验的索引不是结果时，寄存器均不发生改变。因此，Oracle可以换一种表示方式：

\[\left.\left.\right|\mathbf{x}\right\rangle\left(\frac{|0\rangle-|\mathbf{1}\rangle}{\sqrt{2}}\right) \stackrel{\text { Oracle }}{\longrightarrow}(-1)^{f(x)} |\mathbf{x}\rangle\left(\frac{(0)-|\mathbf{1}\rangle}{\sqrt{2}}\right)\]

  其中， \(|x\rangle\) 是查询寄存器的等额叠加态中的一种情况。

  如上述所知，Oracle的作用，是通过改变了解的相位，标记了搜索问题的解。

  现在，将搜索问题的解通过相位标记区分出来，那么如何能够将量子态的末态变为已标记出的态呢？

  将问题换一种思路进行考虑，当查询寄存器由初态经过 Hardmard 门后，会变为所有可能情况的等额叠加态；也就是说，它包含着所有搜索问题的解与非搜索问题的解。可以将这个态记为:

\[|\psi\rangle=\frac{1}{\sqrt{N}} \sum_{x}|\mathrm{x}\rangle\]

  将所有非搜索问题的解定义为一个量子态 \(|\alpha\rangle\) ,其中 \(\Sigma_{x_{1}}\) 代表着 \(x\) 上所有非搜索问题的解的和，记为:

\[\left.\left.\right| \alpha\right\rangle=\frac{1}{\sqrt{N-M}} \sum_{x_1}|\mathrm{x}\rangle\]

  显然， \(|\beta\rangle\) 为最终的量子态，而且 \(|\alpha\rangle\) 和 \(|\beta\rangle\) 相互正交。利用简单的代数运算，就可以将初态 \(|\psi\rangle\) 重新表示为:

\[\left.\left.\right| \psi \right\rangle=\sqrt{\frac{N-M}{N}}|\alpha\rangle^{+} \sqrt{\frac{M}{N}}|\beta\rangle\]

  初始态被搜索问题的解的集合和非搜索问题的解的集合重新定义，也即是说，初态属于 \(|\alpha\rangle\) 与 \(|\beta\rangle\) 张成的空间。因此，可以用平面向量来表示这三个量子态，如图4.4.1所示:

../_images/wps577.jpg

图4.4.1

  那么，Oracle作用在新的表示方法下的初态会产生怎样的影响呢？Oracle的作用是用负号标记搜索问题的解，所以，相当于将 \(|\beta\rangle\) 内每一个态前均增加一个负号，将所有的负号提取出来，可以得到：

\[|\psi\rangle\stackrel{\text { Oracle }}{\longrightarrow} \ \sqrt{\frac{N-M}{N}}|\alpha\rangle^{-} \sqrt{\frac{\mathrm{M}}{N}}|\beta\rangle\]

  对应在平面向量中，相当于将 \(|\psi\rangle\) 做关于 \(|\alpha\rangle\) 轴的对称，但仅有这一种操作是无法将量子态从 \(|\psi\rangle\) 变为 \(|\beta\rangle\) ，还需要另一种对称操作。

  第二种对称操作，是将量子态关于 \(|\psi\rangle\) 对称的操作，这个操作由三个部分构成：

  1. 将量子态经过一个 Hardmard 门；

  2. 对量子态进行一个相位变换，将 \(|0\rangle^{\otimes n}\) 态的系数保持不变，将其他的量子态的系数增加一个负号，相当于 \(2|0\rangle\langle 0|-\mathrm{I}\) 酉变换算子；

  3. 再经过一个 Hardmard 门。

  这三步操作的数学表述为:

\[\mathrm{H}^{\otimes n}\left(2|0\rangle\langle 0|-\mathrm{I}) \mathrm{H} ^{\otimes n}=2|\psi\rangle\langle\psi|-\mathrm{1}\right.\]

  上述过程涉及到复杂的量子力学知识，这三部分的操作，只是为了实现将量子态关于 \(|\psi\rangle\) 对称。如果想了解为什么这三步操作可以实现，可以阅读关于量子计算相关书籍进一步理解。

  前面介绍的两种对称操作，合在一起称为一次Grover迭代。假设初态 \(|\psi\rangle\) 与 \(|\alpha\rangle\) 可以表示为：

\[|\psi\rangle=\cos \frac{\theta}{2}|\alpha\rangle+\sin \frac{\theta}{2}|\beta\rangle\]

  很容易得到：

\[\cos \frac{\theta}{2}=\sqrt{\frac{N-M}{N}}\]

  可以从几何图像上看到，每一次Grover迭代，可以使量子态逆时针旋转 \(\theta\) ，经历了k次Grover迭代，末态的量子态为：

\[G^{k}|\psi\rangle=\cos \left(\frac{2 k+1}{2} \theta\right)|\alpha\rangle+\sin \left(\frac{2 k+1}{2} \theta\right)|\beta\rangle\]

  因此，经过多次迭代操作，总可以使末态在 \(|\beta\rangle\) 态上概率很大，满足精确度的要求。经过严格的数学推导，可证明，迭代的次数 \(R\) 满足:

\[\mathrm{R} \leq \frac{\pi}{4} \sqrt{\frac{N}{M}}\]

  参考路线图4.4.2：

../_images/4.4.2.png

图4.4.2 线路图

  QPanda实现 Grover 算法的代码示例：

1.#include "Core/Core.h"
2.#include "Core/Utilities/Tools/Utils.h"
3.#include "QAlg/Grover/GroverAlgorithm.h"
4.#include "QAlg/Grover/QuantumWalkGroverAlg.h"
5.
6.USING_QPANDA
7.using namespace std;
8.
9.static size_t g_shot = 100000;
10.
11.static uint32_t quantum_grover_search(const std::vector<uint32_t>& search_space, const std::vector<uint32_t>& search_data,
12. std::vector<size_t>& search_result)
13.{
14. search_result.clear();
15. uint32_t search_times = 0;
16. uint32_t repeat_times = 0;
17.    auto machine = CPUQVM();
18.    machine.init();
19. machine.setConfigure({ 64,64 });
20.
21. CPUQVM _tmp_qvm;
22. _tmp_qvm.init();
23. auto x = _tmp_qvm.allocateCBit();
24.
25. std::vector<size_t> search_result_for_check;
26. for (size_t i = 0; i < search_space.size(); ++i)
27. {
28.         if (search_space[i] == search_data[0]) {
29.                 search_result_for_check.emplace_back(i);
30.         }
31. }
32.
33. cout << "Grover will search through " << search_space.size() << " data." << endl;
34. cout << "Start grover search algorithm:" << endl;
35.
36. QProg grover_Qprog;
37. QVec measure_qubits;
38. uint32_t qubit_size = 0;
39. vector<ClassicalCondition> c;
40. const double max_repeat = 3.1415926 * sqrt(((double)search_space.size()) / ((double)search_result_for_check.size())) / 4.0;
41. while (true)
42. {
43.         measure_qubits.clear();
44.         grover_Qprog = build_grover_prog(search_space, x == search_data[0], &machine, measure_qubits, ++repeat_times);
45.         search_times += repeat_times;
46.
47.         if (0 == qubit_size){
48.                 QVec _qv;
49.                 qubit_size = grover_Qprog.get_used_qubits(_qv);
50.                 printf("Number of used-qubits: %u.\n", qubit_size);
51.         }
52.
53.         if (0 == c.size()){
54.                 c = machine.allocateCBits(measure_qubits.size());
55.         }
56.
57.         grover_Qprog << MeasureAll(measure_qubits, c);
58.         write_to_originir_file(grover_Qprog, &machine, "Grover_prog.ir");
59.
60.         auto result = machine.runWithConfiguration(grover_Qprog, c, g_shot);
61.
62.         std::map<string, double> normal_result;
63.         for (const auto& _r : result){
64.                 normal_result.insert(std::make_pair(_r.first, (double)_r.second/(double)g_shot));
65.         }
66.         search_result = search_target_from_measure_result(normal_result, measure_qubits.size());
67.         if ((search_result.size() > 0)
68.                 || ((search_result.size() == 0) && (max_repeat < repeat_times))){
69.                 break;
70.         }
71. }
72. cout << "Draw grover_Qprog:" << grover_Qprog << endl;
73.    return search_times;
74.}
75.
76.int main(int argc, char* argv[])
77.{
78. int search_type = 1;
79. std::vector<uint32_t> search_data = {21};
80. /* run search algorithm */
81. std::vector<size_t> search_result;
82. uint32_t search_cnt = 0;
83. try
84. {
85.         std::vector<uint32_t> search_sapce;
86.        search_sapce.push_back(8);
87.        search_sapce.push_back(7);
88.        search_sapce.push_back(6);
89.        search_sapce.push_back(0);
90.        search_sapce.push_back(6);
91.        search_sapce.push_back(3);
92.        search_sapce.push_back(6);
93.        search_sapce.push_back(4);
94.        search_sapce.push_back(6);
95.        search_sapce.push_back(6);
96.        search_sapce.push_back(6);
97.        search_sapce.push_back(6);
98.        search_sapce.push_back(6);
99.        search_sapce.push_back(6);
100.        search_sapce.push_back(7);
101.        search_sapce.push_back(14);
102.        search_sapce.push_back(9);
103.        search_sapce.push_back(12);
104.        search_sapce.push_back(4);
105.        search_sapce.push_back(9);
106.        search_sapce.push_back(9);
107.        search_sapce.push_back(7);
108.        search_sapce.push_back(21);
109.        search_sapce.push_back(15);
110.        search_sapce.push_back(3);
111.        search_sapce.push_back(11);
112.        search_sapce.push_back(3);
113.        search_sapce.push_back(9);
114.        search_sapce.push_back(7);
115.        search_sapce.push_back(21);
116.        search_sapce.push_back(15);
117.        search_sapce.push_back(21);
118.        search_sapce.push_back(21);
119.        search_sapce.push_back(3);
120.        search_sapce.push_back(9);
121.        search_sapce.push_back(7);
122.
123.                search_cnt = quantum_grover_search(search_sapce, search_data, search_result);
124.
125.        }
126.        catch (const std::exception& e)
127.        {
128.                cout << "Got a exception: " << e.what() << endl;
129.                return -1;
130.        }
131.        catch (...)
132.        {
133.                cout << "Got an unknow exception: " << endl;
134.                return -1;
135.        }
136.
137.        cout << "Search result:\n";
138.        for (const auto &result_item : search_result)
139.        {
140.                cout << result_item << " ";
141.        }
142.        return 0;
143.}