4
$\begingroup$

We look at the following variant of Simon's problem.

There is an algorithm $A$ that solves a problem with the following settings:

The input is an oracle $f:\{0,1\}^n \to [M]$.

The output of the algorithm: if there exists $s \in \{0,1\}^n$ such that for every $x,y \in \{0,1\}^n$ it satisfies that $f(x)=f(y) \iff x=y \oplus s$, then output the first bit of $s$, otherwise output $1$.

Namely, there is no promise about the function $f$ itself, but the algorithm $A$ can determine if it's a 1-to-1 or 2-to-1 function that sends every $x, \text{and } x \oplus s$ to the same value for some $s \in \{0,1\}$.

For example, if $f$ is 2-to-1 but there is no value $s$ such that for every $x,y$ it satisfies $f(x)=f(y) \iff x=y \oplus s$, then the algorithm can determine this and will return $1$ as its output.

The task is to show that there is no quantum algorithm for this problem, which is of polynomial size.

Seemingly, the only difference between this version of Simon's problem and the original version, it that in the original version its promised that such an $s$ exists (which makes $f$ a 2-to-1 function).

Here such a promise isn't present.

I'm not sure how to tackle this problem, but it seems to me that the way is to assume by that such an algorithm exists, which solves this problem in $p(n)$ times, and then use this algorithm in a quantum search algorithm and gain an exponential acceleration for a problem which would end in a contradiction.

Not exactly sure how to formulate it though. Help would be appreciated.

Improve this question
$\endgroup$
13
  • $\begingroup$ To clarify, Simon is $x\oplus y=s$ but here $x=y\oplus s$, right? $\endgroup$
    – Mark Spinelli
    Commented Mar 31 at 12:53
  • $\begingroup$ Isn't it that essentially the same? if $x \oplus y = s$ then applying XOR on both sides with $y$ results in $x = y \oplus s$ $\endgroup$
    – Gabi G
    Commented Mar 31 at 20:18
  • $\begingroup$ So what would happen if $s=0^N$? I’m not clear why this is different from Simon? $\endgroup$
    – Mark Spinelli
    Commented Apr 1 at 0:20
  • 1
    $\begingroup$ If $s$ has its first bit 1, how do you distinguish it from the case when $s$ doesn't exist? Also, you should be more precise in defining the problem statement. Simons problem specifically states that for all x and y there exists s. Not just for some x or y. $\endgroup$
    – MonteNero
    Commented Apr 6 at 23:48
  • 2
    $\begingroup$ It seems like a reduction from element distinctness should be possible. Not an answer, just a suggestion... $\endgroup$
    – John Watrous
    Commented Apr 10 at 13:07

2 Answers 2

Reset to default
1
$\begingroup$

Consider the set of values taken by $f$; that is, consider the range of $f$. For any arbitrary function $f$, this range can be partitioned as follows:

  1. There could be a first set of images $A$ that have precisely one preimage; that is, for each $y\in A$, there is only one $x$ such that $y=f(x)$.

  2. There may be a second set of images $B$ that have more than two preimages; that is, for each $y\in B$, there are more than two $x_i$ such that $y=f(x_1)=f(x_2)=f(x_3)\ldots$

  3. There is a third set of images $C$ that have precisely two preimages; that is, for each $y\in C$, there are only two distinct preimages $x_1$ and $x_2$ such that $y=f(x_1)=f(x_2)$.

This third set $C$ can be further partitioned based on the XOR of these preimages. Every element of $C$ is in one and only one sub-partition of $C$ based on $s=x_1\oplus x_2$. These sub-partitions of $C$ can be indexed by $s$.

It appears that given that $|C|\ge 2$, the problem is equivalent to deciding whether $C$ is further partitioned into one (and only one) component by all values in the range of $f$ with two preimages sharing a common XOR $s$, or alternatively whether $C$ is partitioned into more than one component each having different $s$.

