13、量子算法：从 Deutsch 算法到 Deutsch–Jozsa 算法

量子算法：从 Deutsch 算法到 Deutsch–Jozsa 算法

1. 量子算法概述

算法的开发往往先于其运行的机器。经典算法的出现比经典计算机早了数千年，同样，在大规模量子计算机问世之前，就已经存在了几种量子算法。这些量子算法通过操纵量子比特来解决问题，通常比经典计算机更高效。

量子算法的基本框架如下：
- 系统从特定的经典量子比特状态开始。
- 将系统置于多个状态的叠加态。
- 对这个叠加态进行多个幺正操作。
- 最后对量子比特进行测量。

2. Deutsch 算法

Deutsch 算法是最简单的量子算法，它解决了一个稍显人为设定的问题，该问题涉及从集合 {0, 1} 到集合 {0, 1} 的函数。这类函数共有四个，可分为两类：
- 平衡函数：如果 f(0) ≠ f(1)，即函数是一一对应的，则称函数 f 为平衡函数。
- 常量函数：如果 f(0) = f(1)，则称函数 f 为常量函数。在这四个函数中，有两个是平衡函数，两个是常量函数。

Deutsch 算法要解决的问题是：给定一个从 {0, 1} 到 {0, 1} 的函数 f 作为黑盒，只能对输入进行求值，不能“查看”函数的定义，判断该函数是平衡函数还是常量函数。

2.1 经典计算机的解决方案

使用经典计算机，需要先对一个输入计算 f 的值，再对第二个输入计算 f 的值，最后比较输出。决策树如下：

graph TD; A[开始] --> B{f(0) = 0}; B