对于单比特的布尔函数，其接受一个二元输入，并输出一个二元结果，有：
x \in \{0, 1\}, \quad f(x) \in \{0, 1\}此时根据自变量取值，可能出现四种情况：
| 情况 A | 情况 B | 情况 C | 情况 D | |
| f(0) | 0 | 0 | 1 | 1 |
| f(1) | 0 | 1 | 0 | 1 |
若希望判断函数 ( f(x) ) 属于上述四种情形中的哪一类，考虑到单比特仅有 0 与 1 两种状态，因此无法直接区分全部四种情况。然而，可以基于单比特的测量结果将它们分为两组，从而得到以下三种可能的分组方式：
- A 和 B 组合为一组；C 和 D 组合为另一组。
- A 和 C 组合为一组；B 和 D 组合为另一组。
- A 和 D 组合为一组；B 和 C 组合为另一组。
因此，共有三种可能的均匀分组（即 0 和 1 出现概率相同）方式。
可以看出，对于组合 (1)，判断 f(0) 的值即可区分其所属分组；对于组合 (2)，判断 f(1) 的值即可实现同样目的。但在组合 (3) 的情形下，经典计算机无法通过一次函数调用（一次实验）同时获得足以用于确定分组的信息，因此无法在单次操作中确定函数的分组。
这里引入 Deutsch 算法，证明对于该问题，量子计算机能够在一次实验即确定组合 (3) 的分组，由此首次证明了量子计算机在特定问题中确实能比经典计算机更快地给出答案。
观察组合 (3)，不难发现情况 A 和 D 中 f(0) 和 f(1) 具有固定输出（0 或 1），因此称其为恒常函数（Constant）；而 B 和 C 中的输出根据输入而改变，称为平衡函数（Balanced）。
| 函数类型 | 描述 | 形式 |
| 恒常函数 | 输出与输入无关 | f(x) = 0 或 f(x) = 1 |
| 平衡函数 | 输出与输入有关 | f(x) = x 或 f(x) = 1 – x |
为求解该问题，我们需构建谕示机（Oracle），其对恒常函数和平衡函数应有不同的二进制输出。不难发现，四种情况有：
| 函数形式 | f(0) | f(1) |
| f(x) = 0 | 0 | 0 |
| f(x) = 1 | 1 | 1 |
| f(x) = x | 0 | 1 |
| f(x) = 1 – x | 1 | 0 |
即，恒常函数与平衡函数其 f(0) + f(1) 具有不同的奇偶性：
\begin{cases}
(f(0) + f(1)) \bmod 2 = 0, & \text{if } f \text{ is constant}\\[2pt]
(f(0) + f(1)) \bmod 2 = 1, & \text{if } f \text{ is balanced}
\end{cases}上式的模 2 加法与异或（⊕）具有相同的解：
| 函数形式 | f(0) + f(1) | (f(0) + f(1)) ⊕ 0 |
| f(x) = 0 | 0 | 0 |
| f(x) = 1 | 2 | 0 |
| f(x) = x | 1 | 1 |
| f(x) = 1 – x | 1 | 1 |
进一步，其亦与 CNOT 门具有相同的解：
| q0 | q1 | CX(q0, q1) |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
即，可以构建谕示函数 CX(f(0)+f(1), 0) 从而判定函数形式：
CX\,\ket{f(0)+f(1)}\ket{0}=\begin{cases}
\ket{f(0)+f(1)}\ket0, & \text{if } f \text{ is constant}\\[2pt]
\ket{f(0)+f(1)}\ket1, & \text{if } f \text{ is balanced}
\end{cases}因此，实现电路有：
CX\,U_{f(q_0)} \ket{+} \ket{0} = \begin{cases}
\ket+\ket0, & \text{if } f \text{ is constant}\\[2pt]
\ket+\ket1, & \text{if } f \text{ is balanced}
\end{cases}进一步的，为了保留辅助比特 |0> 的状态，这里可以基于辅助比特状态实现相位踢回（kickback）至 q0，考虑到：
CX\,U_{f(q_0)} \ket{+} \ket{1} = \begin{cases}
\ket+\ket1, & \text{if } f \text{ is constant}\\[2pt]
\ket+\ket0, & \text{if } f \text{ is balanced}
\end{cases}因此，构建：
\begin{aligned}
CX\,U_{f(q_0)}\ket{+}\ket{-}
&= \frac{1}{2}\,CX\,U_{f(q_0)} \ket{+}(\ket{0}-\ket{1}) \\[2pt]
&= \frac{1}{2}\,\Big( CX\,U_{f(q_0)}\ket{+}\ket{0} - CX\,U_{f(q_0)}\ket{+}\ket{1} \Big) \\[2pt]
&=
\begin{cases}
\ket{+}\ket{0} - \ket{+}\ket{1} = \ket{+}\ket{-}, & \text{if } f \text{ is constant}\\[2pt]
\ket{+}\ket{1} - \ket{+}\ket{0} = -\ket{+}\ket{-}, & \text{if } f \text{ is balanced}
\end{cases}
\end{aligned}即，此时，通过测定 q0 的相位，即可判定函数类型：
H\,CX\,U_{f(q_0)}\ket{+}\ket{-} =\begin{cases}
\ket{0}\ket{-}, & \text{if } f \text{ is constant}\\[2pt]
\ket{1}\ket{-}, & \text{if } f \text{ is balanced}
\end{cases}至此，基于量子计算机仅需一次输入即可判定原函数为恒常函数亦或平衡函数。
发表回复