Deutsch算法的泛化

Question

這個問題涉及一個簡單的泛化的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（x），將f的電路用作「黑盒子」。這被稱爲「查詢」操作。

證明經典概率算法可以通過使用2個查詢來確定f是否平衡或常數至少爲2/3。

提示：（顯然，我們可以使用一個確定性算法除非確定算法看到了至少9個輸入值的輸出不會做，也沒有辦法爲它找到了該功能是否平衡或不變）。

考慮從16組可能的輸入中均勻地隨機選取兩個輸入。您的最終結果可能會依賴於這兩個查詢的結果。

Answer 1

編輯：我已經計算了一些錯誤的概率。另外我現在提到，我們需要爲函數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。然後，算法給出正確答案的概率是p正確（p）= p * P（正確）+（1-p）* P（正確|平衡）。

假設0 < = p< = 1，p正確性（p）必須至少爲最小值（P（正確），P（正確平衡））且至多最大（P（正確） ，P（正確|平衡））。 2/3和31/45的最小值爲2/3，因此，對於任何先前的函數恆定概率，pCorrect從2/3起限定。如果p = 0或p = 1，那麼我們實際上只有P（正確的|平衡的）或者P（正確的）。常數），對於p的任何中間值，我們將有一箇中間總數。）

Answer 2

看的概率爲不同類型的函數返回不同的結果對於兩個給定值：

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％的確定。