Grover 的搜索算法解析

23ars

4.95/5 (8投票s)

2016年10月2日

GPL3

4分钟阅读

26210

在之前的一篇文章中，我讨论了我编写的量子计算库，并以 Deutsch 算法的实现为例进行了演示。在本文中，我将介绍 Grover 搜索算法。

引言

在之前的一篇文章中，我讨论了我编写的量子计算库，并以 Deutsch 算法的实现为例进行了演示。在本文中，我将介绍 Grover 搜索算法。

Lov Grover 在 1996 年提出的算法利用量子干涉的特性来解决一项极具挑战性的任务，即在无序集合 $N=2^{n}$ 中搜索某个参数的值，在该参数下，定义的函数返回特定的结果。该算法在量子计算机上仅需 $O(\sqrt{N})$ 次运算即可完成搜索，而用于无序数据搜索的最佳经典算法需要 O(N) 时间。

背景

Grover 算法从一个 n 量子比特的量子寄存器开始，其中 n 是表示 $2^{n}=N$ 的搜索空间所需的量子比特数，所有量子比特都初始化为 $|0\rangle$

$\begin{equation} |0^{\otimes n}\rangle=|0\rangle \end{equation} $

第一步是将系统置于状态的等概率叠加中，通过应用 Hadamard 变换 $H^{\otimes n}$ 来实现

$ \begin{equation} |\psi\rangle=H^{\otimes n}|0^{\otimes n}\rangle=\frac{1}{\sqrt{2^{n}}}\displaystyle\sum_{x=0}^{2^{n}-1}|x\rangle \end{equation} $

下一系列变换通常称为 Grover 迭代，它将被重复 $\frac{\pi}{4}{\sqrt{2^{n}}}$ 次。调用量子神谕 O，这是一个可以观察和修改系统而不会将其坍缩为经典状态的量子黑盒，代表了 Grover 迭代的第一步。

$ \begin{equation} |x\rangle\xrightarrow{O}(-1)^{f(x)}|x\rangle \end{equation} $

其中 $f(x)=1$ 如果 x 是正确的状态，否则为 0。

迭代的下一部分称为扩散变换，它执行关于平均值的反演，变换每个状态的振幅。扩散变换包括再次应用 Hadamard 变换 $H^{\otimes n}$，然后是条件相移，该相移将除 $|0\rangle$ 之外的每个状态移动 -1，最后再次进行 Hadamard 变换。

条件相移可以用酉算子表示

$ \begin{equation} 2|0^{\otimes n}\rangle\langle 0^{\otimes n}|-I \end{equation} $

给定整个扩散变换，使用等式 2 中的符号 $\psi$

$ \begin{equation} H^{\otimes n}[2|0^{\otimes n}\rangle\langle 0^{\otimes n}|-I]H^{\otimes n}= 2H^{\otimes n}|0^{\otimes n}\rangle\langle 0^{\otimes n}|H^{\otimes n}-I= 2|\psi^{\otimes n}\rangle\langle\psi^{\otimes n}|-I \end{equation} $

以及整个 Grover 迭代

$ \begin{equation} [2|\psi^{\otimes n}\rangle\langle\psi^{\otimes n}|-I]O \end{equation} $

示例

假设有一个来自 n 个二进制参数的二元函数，它仅在其中一个参数上接受值 1。需要找到 f(x)=1 的输入参数值。

所以，让我们考虑以下任务

$ \begin{equation} f(x_1,x_2,x_3)=x_1\&x_2\&x_3 \end{equation} $

。此函数仅在八个输入值变体之一中接受值 1，更准确地说，当

$ \begin{equation} x_1=x_2=x_3=1\Rightarrow f(x_1,x_2,x_3)=1 \end{equation} $

算法步骤

初始状态 $|0^{\otimes n}\rangle$
将 Hadamard 变换应用于所有量子比特：$H^{\otimes n}|0^{\otimes n}\rangle$
应用 Grover 迭代 3 次
测量寄存器

