the oracle

• 搜索空间: $N$N 元素

• 只关心$[0,N-1]$[0,N−1]的索引，不关注元素本身

• 假设$N=2^n$N=2n，这样索引用$n-bits$n−bits存储

• 有$M$M个解
  

• 假如我们有一个 a quantum oracle， with the ability to recognize solutions to the search problem.

  • The oracle is a unitary operator, $O$O, defined by its action on the computational basis:
  • $\left|x\right>\left|q\right>\stackrel{O}{\longrightarrow}\left|x\right>\left|q\oplus f(x)\right>$∣x⟩∣q⟩⟶O​∣x⟩∣q⊕f(x)⟩
  • $\left|x\right>:$∣x⟩:index register
  • $f(x)=1$f(x)=1的话oracle qubit $q$q就翻转
  • 如果一开始oracle qubit 是$\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}$2​∣0⟩−∣1⟩​,那么末态就是：
  • $\left| x \right>\left|\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\right>\stackrel{O}{\longrightarrow}(-1)^{f(x)}\left|x\right>\left|\frac{\left|0\right>-\left|1\right>}{\sqrt{2}}\right>$∣x⟩∣∣∣​2​∣0⟩−∣1⟩​⟩⟶O​(−1)f(x)∣x⟩∣∣∣​2​∣0⟩−∣1⟩​⟩
  • 看到 oracle qubit总是没有改变，所以这个oracle可以这样干
    • 其实俺是有疑惑的
  • $\left| x \right>\stackrel{O}{\longrightarrow}(-1)^{f(x)}\left|x\right>$∣x⟩⟶O​(−1)f(x)∣x⟩
    • 这个oracle的作用是将解的相位移动了
      

Deutsch-Jozsa算法

• 场景：
  • alice 从$0到2^n-1$0到2n−1间选择了一个数$x$x，发给了Bob计算$f(x)(constant\quad or \quad balanced)$f(x)(constantorbalanced)，然后回复1或0.
• 目标：
  • Alice 将判定Bob使用哪个函数呢？并且通信要尽可能少哦！！
• 经典的要： $2^n/2+1$2n/2+1次查询
• 量子：1个查询，使用$U_f$Uf​去计算$f(x)$f(x)
• 下面的图就是通信过程：

  • 上面左是alice，下面左是oracle

  • $\left|\psi_0\right>=\left|0\right>^{\otimes n}\left|1\right>$∣ψ0​⟩=∣0⟩⊗n∣1⟩

  • $\left|\psi_1\right>=\left|+\right>^{\otimes n}\left|-\right>=$∣ψ1​⟩=∣+⟩⊗n∣−⟩=

    • $\frac{1}{\sqrt{2^n}}\sum\limits_{x=0}^{2^n-1}\left|x\right>\frac{1}{\sqrt{2}}(\left|0\right>-\left|1\right>)$2n​1​x=0∑2n−1​∣x⟩2​1​(∣0⟩−∣1⟩)

  • $\left|\psi_2\right>=\frac{1}{\sqrt{2^n}}\sum\limits_{x=0}^{2^n-1}(-1)^{f(x)}\left|x\right>\frac{1}{\sqrt{2}}(\left|0\right>-\left|1\right>)$∣ψ2​⟩=2n​1​x=0∑2n−1​(−1)f(x)∣x⟩2​1​(∣0⟩−∣1⟩)

    • 当$H^{\otimes n}$H⊗n作用在前面一大撮东西上面会变成啥呢？

    • $\left|x\right>=\left|x_1,x_2,...,x_n\right>$∣x⟩=∣x1​,x2​,...,xn​⟩

    • 看每个$H$H作用后成了啥？成了$\left|0\right>+(-1)^{x_1}\left|1\right>=$∣0⟩+(−1)x1​∣1⟩=
      $\sum\limits_{z=0}^{z=1}(-1)^{zx_1}\left|z\right>$z=0∑z=1​(−1)zx1​∣z⟩

    • 所以$x$x作用的话就成了 $\sum\limits_{z=0}^{2^n-1}(-1)^{zx}\left|z\right>$z=0∑2n−1​(−1)zx∣z⟩

    • 作用在一大群$x$x上就是$\frac{1}{\sqrt{2^n}}\sum\limits_{z=0}^{2^n-1}\sum\limits_{x=0}^{2^n-1}(-1)^{f(x)+xz}\left|z\right>$2n​1​z=0∑2n−1​x=0∑2n−1​(−1)f(x)+xz∣z⟩

  • $\left|\psi_3\right>=\frac{1}{\sqrt{2^n}}\sum\limits_{z=0}^{2^n-1}\sum\limits_{x=0}^{2^n-1}(-1)^{f(x)+xz}\left|z\right>\frac{1}{\sqrt{2}}(\left|0\right>-\left|1\right>)$∣ψ3​⟩=2n​1​z=0∑2n−1​x=0∑2n−1​(−1)f(x)+xz∣z⟩2​1​(∣0⟩−∣1⟩)

  • 我们只需要测量$“z=0”$“z=0”的系数，便可知道啦！！
    
    
    

