1

这个问题涉及对多于一位作为输入的函数所讨论的 Deutsch 问题的直接概括。这一次，我们有一个布尔函数 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.

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

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

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

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

4

2 回答 2

0

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

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

我提出以下概率算法：

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

让我们先看看我们可以实际计算的东西：条件概率。

  1. “什么是 P（正确|常数），即假设 f 是常数，我们的算法给出正确答案的概率？” 当 f 为常数时，我们的算法在 2/3 的时间内报告正确答案。
  2. “什么是 P（正确|平衡），即假设 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(正确|常数) + (1-p)*P(正确|平衡)。

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

于 2012-12-08T06:41:20.297 回答
-1

查看不同类型的函数返回两个给定值的不同结果的概率：

constant  0,0  50%
constant  1,1  50%
balanced  0,0  4/8 * 3/7 = 21,4%
balanced  0,1  4/8 * 4/7 = 28.6%
balanced  1,0  4/8 * 4/7 = 28.6%
balanced  1,1  4/8 * 3/7 = 21.4%

如果结果为 0,0 或 1,1，则函数有 70% 的机会保持不变，而对于结果 0,1 和 1,0，则函数有 100% 的机会平衡。因此，对于发生率为 71.4% 的情况，我们有 70% 的把握，而发生在 28.6% 的时间的情况，我们是 100% 确定的。平均而言，我们有 78.6% 的把握。

于 2012-12-08T05:06:09.283 回答