Skip to content

Latest commit

 

History

History
255 lines (206 loc) · 12.5 KB

4.4Grover算法.rst

File metadata and controls

255 lines (206 loc) · 12.5 KB
Raw

4.4 Grover算法

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

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

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

$$\begin{aligned} f(x)\left\{\begin{array}{l} 0\left(x \neq x_{0}\right) \\ 1\left(x=x_{0}\right) \end{array}\right. \end{aligned}$$

  其中 x0 为搜索目标的索引值，也即是说，当搜索到目标时，函数值 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⟩ 是一个结果寄存器, ⨁ 是二进制加法。通过Oracle可以实现，当搜索的索引为目标结果时，结果寄存器翻转；反之，结果寄存器值不变；从而可以通过判断结果寄存器的值，来确定搜索的对象是否为目标值。

  Oracle对量子态的具体操作是什么样的呢？同D-J算法相似，先将初态制备在 |0⟩ ⊗ n |1⟩ 态上， |0⟩ ⊗ n 为查询寄存器， |1⟩ 为结果寄存器。 经过 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⟩ 是查询寄存器的等额叠加态中的一种情况。

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

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

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

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

  将所有非搜索问题的解定义为一个量子态 |α⟩ ,其中 Σx1 代表着 x 上所有非搜索问题的解的和，记为:

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

  显然， |β⟩ 为最终的量子态，而且 |α⟩ 和 |β⟩ 相互正交。利用简单的代数运算，就可以将初态 |ψ⟩ 重新表示为:

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

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

image

图4.4.1

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

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

  对应在平面向量中，相当于将 |ψ⟩ 做关于 |α⟩ 轴的对称，但仅有这一种操作是无法将量子态从 |ψ⟩ 变为 |β⟩ ，还需要另一种对称操作。

  第二种对称操作，是将量子态关于 |ψ⟩ 对称的操作，这个操作由三个部分构成：

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

  2. 对量子态进行一个相位变换，将 |0⟩ ⊗ n 态的系数保持不变，将其他的量子态的系数增加一个负号，相当于 2|0⟩⟨0| − I 酉变换算子；

  3. 再经过一个 Hardmard 门。

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


H ⊗ n(2|0⟩⟨0|−I)H ⊗ n=2|ψ⟩⟨ψ|−1

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

  前面介绍的两种对称操作，合在一起称为一次Grover迭代。假设初态 |ψ⟩ 与 |α⟩ 可以表示为：

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

  很容易得到：

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

  可以从几何图像上看到，每一次Grover迭代，可以使量子态逆时针旋转 θ ，经历了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$$

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

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

  参考路线图4.4.2：

image

图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.}