the procedure

• 搜索算法就像下面这样运行

• The oracle may employ work qubits for its implementation,
  but the analysis of the quantum search algorithm involves
  only the n-qubit register.

• Goal: to find a solution to the search problem, using the
  smallest possible number of the applications of the oracle.
  

• The quantum search algorithm consists of repeated application
  known as the Grover iteration or Grover operator, which we
  denote G. And it may be broken up into four steps:

  • Apply the oracle $O$O.

  • Apply the Hadamard transform $H^{\otimes n}$H⊗n.

  • Perform a conditional phase shift with every computational
    basis state except |0⟩ receiving a phase shift of −1,

    • $\left|x\right⟩ \rightarrow−(−1)^{δ_x}\left|x\right⟩$∣x⟩→−(−1)δx​∣x⟩
    • Show that the unitary operator corresponding to the phase shift in the G is $2|0⟩⟨0| − I$2∣0⟩⟨0∣−I.
    • 显然$2|0⟩⟨0| − I$2∣0⟩⟨0∣−I作用在$|0⟩$∣0⟩上是不变，其他你可以验证啊，

  • Apply the Hadamard transform $H^{\otimes n}$H⊗n.

• Each of the operations in the G may be efficiently implemented
  on a quantum computer.

  • $G=H^{\otimes n}(2|0⟩⟨0| − I)H^{\otimes n}O$G=H⊗n(2∣0⟩⟨0∣−I)H⊗nO
    • 又看到了经常看到的东西了
      

geometric visualization

• $G$G 可以被视为 a rotation in the two-dim space spanned by the starting vector |ψ⟩ and the superposition.
• 来个定义哦
  • 假设有$M$M个是解， 令$\left|\alpha\right>=\frac{1}{\sqrt{N-M}}\sum_x^{''}\left|x\right>$∣α⟩=N−M​1​∑x′′​∣x⟩
  • 令$\left|\beta\right>=\frac{1}{\sqrt{M}}\sum_x^{'}\left|x\right>$∣β⟩=M​1​∑x′​∣x⟩
  • 记得$\left|\psi\right>=\frac{1}{\sqrt{N}}\sum\limits_{x=0}^{N-1}\left|x\right>=\sqrt{\frac{N-M}{N}}\left|\alpha\right>+\sqrt{\frac{M}{N}}\left|\beta\right>$∣ψ⟩=N​1​x=0∑N−1​∣x⟩=NN−M​​∣α⟩+NM​​∣β⟩
  • 从下面的图容易看出来，$\cos\frac{\theta}{2}=\sqrt{\frac{N-M}{N}}$cos2θ​=NN−M​​
  • 我们来看看$G$G对$\left|\psi\right>$∣ψ⟩的作用
    • 先看$O$O的作用，$\left|\psi\right>\stackrel{O}{\longrightarrow}=\sqrt{\frac{N-M}{N}}\left|\alpha\right>-\sqrt{\frac{M}{N}}\left|\beta\right>$∣ψ⟩⟶O​=NN−M​​∣α⟩−NM​​∣β⟩
      • 看出来是关于$\alpha 粥$α粥对称
    • $2\left|\psi\right>\left<\psi\right|-I$2∣ψ⟩⟨ψ∣−I是数学上的啥？
      • 初等反射阵啊！
        
        
        

例子

• Here is an explicit example illustrating how the quantum search
  algorithm works on a search space of size $N = 4$N=4.
• The oracle can be taken to be one of the four circuits:
  • 第一个图： 只有输入都是11的时候才会触发，其他类似

• The whole circuit is as follows.
• where the gates in the box perform $2|00⟩⟨00| − I$2∣00⟩⟨00∣−I.
  • 这意味着$\left|\psi\right>$∣ψ⟩