undefined

Problem 3: Running Simon's problem (30 points) (a) For this question, we will be dealing with Simon's problem for n=5. Assume that, after 4 runs of the algorithm, the measurements we got from the input register were y(1) = (1,1,1,1,0), y(2) = (1,0,0,1,0), y() = (1,0,1,1,1), and y() = (1,1,0,1,1). Can we determine the hidden period a at this point? If so, what is a? If not, explain. (b) What if we run the algorithm one more time and get y(5) (0,1,0,0,0), Can we determine a now? If so, what is a? If not, explain. (c) Run Simon's algorithm for a two-to-one function f : {0,1} + {0,1}?, with hidden period a = (1,1,0). Problem 3: Running Simon's problem (30 points) (a) For this question, we will be dealing with Simon's problem for n=5. Assume that, after 4 runs of the algorithm, the measurements we got from the input register were y(1) = (1,1,1,1,0), y(2) = (1,0,0,1,0), y() = (1,0,1,1,1), and y() = (1,1,0,1,1). Can we determine the hidden period a at this point? If so, what is a? If not, explain. (b) What if we run the algorithm one more time and get y(5) (0,1,0,0,0), Can we determine a now? If so, what is a? If not, explain. (c) Run Simon's algorithm for a two-to-one function f : {0,1} + {0,1}?, with hidden period a = (1,1,0)