Grover算法及其变形

Grover算法简介

Grover算法是一个非结构化的量子搜索算法,由Lov Grover于1996年提出 (https://arxiv.org/pdf/quant-ph/9605043.pdf)。这个算法是用于寻找能通过一个黑箱函数产生特定输出对应最大可能的唯一输入态。 该算法的时间复杂度为 \(O(\sqrt{N})\) 。 与经典算法的时间复杂度 \(O(N)\) 相比, Grover算法实现了计算的平方加速。 1997年,Bennett等人证明,对于非结构化的量子搜索问题,至少需要 \(\Omega(\sqrt{N})\) 次量子查询,因此Grover算法对于该问题是渐进意义下的最优算法 (https://arxiv.org/pdf/quant-ph/9701001.pdf)。

Grover算法的基本思路

Grover算法主要解决的问题:在 \(n\) 个量子比特的非结构化数据库中,有 \(N=2^n\) 个量子基态 \(|1\rangle,|2\rangle, \ldots, |N\rangle\),其中只有一个目标态 \(|\tau\rangle\) 是问题的解。 量子算法的目标是以大概率将目标态找到。Grover算法包括以下步骤:

  1. 数据库初始化。实施 \(n\) 量子比特上的Walsh-Hadamard操作 \(W=H^{\otimes n}\) 使得数据库被初始为一个平均叠加态

    \[|\psi_0\rangle=W|0\rangle=\sqrt{1/N}\sum_{i=1}^n|i\rangle.\]
  2. 进行Grover迭代 \(O(\sqrt{N})\) 次,然后以高概率得到目标量子态 \(|\tau\rangle\) 。Grover迭代包括四个子步骤:

    > 第一步,翻转目标态 \(|\tau\rangle\) 的相位,其他态保持不变,即施加操作

    \[I_{\tau}=I-2|\tau\rangle\langle \tau |.\]

    > 第二步, 进行 \(n\) 比特的Walsh-Hadamard变换, \(W=H^{\otimes n}\)

    > 第三步,翻转除初态 \(|0\rangle^{\otimes n}\) 以外所有基态的相位,这个作用可以表示为

    \[I_0=2|0\rangle^{\otimes n~n \otimes}\langle 0|-I.\]

    > 第四步, 进行 \(n\) 比特的Walsh-Hadamard变换 \(W=H^{\otimes n}\)

该算法的电路描述如下所示:

../images/Grovers_algorithm.png

Grover算法的HiQ实现 Grover算法的HiQ实现代码如下:

import math

from projectq import MainEngine
from projectq.ops import H, Z, X, Measure, All, Ph
from projectq.meta import Loop, Compute, Uncompute, Control


def run_grover(eng, n, oracle):
    """
    利用给定的量子oracle运行Grover's算法.

    参数:
        eng (MainEngine): 运行Grover算法的主引擎。
        n (int): 解所对应的比特数。
        oracle (function): 一个输入为engine, n比特寄存器,和能够被解所对应的比特串控制翻转的输出比特。

    返回:
        solution (list<int>): 解所对应的比特串.
    """
    x = eng.allocate_qureg(n)

    # 制备初始叠加态
    All(H) | x

    # Grover迭代的迭代次数:
    num_it = int(math.pi/4.*math.sqrt(1 << n))

    # 制备oracle的工作比特 1/sqrt(2) * (|0> - |1>),当输入比特是解时,可将工作比特翻转,从而得到一个相位为-1的标记
    oracle_out = eng.allocate_qubit()
    X | oracle_out
    H | oracle_out

    # 开始num_it次迭代
    with Loop(eng, num_it):
        # oracle给解所对应的基标记相位-1
        oracle(eng, x, oracle_out)

        # 关于初始叠加态反射
        with Compute(eng):
            All(H) | x
            All(X) | x

        with Control(eng, x[0:-1]):
            Z | x[-1]

        Uncompute(eng)

        All(Ph(math.pi/n)) | x

    All(Measure) | x
    Measure | oracle_out

    eng.flush()
    # 返回结果
    return [int(qubit) for qubit in x]


def alternating_bits_oracle(eng, qubits, output):
    """
    利用翻转标记解所对应的比特串1,0,1,0,...,0,1.

    参数:
        eng (MainEngine): 运行该算法的主引擎.
        qubits (Qureg): Grover算法运行的n量子比特的寄存器.
        output (Qubit): 能够被解所对应的比特串控制翻转的输出比特。
    """
    with Compute(eng):
        All(X) | qubits[1::2]
    with Control(eng, qubits):
        X | output
    Uncompute(eng)


if __name__ == "__main__":
    eng = MainEngine()  # use default compiler engine
    # 运行Grover算法,找到7比特的解
    n=int(input("Please input the number of qubits:"))
    print(run_grover(eng, n, alternating_bits_oracle))

精确Grover算法简介

原始的Grover算法只能以一定概率输出正确结果,特别是在一些特殊情况下输出错误结果的概率较大。 2001年,Long利用相位匹配的技巧将Grover算法的成功概率提高到1 (https://arxiv.org/pdf/quant-ph/0106071.pdf)。

原始的Grover迭代算子具有如下形式:

\[G=-H^{\otimes n}(I-2|0\rangle\langle 0|)H^{\otimes n}(I-2|\tau\rangle \langle \tau|),\]

其中 \(\tau\) 为该问题的解。精确Grover算法在原始的Grover算法的基础上,修改了Grover迭代算子,形式如下

\[G(\theta, \phi)=-H^{\otimes n}(I+(e^{i\theta}-1)|0\rangle\langle 0|)H^{\otimes n}(I+(e^{i\phi}-1)|\tau\rangle \langle \tau|).\]

这里, \(\theta\)\(\phi\) 满足相位匹配条件:

\[\cot ((2m+1)\beta)=e^{i\phi}\sin(2\beta)(-\cos(2\beta)+i\cot(\theta/2))^{-1},\]

其中 \(m=\pi 2^{n-2}\)\(\sin^2(\beta)=1/2^{n}\)

精确Grover算法的HiQ实现

import math

from projectq.ops import H, Z, X, Measure, All, Ph, Rz
from projectq.meta import Loop, Compute, Uncompute, Control

from projectq.cengines import (AutoReplacer,
                               LocalOptimizer,
                               TagRemover,
                               DecompositionRuleSet)

from hiq.projectq.cengines import GreedyScheduler, HiQMainEngine
from hiq.projectq.backends import SimulatorMPI

from mpi4py import MPI


def run_exactgrover(eng, n, oracle, oracle_modified):
"""
    利用给定的两种量子oracle运行精确Grover算法。
    该算法能以概率1输出解所对应的比特串。

    参数:
        eng (MainEngine): 运行Grover算法的主引擎.
        n (int): 解所对应的比特数.
        oracle (function): 一个输入为engine, n比特寄存器,和能够被解所对应的比特串控制翻转的输出比特.

    返回:
        solution (list<int>): 解所对应的比特串.
 """
    x = eng.allocate_qureg(n)

    # 制备初始叠加态
    All(H) | x

    # 精确Grover算法迭代次数
    num_it = int(math.pi/4.*math.sqrt(1 << n))

    # phi是modified oracle对应的参数
    # varphi是关于初始叠加态反射的参数
    theta=math.asin(math.sqrt(1/(1 << n)))
    phi=math.acos(-math.cos(2*theta)/(math.sin(2*theta)*math.tan((2*num_it+1)*theta)))
    varphi=math.atan(1/(math.sin(2*theta)*math.sin(phi)*math.tan((2*num_it+1)*theta)))*2

    # 制备oracle的输出比特 1/sqrt(2) * (|0> - |1>)
    oracle_out = eng.allocate_qubit()
    X | oracle_out
    H | oracle_out

    # 运行Grover迭代的迭代次数
    with Loop(eng, num_it):
        # oracle给解所对应的基添加相位-1
        oracle(eng, x, oracle_out)

        # 关于初始叠加态反射
        with Compute(eng):
            All(H) | x
            All(X) | x

        with Control(eng, x[0:-1]):
            Z | x[-1]

        Uncompute(eng)

    # 制备modified oracle的输出比特|1>
    H | oracle_out
    oracle_modified(eng, x, oracle_out, phi)

    with Compute(eng):
        All(H) | x
        All(X) | x

    with Control(eng, x[0:-1]):
        Rz(varphi) | x[-1]
        Ph(varphi/2) | x[-1]

    Uncompute(eng)

    All(Measure) | x
    Measure | oracle_out

    eng.flush()
    # 返回结果
    return [int(qubit) for qubit in x]


def alternating_bits_oracle(eng, qubits, output):
    """
    利用翻转标记解所对应的比特串1,0,1,0,...,0,1相位-1.

    参数:
        eng (MainEngine): 运行该算法的主引擎.
        qubits (Qureg): Grover算法运行的n量子比特的寄存器.
        output (Qubit): 能够被解所对应的比特串控制翻转的输出比特.
    """
    with Compute(eng):
        All(X) | qubits[1::2]
    with Control(eng, qubits):
        X | output
    Uncompute(eng)

def alternating_bits_oracle_modified(eng, qubits, output, phi):
   """
    利用翻转标记解所对应的比特串1,0,1,0,...,0,1相位phi.

    参数:
        eng (MainEngine): 运行该算法的主引擎.
        qubits (Qureg): Grover算法运行的n量子比特的寄存器.
        output (Qubit): 能够被解所对应的比特串控制翻转的输出比特.
        phi(parameter): 标记解的相位参数.
    """
    with Compute(eng):
        All(X) | qubits[1::2]
    with Control(eng, qubits):
        Rz(phi) | output
        Ph(phi/2) | output

    Uncompute(eng)

if __name__ == "__main__":

     # 使用模拟器后端创建一个主编译器引擎:
    backend = SimulatorMPI(gate_fusion=True)

    rule_set = DecompositionRuleSet(modules=[projectq.setups.decompositions])
    compilerengines = [AutoReplacer(rule_set)
                       , InstructionFilter(high_level_gates)
                       , TagRemover()
                       , LocalOptimizer(3)
                       , AutoReplacer(rule_set)
                       , TagRemover()
                       , LocalOptimizer(3)
                       , GreedyScheduler()
                       ]

    eng = HiQMainEngine(backend, engines)

    # 运行Grover搜索算法寻找一个n比特系统的解
    n=10
    print(run_exactgrover(eng, n, alternating_bits_oracle, alternating_bits_oracle_modified))

参考文献:

[1] Grover L K. A fast quantum mechanical algorithm for database search[C]// Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996: 212-219.
[2] Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation[J]. Contemporary Mathematics, 2002, 305: 53-74.