在4對1函數上具有高概率的量子算法

Question

讓$ f：$ {0,1} $^n \ rightarrow $ {0,1} $^n $是一個4對1函數，例如存在 不同和非零

$ a，b \ in $ {0,1} $^n $這樣對於所有$ x \ in $ {0,1} $^n $： $ f（x）= f（x⊕a）= f（x⊕b）= f（x⊕a⊕b）$。注意⊕是一個按位xor，對於所有$ y \ notin $ {$ x，x⊕a，x⊕b，x⊕a⊕b$}，$ f（y）\ neqf（x ）$。查找 一個高概率報告集合{a，b，a⊕b}的量子算法。

Answer 1

那麼，選擇x爲0給出f(0) = f(a) = f(b) = f(a xor b)。沒有其他輸入匹配f(0)。所以我們只是尋找v滿足v != 0, f(v) = f(0)。因此，製作一個電路，需要一個v並在滿足其他條件時不進行任何操作。然後應用grover的算法。運行時間將是O(sqrt(N))找到第一個值。然後你再重複一遍，也是一樣。

另一方面，只是隨機抽樣直到發現碰撞還有預計的時間O(sqrt(N))，所以可能會有更聰明的做法。