Bernstein-Vazirani算法

B-V算法

(1) 问题描述

  给定布尔函数f:{0,1}n→0,1f:{\left\{ {0,1} \right\}^n} \to{0,1}f:{0,1}n→0,1, 函数$f$的值是由输入比特串$x$和确定的比特串$s$做模2意义下的内积：$$f\left(x\right)=x\cdot s\left(\mathrm{mod}2\right),$$其中$$x\cdot s=\sum _i\left(x_i\oplus s_i\right)$$
前提：可以调用访问函数$f$的黑盒
问题：计算出比特串$s$

经典意义下：
  依次输入比特串$x$:
$$\begin{array}{l}\mathrm{00...00}\\ \mathrm{00...01}\\ \mathrm{00...10}\\ ...\\ \mathrm{01...00}\\ \mathrm{10...00}\end{array}$$
对于第$i$次输入：
$$\mathrm{000100...00}\to x\cdot s\left(\mathrm{mod}2\right)=s_i$$
重复该流程$n$次，即可确定比特串$s$，上述方法的查询复杂度为$O\left(n\right)$

(2) 量子算法核心思路：

基础知识：$H^{\otimes n}|s⟩=\frac{1}{2^{\frac{n}{2}}}{\sum }_x(-1{)}^{s\cdot x}|x⟩$

Step1：制备初始量子比特$$|{\Phi }_0⟩={|0⟩}^{\otimes n}$$
Step2：作用$H^{\otimes n}$，得到量子态$$|{\Phi }_0⟩=\frac{1}{2^{\frac{n}{2}}}\sum _x|x⟩$$
Step3：作用量子黑盒$O_f$，$O_f:|x⟩\to {\left(-1\right)}^{x\cdot s}|x⟩$，此时系统状态为$$|{\Phi }_1⟩=\frac{1}{2^{\frac{n}{2}}}\sum _x{\left(-1\right)}^{s\cdot x}|x⟩$$
Step4：作用$H^{\otimes n}$，系统状态变为$|s⟩$
此时测量量子系统即可得到比特串$s$，该算法的查询复杂为$O(1)$

备注：上述量子黑盒$O_f$的实现方法与Deutsh算法相似，具体方法如下

(1) 制备量子态$|{\Psi }_0⟩={|0⟩}^n|1⟩$
(2) 作用$H^{\otimes n}$，量子系统变为$|{\Psi }_1⟩=\frac{1}{2^{\frac{n}{2}}}\sum _x|x⟩|-⟩$
(3) 作用$U_f：|x⟩|y⟩\to |x⟩|y\oplus f\left(x\right)⟩$，量子系统演变为$$|{\Psi }_2⟩=\frac{1}{2^{\frac{n}{2}}}\sum _x|x⟩\frac{1}{2^{\frac{1}{2}}}\left(|0\oplus f\left(x\right)⟩-|1\oplus f\left(x\right)⟩\right)$$
当$f\left(x\right)=0$时，$$|x⟩\frac{1}{2^{\frac{1}{2}}}\left(|0\oplus f\left(x\right)⟩-|1\oplus f\left(x\right)⟩\right)=|x⟩\frac{1}{2^{\frac{1}{2}}}\left(|0⟩-|1⟩\right)=|x⟩|-⟩$$
当$f\left(x\right)=1$时，$$|x⟩\frac{1}{2^{\frac{1}{2}}}\left(|0\oplus f\left(x\right)⟩-|1\oplus f\left(x\right)⟩\right)=|x⟩\frac{1}{2^{\frac{1}{2}}}\left(|0⟩-|1⟩\right)=-|x⟩|-⟩$$
不难发现$U_f$的作用为：$$|x⟩|-⟩\to {\left(-1\right)}^{f\left(x\right)}|x⟩|-⟩={\left(-1\right)}^{s\cdot x}|x⟩|-⟩$$
舍弃掉最后一个量子比特（辅助比特）$|-⟩$，即实现了Step3中的黑盒$O_f$

参考资料
[1] Bernstein-Vazirani Algorithm 学习笔记
[2] 量子计算【算法篇】第7章 Deutsch-Josza算法及实现
(3) 由 Fourier Sampling 到 Deutsch-Jozsa Algorithm & Bernstein-Vazirani Algorithm