[Solved]: Simple explanation of Simon's Problem

Problem Detail: 

I just read the Wiki article for Simon's Problem but I don't fully understand it because I don't follow the symbolic notation used to describe functions (I am not a computer scientist).

Can someone just briefly explain it in simple language, like is it just XOR'ing two binary strings and trying to isolate each string? Also, if this problem is known to take exponential time to solve, why isn't it being used as a cryptographic primitive?

Asked By : William Hird

Answered By : Logan Mayfield

I think there are really three issues buried in your question.

1. What's Simon's Problem?
2. What's a plain english description of the function involved in Simon's Problem?
3. Why isn't this problem a cryptographic primitive?

I can't really speak to 3 as cryptography is not my area. I can take a crack at 1 and 2 for you though. The distinction between 1 and 2 is, I think, important.

Simon's problem is one of discovering the parameter to a function given a black-box to that function and some basic information about the function. So, an algorithm to solve this problem takes as its input a black-box to a function and gives a output a binary string. Our goal is to reduce the number of queries to that black box. I think people tend to miss this point and focus on the internals of the function itself.

All we know about the function $f$ is that our black-box can compute it for us in constant, $O(1)$, time, and that if $f(x) = f(y)$, then either $x=y$ or $x \oplus y = s$. We want to know the value of $s$. A brute force, classical computing solution might give you a better feel for the problem. Here it is:

1. Feed all $n$ bit binary strings to the black-box and save each input-output pair to a table.
2. If no two inputs produce the same output then it must be the case that the parameter $s$ is $n$ bit $0$. Otherwise, two inputs will produce the same output and $s$ is the result of XOR'ing those inputs together.

In the worst case, we have to query all $2^n$ inputs leading to $O(2^n)$ query complexity.

Querying the black-box is at the heart of Simon's problem. We need not concern ourselves with how to construct the black-box, i.e. how to compute $f$, as that is not what the problem is about. I don't believe that Simon's problem is practically useful beyond the fact that it helps establish some complexity results about Quantum Computers. It's main significance is that it was an inspiration for Peter Shor's factoring algorithm.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19519