algorithm - Deutsch 算法的推广

Question

此问题涉及针对具有多于一位作为输入的函数所讨论的 Deutsch 问题的直接概括。这一次，我们有一个 bool 函数 f，它以 4 位数字作为输入并输出 0 或 1，即 f:{0,1}4→{0,1}。因此，f 的输入是 16 个可能的 4 位二进制数之一:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

我们还被告知 f 是以下两种类型之一:

either f is a constant function, i.e., f(x) is the same for all 16 possible values of the input x, or
f is a balanced function, i.e., f(x) is 0 for exactly 8 of the possible 16 inputs and f(x) is 1 for the remaining 8 of the possible 16 inputs.

我们被允许做的是通过将输入 x 提供给 f 的电路并观察输出 f(x)，将 f 的电路用作“黑匣子”。这称为“查询”操作。

表明经典概率算法可以通过使用 2 个查询以至少 2/3 的概率确定 f 是平衡的还是常数。

提示:(显然，我们不能使用确定性算法来做到这一点。除非确定性算法看到至少 9 个输入值的输出，否则它无法确定函数是否是平衡的或恒定的)。

考虑从 16 个可能的输入集合中均匀随机地挑选两个输入。您的最终结果可能在概率上取决于这两个查询的结果。

Answer 1

编辑:我错误地计算了一些概率。我现在还提到，我们需要为函数 f 随机选择 2 个不同的输入，以保证如果 f 是平衡的，那么我们知道看到各种可能结果的概率。

函数为常量的先验概率未知这一事实使这个问题变得更加困难，因为这意味着我们无法直接计算任何算法的成功概率。但是，我们将能够计算出此概率的界限。

我提出以下概率算法:

• 随机选择两个不同的 4 位值，并将每个值提供给函数 f。
• 如果看到 0,0 或 1,1，则以 2/3 的概率输出“常数”，以 1/3 的概率输出“平衡”。
• 否则(如果看到 0,1 或 1,0)，始终报告“平衡”。

让我们从实际可以计算的东西开始:条件概率。

1. “什么是 P(correct|constant)，即给定 f 是常数，我们的算法给出正确答案的概率？” 当 f 是常数时，我们的算法报告正确答案 2/3 次。
2. “什么是 P(correct|balanced)，即我们的算法在给定 f 平衡的情况下给出正确答案的概率？” 当 f 平衡时，看到 0,1 或1,0就是2*(8/16 * 8/15) = 8/15，这样肯定会输出正确答案。在剩下的 7/15 的情况下——即看到 0,0 或 1,1 的情况——正确答案将在 1/3 的时间内输出，因此正确输出的总比例为 8/15 * 1 + 7/15 * 1/3 = 31/45 = 2/3 + 1/45 ≈ 0.6889。

现在假设函数为常量的先验概率为 p。那么算法给出正确答案的概率就是

pCorrect(p) = p*P(correct|constant) + (1-p)*P(correct|balanced)。

鉴于 0 <= p <= 1，pCorrect(p) 必须至少为 min(P(correct|constant), P(correct|balanced))，至多为 max(P(correct|constant), P(正确|平衡))。 2/3 和 31/45 中的最小值是 2/3，因此 pCorrect 从下方开始以 2/3 为界，对于函数为常数的任何先验概率。(可能有助于思考p 作为“混合杠杆”，控制每个项包含多少。如果 p = 0 或 p = 1，那么我们实际上分别只有 P(正确|平衡)或 P(正确|恒定)，并且对于任何p 的中间值，我们将有一个中间总数。)