I claim (with a lot of handwaving) that this reduces to, e.g., element distinctness, which at best can be solved only in time $\Theta(N^{2/3})$. For, from the element distinctness optimality, we can't easily distinguish whether even $|B|=|C|=0$ (and $f$ is injective) from $|B|=0$ and $|C|=1$ (and there is precisely $y$ having two preimages, while all other $y$ have only a single preimage.) Because, the first case indicates that $f(x)$ is distinct for all $x$ while the second case indicates that there is one non-distinct element repeated twice in the output of $f$.

Of course, we can always Hadamard the input register and measure to get a string $d$ that is orthogonal to the XOR of the output register (orthogonal to $s$), but this won't help in counting the number of partitions of $C$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm not sure that I understood completely the reduction here. For the case $|B|=|C|=0$ the algorithm $A$ will return $0$ (since in this case $s=0$), for the case $|B|=0$ and $|C|=1$ the algorithm will return $1$, and using it we can solve element distinctness on $Im(f)$? $\endgroup$
    – Gabi G
    Commented Apr 13 at 20:42
  • $\begingroup$ If $|B|=0$ and $|C|=0$ then there are no images with precisely two preimages; if $|B|=0$ and $|C|=1$ then there is precisely one image with precisely two preimages. The first case shows that $f$ maps all preimages to distinct images; the second case shows that $f$ maps two preimages to the same image. $\endgroup$
    – Mark Spinelli
    Commented Apr 13 at 22:22
-1
$\begingroup$

Assume You have a function $f(x) := \begin{cases} 1 & \text{if } x = \widehat{x} \\ 0 & \text{else}\end{cases} $ for an arbitrary value $\widehat{x}$. We also have a function $F:\{0,1\}^n\to [M]$ and an algorithm $A$ which decides: \begin{align*} A(F) = \begin{cases} s_1 & \text{if } \exists s: F(x)=F(y) \iff x=y\oplus s \\ 1 & \text{else}.\end{cases} \end{align*} We use the algorithm $A$ to find $\widehat{x}$ in polynomial time.

  1. Check if $f(0)\neq 1$, otherwise $\widehat{x}$ is found.
  2. def $\overline{f}(x)=\begin{cases} 1 & \text{if } x = 0^n \\ 0 & \text{else}.\end{cases}$
  3. Def. $F=f+\overline{f}$. Now $F$ fulfils the requirement of $A$ of having a period of exactly $\widehat{x}$. Therefore, $A$ returns $s_1$.
  4. Finally some sort of reduction should be made to skip the first bit of $s$ so that the next call of $A$ returns us $s_2$.
  5. Repeat $n$ times to get the whole string $s$ and therefore the $\widehat{x}$
Improve this answer
$\endgroup$
6
  • $\begingroup$ What do you mean by $f(x)$? There’s no $x=\bar x$. $\endgroup$
    – Mark Spinelli
    Commented Apr 11 at 11:09
  • $\begingroup$ You want to create a reduction from Grover's search to this altered Simon. $f$ is the function that Grover's search becomes as a task, and You build an algorithm that parses the input into something that is understood by the algorithm $A$. That's why You build the function $F$ $\endgroup$
    – Sezzart
    Commented Apr 11 at 12:12
  • $\begingroup$ Ok, but there is no Boolean string equal to its own inverse. $\endgroup$
    – Mark Spinelli
    Commented Apr 11 at 12:32
  • $\begingroup$ $\overline{x}$ is not the inverse, its just some specific fixed string. maybe the notation is not perfect $\endgroup$
    – Sezzart
    Commented Apr 11 at 12:37
  • 1
    $\begingroup$ I am not sure that running $A$ on $F$ will return $s_1$. Because I find an $x,y$ such that $x,y \ne 0^n, \widehat{x}$ and I will have $F(x)=F(y)$, but $x \ne y \oplus \widehat{x}$. So $\widehat{x}$ doesn't separate $F$ to a $2-to-1$ function. $\endgroup$
    – Gabi G
    Commented Apr 12 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.