a quantum algorithm with high probability on a 4 to 1 function

81 Views Asked by At

Let $f : $ {0,1}$^n \rightarrow $ {0,1}$^n$ be a 4-to-1 function, such that there exist distinct and non-zero

$a,b\in $ {0,1}$^n$ such that for all $x\in$ {0,1}$^n$: $f(x) = f(x ⊕ a) = f(x ⊕ b) = f(x ⊕ a ⊕ b)$ . Note that ⊕ is a bit-wise xor, and that for all $y \notin ${$x,x ⊕ a, x ⊕ b, x ⊕ a ⊕ b$}, $f(y) \neq f(x)$. Find a quantum algorithm that with high probability reports the set {a,b, a ⊕ b}.

really stuck here guys, any guidance would come along way!