Bernstein-Vazirani 算法

Bernstein-Vazirani 算法简介

Bernstein-Vazirani算法由Bernstein Ethan与Vazirani Umesh在1993年提出。该算法求解的问题描述如下:给定一个函数

\[f_s:\{0,1\}^n\rightarrow \{0,1\}: f_s(x)=s\cdot x, x,s\in\{0,1\}^n.\]

这里 \(s\) 是一个未知比特串,且

\[s\cdot x=(\sum_{i=1}^n s_ix_i) mod~2,\]

其中, \(x_i​\)\(s_i​\) 分别为 \(x​\)\(s​\) 的第 \(i​\) 个比特。 我们的目标是求解比特串 \(s​\)。 该问题的经典算法的查询复杂度可以表述为要求解 \(f_s​\) 至少需要查询 \(\Omega(n)​\) 个黑箱, 而Bernstein-Vazirani 算法仅仅需要查询 \(O(1)​\) 个黑箱。

Bernstein-Vazirani 算法在HiQ上的实现

import math

from projectq.ops import H, Z, X, Measure, All, CNOT
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_BV_algorithm(eng, n, oracle):
   """
   利用给定的量子oracle运行Bernstein-Vazirani算法.

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

   返回:
     solution (list<int>): s所对应的比特串.
   """

    x = eng.allocate_qureg(n)

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

    oracle_out = eng.allocate_qubit()
    X | oracle_out
    H | oracle_out

    oracle(eng, x, oracle_out)

    All(H) | x

    All(Measure) | x
    Measure | oracle_out

    eng.flush()

    return [int(qubit) for qubit in x]

def BV_oracle(eng, qubits, output):
    """
    这是线形函数 f(x)=a \cdot x 的oracle, 其中 a=(1,0,0,0,...).
    这个oracle标价所有 f(x)=1 的基.

    Args:
        eng (MainEngine): 算法运行的主引擎.
        qubits (Qureg): Bernstein-Vazirani算法的输入n比特.
        output (Qubit): 能够被解所对应的比特串控制翻转的输出比特.
    """
    CNOT | (qubits[0], output)

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)

    n = 10 # number of qubits

    print("===========================================================")
    print("= This is the Bernstein-Vazirani algorithm demo")
    print("= you can change the unknown string by modifying the oracle")

    s = run_BV_algorithm(eng, n, BV_oracle)
    s_str = "".join([str(ch) for ch in s])
    print("= Length of the bit string: {}".format(n))
    print("= The unknown bit string is: {}".format(s_str))
    print("===========================================================")