Protocol: Alice Bob l）=2-1/2(I0)cl0)M +l1)c Eseaf(s)xs(y)IE(s))M) l) On 11)c: lIE(s)》M→Xs(x)lE1(s)》M y=2-1/2(10)clo)M +l1)c∑seAf(s)x,(z)lE1(s)》M) ly ↓Onl1)c:IE(s》M→lsM Ipy'=2-1/2(l0)cl0)w +l1)c Eseaf(s)xs(z)Is)M) Apply FT on M:Is)MN-1/2 Xs(t)lt)M y=(2N)-12(10)c Elt)M +l1)c∑：∑seAf(sxs(z+tlt)M) =(2W)-1/2(Io)c∑tlt)M+l1)c∑tf(z+tlt)M) =N-/r(tM v2 Apply Hadamard on C,then measure M A random t∈{0，1]n and the corresponding f(z+t)Protocol: Alice Bob |𝜓〉 = 2 −1/2 (|0〉𝐶 |0〉𝑀 +|1〉𝐶 ∑ 𝑓̂(𝑠)𝜒𝑠 (𝑦)|𝐸1 𝑠∈𝐴 (𝑠)〉𝑀) |𝜓〉 On |1〉𝐶: |𝐸1 (𝑠)〉𝑀 → 𝜒𝑠 (𝑥)|𝐸1 (𝑠)〉𝑀 |𝜓〉′ = 2 −1/2 (|0〉𝐶 |0〉𝑀 +|1〉𝐶 ∑ 𝑓̂(𝑠)𝜒𝑠 (𝑧)|𝐸1 𝑠∈𝐴 (𝑠)〉𝑀) |𝜓〉′ On |1〉𝐶: |𝐸1 (𝑠)〉𝑀 → |𝑠〉𝑀 |𝜓〉′ = 2 −1/2 (|0〉𝐶 |0〉𝑀 +|1〉𝐶 ∑ 𝑓̂(𝑠)𝜒𝑠 𝑠∈𝐴 (𝑧)|𝑠〉𝑀) Apply FT on M: |𝑠〉𝑀 → 𝑁−1/2 𝜒𝑠(𝑡)|𝑡〉𝑀 |𝜓〉′ = (2𝑁) −1/2 (|0〉𝐶 ∑𝑡 |𝑡〉𝑀 +|1〉𝐶 ∑ ∑ 𝑓̂(𝑠)𝜒𝑠 𝑡 𝑠∈𝐴 (𝑧 + 𝑡)|𝑡〉𝑀) = (2𝑁) −1/2 (|0〉𝐶 ∑𝑡 |𝑡〉𝑀 + |1〉𝐶 ∑𝑡 𝑓(𝑧 + 𝑡)|𝑡〉𝑀) = 𝑁−1/2 ∑ |0〉𝐶+𝑓(𝑧+𝑡)|1〉𝐶 √2 𝑡 |𝑡〉𝑀 Apply Hadamard on C, then measure M A random 𝑡 ∈ {0,1} 𝑛 and the corresponding 𝑓(𝑧 + 𝑡)