量子算法
Deutsch算法¶
算法目标¶
利用并行性，降低查询次数，以优化时间复杂度
判断一个函数是常数函数还是平衡函数
门电路分析
\[
H|0\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}
\]
\[
H|1\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}
\]
\[
U_f(|x\rangle\otimes|y\rangle)=|x\rangle\otimes(|y\oplus f(x)\rangle)
\]
两个量子比特¶
\[
|\psi_0\rangle=|0\rangle\otimes|1\rangle
\]
\[
|\psi_1\rangle=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\otimes \frac{|0\rangle-|1\rangle}{\sqrt{2}}
\]
\[
\,
\]
\[
当\,f(x)=0\,时\text{，}|y\oplus 0\rangle=\frac{|0\rangle-|1\rangle}{\sqrt{2}}
\]
\[
当\,f(x)=1\,时\text{，}|y\oplus 1\rangle=-\frac{|0\rangle-|1\rangle}{\sqrt{2}}
\]
\[
\Rightarrow \frac{|0\rangle-|1\rangle}{\sqrt{2}} \overset{U_f}\rightarrow (-1)^{f(x)}\frac{|0\rangle-|1\rangle}{\sqrt{2}}
\]
\[
\begin{align*}
|\psi_2\rangle&=\frac{|0\rangle+|1\rangle}{\sqrt{2}}\otimes (-1)^{f(x)}\frac{|0\rangle-|1\rangle}{\sqrt{2}}\\
&=\frac{((-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle)\otimes \frac{|0\rangle-|1\rangle}{\sqrt{2}}}{\sqrt{2}}
\end{align*}
\]
\[
现将\,|\psi_2\rangle\,中的第一个量子比特再经历一个Hadamard门转变为\,|\psi_3\rangle
\]
\[
(-1)^{f(0)}|0\rangle+(-1)^{f(1)}|1\rangle
\]
\[
\overset{hadamard}\rightarrow \frac{1}{\sqrt{2}}(-1)^{f(0)}(|0\rangle+|1\rangle)+\frac{1}{\sqrt{2}}(-1)^{f(1)}(|0\rangle-|1\rangle)
\]
\[
若\,f(0)=f(1)\text{，}得\,|0\rangle
\]
\[
若\,f(0)\neq f(1)\text{，}得\,|1\rangle
\]
Deutsch算法¶
门电路分析
单个Hadamard门
\[
\begin{align*}
H|x_i\rangle&=\frac{1}{\sqrt{2}}(|0\rangle+(-1)^{x_i}|1\rangle)\\
&=\frac{1}{\sqrt{2}}\sum_{y_i=0}^{1}(-1)^{x_iy_i}|y_i\rangle
\end{align*}
\]
推广到\(\,n\,\)hadamard门
\[
\prod_{i=0}^{n-1}[\frac{1}{\sqrt{2}}\sum_{y_i=0}^{1}(-1)^{x_iy_i}|y_i\rangle]
\]
\[
\begin{align*}
&=(\frac{1}{\sqrt{2}})^n\prod_{i=0}^{n-1}[\sum_{y_i=0}^{1}(-1)^{x_iy_i}|y_i\rangle]\\
&=(\frac{1}{\sqrt{2}})^n\sum_{y_{n-1}=0}^{1}\cdots\sum_{y_{0}=0}^{1}(-1)^{\sum_i x_iy_i}|y_{n-1}\cdots y_0\rangle\\
&=(\frac{1}{\sqrt{2}})^n\sum_{y=0}^{2^n-1}(-1)^{x\cdot y}|y\rangle\,\,其中\text{:}\,x\cdot y=\sum_i x_iy_i
\end{align*}
\]
n+1个量子比特¶
\[
\begin{align*}
|0\rangle^{\otimes n}|1\rangle &\overset{H^{\otimes n}\otimes H}\rightarrow \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}|x\rangle\otimes \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\\
&\overset{U_f}\rightarrow \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1}(-1)^{f(x)}|x\rangle\otimes\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)\\
&\overset{H^{\otimes n}\otimes I}\rightarrow \frac{1}{2^n}\sum_{x=0}^{2^n-1}\sum_{y=0}^{2^n-1}(-1)^{f(x)+x\cdot y}|y\rangle \otimes\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)
\end{align*}
\]
\[
测量上方\,n\,个量子比特在计算基矢上的情况\text{：}
\]
\[
当\,f(x)\,为常数时\text{，}100\%得到\,|00\cdots0\rangle
\]
\[
当\,f(x)\,为平衡时\text{，}不可能得到\,|00\cdots0\rangle
\]