Deutsch-Jozsa 算法 简述-deutsche bank sperrkonto
Deutsch-Jozsa 算法 是最早展现指数加速的传统量子算法之一。虽然它所解决的问题构造性太强，算法缺乏实用性，但由于其步骤简单，故经常被当作“toy algorithm”用来引出后续一系列的传统量子算法。
本文 reformulate 其步骤和证明。
Deutsch-Jozsa 算法
问题描述：
已知函数 f:{0,1}⊗n→{0,1}f:\{0,1\}^{\otimes n}\rightarrow\{0,1\} 一定是下列两种极端形式的一种
1. "constant"
f(x)=0,∀xorf(x)=1,∀xf(x)=0,\forall x~~\text{or}~~f(x)=1,\forall x
2. "balanced"
f(x)=0for half of {0,1}⊗n,andf(x)=0~~\text{for half of }\{0,1\}^{\otimes n},~\text{and}
f(x)=1for the other halff(x)=1~~\text{for the other half}
问如何用最少的查询次数确定 ff 属于二者中的哪一种。
注：显然，对于最坏的情况，经典算法至少要查询 2n−1+12^{n-1}+1 次。输入：
black box oracle Uf|x⟩|y⟩=|x⟩|y⊕f(x)⟩U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle
注：此处记录 |x⟩|x\rangle 的 qubits 称作 query register，作用一次 UfU_f 称为一次“quantum query”。输出：
ff is constant or balanced.
步骤陈述：
1. 在初态 |0⟩⊗n|1⟩|0\rangle^{\otimes n}|1\rangle 上作用 H⊗(n+1)H^{\otimes (n+1)} 得到 |+⟩⊗n|−⟩|+\rangle^{\otimes n}|-\rangle ；
2. 作用一次 oracle UfU_f ；
3. 在 query rigister 上作用 H⊗nH^{\otimes n} 并测量，若得到 |0⟩⊗n|0\rangle^{\otimes n} 则说明 ff 是 constant，否则为 balanced。
线路：
证明：
由于 f(x)∈{0,1}f(x)\in\{0,1\} 且
Uf|x⟩|y⟩=|x⟩|y⊕f(x)⟩U_f|x\rangle|y\rangle=|x\rangle|y\oplus f(x)\rangle
故对于 |−⟩=(|0⟩−|1⟩)/2|-\rangle=(|0\rangle-|1\rangle)/\sqrt{2} 有
Uf|x⟩|−⟩=(−1)f(x)|x⟩|−⟩U_f|x\rangle|-\rangle=(-1)^{f(x)}|x\rangle|-\rangle
从而
Uf|+⟩⊗n|−⟩=∑x(−1)f(x)|x⟩2n|−⟩U_f|+\rangle^{\otimes n}|-\rangle=\sum_x\frac{(-1)^{f(x)}|x\rangle}{\sqrt{2^n}}|-\rangle
另外，由于 single-qubit Hadamard gate 的作用可紧凑地表示为
H|x⟩=12∑z(−1)xz|z⟩H|x\rangle=\frac{1}{\sqrt{2}}\sum_z(-1)^{xz}|z\rangle
故 multi-qubit case 可表示为
H⊗n|x⟩=12n∑z(−1)x⋅z|z⟩H^{\otimes n}|x\rangle=\frac{1}{\sqrt{2^n}}\sum_z(-1)^{x\cdot z}|z\rangle
从而
H⊗n(∑x(−1)f(x)|x⟩2n)=12n∑x,z(−1)x⋅z+f(x)|z⟩≡|out⟩H^{\otimes n}\left(\sum_x\frac{(-1)^{f(x)}|x\rangle}{\sqrt{2^n}}\right) =\frac{1}{2^n}\sum_{x,z}(-1)^{x\cdot z+f(x)}|z\rangle\equiv|\text{out}\rangle
输出态中 |0⟩⊗n|0\rangle^{\otimes n} 对应分量为
⟨0⊗n|out⟩=12n∑x(−1)f(x)\langle 0^{\otimes n}|\text{out}\rangle= \frac{1}{2^n}\sum_{x}(-1)^{f(x)}
显然，
当 ff 为 constant 时， ⟨0⊗n|out⟩=±1\langle 0^{\otimes n}|\text{out}\rangle=\pm 1 ， |out⟩=±|0⟩⊗n|\text{out}\rangle=\pm|0\rangle^{\otimes n} ；
当 ff 为 balanced 时， ⟨0⊗n|out⟩=0\langle 0^{\otimes n}|\text{out}\rangle=0 。
因此，若测量结果出现 |0⟩⊗n|0\rangle^{\otimes n} 则ff 一定为 constant ，否则一定为 balanced。 ◼\blacksquare
Comments：
1. Deutsch 算法一般指以上算法的 2-qubit 版本。
2. 该算法简洁地体现了传统量子算法利用“parallelism + interference”提取 全局信息 的思想。即，虽然碍于测量坍缩的限制，无法直接提取量子并行的所有结果，但通过巧妙地设计一些变换，我们可以将藏在量子态中的全局信息转换到直积态上加以测量，而这些全局信息通常是经典算法难以快速获取的。
3. 值得指出，若放宽确定性的限制，则经典算法同样可以快速地以高概率得出问题的解（失误概率指数衰减 ϵ≤1/2k\epsilon\leq 1/2^k ）。另外 ff 和 UfU_f 的查询次数也并不能直接拿来作比较。尽管如此，Deutsch-Jozsa 算法还是由于包含了传统量子算法的基本思想而广为人知。
题外话：算法提出者 David Deutsch 的姓氏和“德意志”的拼写一样，另外作为上海话谐音就是“同济”。