结果

以下 8x8 矩阵对应于表格

$ O= \begin{pmatrix} 1&0&0&0&0&0&0&0 \\ 0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&0 \\ 0&0&0&1&0&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&0&0&1&0 \\ 0&0&0&0&0&0&0&-1 \end{pmatrix} $

现在我们有了神谕，让我们计算扩散矩阵

$ D=2|+^{\otimes n}\rangle\langle +^{\otimes n}|-I_n $

最后，如果我们应用 Grover 迭代 3 次，我们将获得

$ |\psi\rangle= \begin{bmatrix} -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ 0.574524 \end{bmatrix} $

使用代码

首先，在开始实现 Grover 算法中的步骤之前，我们将定义一个用于创建扩散矩阵的方法

	private void generateDiffusionMatrix() {
		diffusionMatrix = QuantumOperations.outerProduct(qubitPlus, qubitPlus);
		diffusionMatrix = MatrixOperations.multiplyByConstant(diffusionMatrix, 2);
		ComplexNumber[][] identityMatrix = MatrixOperations.generateIdentityMatrix(8);
		diffusionMatrix = MatrixOperations.subtract(diffusionMatrix, identityMatrix);
	}

该实现将有 3 个公共方法：

init() - 将创建 Hadamard 门对象、量子比特对象并设置初始状态；
run() - 将执行 Grover 迭代 3 次；
measure() - 将执行测量

	@Override
	public void init() {
	    //create gate object
	    gateH = gateFactory.getGate(EGateTypes.E_HadamardGate);
		//initialize resultQubit with QubitZero()
        resultQubit = QUBIT_0;
        //create |+> object
		qubitPlus = new QubitPlus();
        //entangle the resultQubit, qubitPlus
		for (int i = 0; i < NO_OF_INPUT - 1; i++) {
			resultQubit = QuantumOperations.entangle(resultQubit, QUBIT_0);
		}
		for (int i = 0; i < NO_OF_INPUT - 1; i++) {
			qubitPlus = QuantumOperations.entangle(qubitPlus, new QubitPlus());
		}
		gateHn = gateH.getUnitaryMatrix();
		for (int i = 0; i < NO_OF_INPUT - 1; i++) {
			gateHn = MatrixOperations.tensorProduct(gateHn, gateH.getUnitaryMatrix());
		}
        //set the oracle
		setOracle(oracleMatrix);
        //generate diffusion matrix
		generateDiffusionMatrix();
	}

    @Override
	public void run() {
        //calculate the needed number of iterations
		int noOfIterations = (int) Math.sqrt(Math.pow(2, NO_OF_INPUT));
        //apply Hadamard gate
		resultQubit = QuantumOperations.applyGate(resultQubit, gateHn);
        //perform the Grover iterations
		for (int i = 0; i < noOfIterations + 1; i++) {
			resultQubit = QuantumOperations.applyGate(resultQubit, oracleMatrix);
			resultQubit = QuantumOperations.applyGate(resultQubit, diffusionMatrix);
		}
        //test if resulted qubit is valid
		assert (resultQubit.isValid() == true);
	}

    @Override
	public void measure() {
		MeasurementPerformer measurementPerformer = new MeasurementPerformer().configure(resultQubit);
		resultQubit = measurementPerformer.measure();
	}

运行 Grover 算法 100 万次后，得到下图

我们可以观察到，在 100 万次运行中，大约有 350000 次获得了正确答案 |111>。

关注点

我发现使用我实现的量子计算库来模拟著名的量子算法很有趣。这样我可以向其中添加更多功能，还可以发现一些小错误。此外，我认为这是理解量子算法的好方法。

参考文献

量子算法导论，Emma Strubell，2011 年春季

量子比特、量子力学和计算机, Umesh V. Vazirani, 2005 年春季

历史

添加了文章
添加了 GPL3 许可