实践|Bernstein-Vazirani算法及实践

点击上方↑↑↑“量子发烧友”关注我

Bernstein-Vazirani算法及实践

本文将主要介绍Bernstein-Vazirani算法的基本概念、Bernstein-Vazirani问题以及该问提的经典与量子解决方式。本文对Bernstein-Vazirani算法的实现将主要使用启科量子的配套产品量子编程框架QuTrunk、可视化量子编程软件QuBranch以及启科量子自研的量子后端设备QuBox。

1.Bernstein-Vazirani算法

Bernstein-Vazirani算法是由Ethan Bernstein和Umesh Vazirani于1992年提出的一个算法。该算法主要用于求解编码函数，是一个条件限制版的Deutsch-Jozsa算法。也就是说Bernstein-Vazirani的工作建立在Deutsch和Jozsa早期工作理论上来探索量子查询复杂度。他们对该领域的贡献主要为编写出一个用于隐藏字符串问题的量子算法。已经有人证明了Bernstein-Vazirani算法时间复杂度在BQP和BPP之间，该算法的非递归量子查询复杂度仅为11。这一量子算法的最核心价值在于加快了查询速度, 而不是执行时间本身。

那么何为BQP复杂度和BPP复杂度？在计算复杂性理论中，BQP（bounded-error quantum polynomial time）是量子计算机在多项式时间内可以解决的一类决策问题，所有实例的错误概率最多为1/3。BPP这个每个字母分别代表"Bounded-error"(有限错误)，"Probabilistic"(机率的)，"Polynomial time"(多项式时间)。BPP是在多项式时间内以概率图灵机解出问题的集合, 并且对所有的输入、输出结果出错的概率在1/3之内。当一个问题属于BPP问题集合时，则存在一个多项式时间内的算法允许随机决定，且对于该算法的任何输入都必须在错误率为1/3的概率下给出正确判断。

2.Bernstein-Vazirani问题

假设一个函数f(x)满足₀₁₂，以x作为输入，并返回结果0或1。现在给定一个输入x，函数，其中，最终预计会找到s。因此，Bernstein-Vazirani算法目标为求解s。

2.1经典方式求解

采用经典方式求解Bernstein-Vazirani问题，所列表达式为。给定一个输入x，隐藏位串 s 可以按输入序列使用算子oracle查找。如输入x为100…0,010…0,001…0,000…1，经典算法求解方式只能查询生成1位信息，任意隐藏字符串s具有n位信息，所以经典查询的复杂度为O(n)。

示例：当n=2时的Bernstein-Vazirani问题。经典设元素为两位，s向量表示为，所代表函数为4种类（00，01，10，11）。此时的Bernstein-Vazirani问题为，S可对应01、10两种取值，复杂度O（2）。

2.2量子方式求解

关于Bernstein-Vazirani问题的经典算法中Oracle构造可以表示如下图：

而经典算法中Oracle构造可以表示为如下图：

构造步骤：

• 首先初始化输入的量子比特，得到输出量子比特；
• 对每个量子比特进行H门操作；
• 应用设计出的量子Oracle算子 找到搜索目标；
• 经过量子Oracle门操作后，再次进行H门操作得到态。根据。对于任意量子比特得到经过以上步骤量子门操作后的输出态表达式为。

整个Bernstein-Vazirani算法过程可表示为：

3.Bernstein-Vazirani算法的实现

3.1Bernstein-Vazirani算法——以QuTrunk为例

• 步骤一：QuTrunk环境准备

    from qutrunk.circuit import QCircuit
    from qutrunk.circuit.gates import CNOT, X

以上调用qutrunk.circuit实现量子线路功能，qutrunk.circuit.gates实现量子逻辑门使用。

• 步骤二：设置量子比特数、量子线路后端、量子寄存器等

    num_qubits = 9
    secret_num = 2 ** 4 + 1
    circuit = QCircuit(resource=True)

    qureg = circuit.allocate(num_qubits)

• 步骤三：按QuTrunk的量子汇编语言输入量子线路

    X * qureg[0]

    bits = secret_num
    bit = 0
    for qb in range(1, num_qubits):
        bit = int(bits % 2)
        bits = int(bits / 2)
        if bit:
            CNOT * (qureg[0], qureg[qb])

    success_prob = 1.0
    bits = secret_num
    for qb in range(1, num_qubits):
        bit = int(bits % 2)
        bits = int(bits / 2)
        success_prob *= circuit.get_prob_outcome(qb, bit)

• 步骤四：运行Bernstein-Vazirani算法并打印结果

    print(f"solution reached with probability {success_prob}")
    circuit.print()

    circuit.run()
    circuit.show_resource()

输出统计信息如下，包括了所用量子比特数、量子逻辑门、算法运行时间、后端设备运行时间等，具体如下：

 *solution reached with probability 1.0  
qreg q[9]  
creg c[9]  
X * q[0]  
MCX(1) * (q[0], q[1])  
MCX(1) * (q[0], q[5])  
==================Counter==================  
Counter(quit=9)  
qubits = 9  
quantum_gates = 3  
total_time = 0.0024347305297851562  
qutrunk_time = 0.0009989738464355469  
backend_time = 0.0014357566833496094*

参考资料：

[1]https://qiskit.org/textbook/ch-algorithms/bernstein-vazirani.html#3a.-Experiment-with-Simulators--

[2]https://baike.baidu.com/item/BQP/22700880?fr=aladdin

[3]Ethan Bernstein and Umesh Vazirani (1997) "Quantum Complexity Theory" SIAM Journal on Computing, Vol. 26, No. 5: 1411-1473, doi:10.1137/S0097539796300921.

— 完 —