Usually Simon's algorithm is defined for function $f: \{0,1\}^n \mapsto \{0,1\}^n$. Can Simon's algorithm still be applied to function of the form $f: \{0,1\}^n \mapsto \{0,1\}^m$, where $n > m$? My understanding is that as long as we have an oracle of the form $O_f: |x\rangle \otimes |y\rangle \rightarrow |x\rangle |y \oplus f(x) \rangle$, where $x,y$ are $n$-qubit registers, Simon's algorithm should work in the exact same way as it does for functions of the form $f: \{0,1\}^n \mapsto \{0,1\}^n$. Is that correct?


1 Answer 1


Remember that $f$ must satisfy Simon's promise: $$\forall (x,y),f(x)=f(y)\implies \begin{cases}y\\s\oplus y\end{cases}$$ Thus there are two cases:

  1. Either $s=0$, in which case $f$ is injective
  2. Or $s\neq 0$, in which case $f$ is "2-to-1."

Now, let us assume that $n>m$. It is easy to see that it is not possible to have $s=0$, since by the pigeonhole's principle two $x_i$ will necessarily be mapped to the same $y$.

The same applies to the case $s\neq0$. Without loss of generality, let $s$ be equal to $1||0^{n-1}$. In this case, we have to choose a different $y$ depending on the last $n-1$ bits of the input. As such, at least $2^{n-1}$ different values are required to satisfy Simon's promise.

Thus, though $n=m+1$ works if $s\neq0$ holds, it is not possible to find a function satisfying Simon's promise for $n>m+1$. Now, the quantum and classical routines in Simon's algorithm works independently of $m$, so as long as $n\leqslant m+1$, it is possible to use Simon's algorithm.

Now, as you mentioned in the comments, Kaplan et al. showed that if the promise is approximately fulfilled, Simon's algorithm can still be applied.

More precisely, they define the following quantity: $$\varepsilon(f,s)=\max_{t\in\{0;1\}^n\setminus\{0;s\}}\mathbb{P}[f(x)=f(x\oplus t)]$$ and state the following theorem:

Theorem 1 (Simon’s algorithm with approximate promise). If $\varepsilon(f,s)\leqslant p_0<1$, then Simons' algorithm returns $s$ with $cn$ queries, with probability at least $1-\left[2\left(\frac{1+p_0}{2}\right)^c\right]^n$.

Thus, if you are able to bound $\varepsilon(f,s)$, then you are able to run Simon's algorithm to retrieve $s$. However, they use a function from $\{0;1\}^n$ to itself. To understand whether that matters, we need to take a deeper look to their proof. Going through it, you can realize that no step in their proof actually uses the size of the output register. Thus, not only is Simon's algorithm usable if $m < n$, but the bounds from Theorem 1 are also independent of it. Putting things differently, Theorem 1 can be used as is without caring about what $m$ is. If you want to look in details at theur proof and to whether it is truly independent of $m$, please have a look a the following and tell me in the comments if there's something you don't understand.

They first prove the following Lemma:

For $t\in\{0;1\}^n$, consider the function $g(x)=\frac{1}{2^n}\sum\limits_{y\in t^\perp}(-1)^{x\cdot y}$. For any $x$, it satisfies: $$g(x)=\frac12\left(\delta_{x,0}+\delta_{x,t}\right).$$

This lemma generic and does not consider $m$ at all. Now to the proof.

They first argue that by construction, since for all $x$, $f(x)=f(x\oplus s)$ holds, the vector $u_i$ obtained from the quantum routine is orthogonal to $s$. This wasn't trivial for me but but wwe can work out the computation pretty easily. Because of the aforementioned property, after the first measurement the state collapses to: $$\sum_i\left(\left|x_i\right\rangle+\left|x_i\oplus s\right\rangle\right)$$ Applying the Hadamard gate to it yields: $$\sum_y\left[\sum_i(-1)^{x_i\cdot y}\left[1+(-1)^{y\cdot s}\right]\right]|y\rangle$$ Thus, any $y$ that's being measured must be orthogonal to $s$. Note that this fact is independent of $m$.

Thus, you're left with $cn$ vectors $u_1,\cdots,u_{cn}$ that are all orthogonal to $s$. The classical routine recovers $s$ successfully if these vectors span the sub-vector space $s^\perp$, which dimension is $n-1$, since $s$ is an $n$-bit string.

They thus compute the probability for the algorithm to fail to be: $$p_{\text{fail}}\leqslant\max_{t\in\{0;1\}^n\setminus\{0;s\}}\left(2\mathbb{P}\left[u_1\cdot t=0\right]^c\right)^n$$ Note that this computation only considers the $u_i$ and uses their indepedance. Thus, this result does not depend on $m$.

Thus, if we can show that $\mathbb{P}\left[u_1\cdot t=0\right]^c$ is bounded away from $1$ independently of $m$, then we would have achieved our goal.

So, let us follow through their proof. Let $t$ be an arbitrary $n$-bit string. The state before the measurements is: $$\begin{align}&\frac{1}{2^n}\sum_{x\in\{0;1\}^n}\sum_{y\in\{0;1\}^n}(-1)^{x\cdot y}|y\rangle|f(x)\rangle\\=&\frac{1}{2^n}\sum_{\substack{y\in\{0;1\}^n\\y\cdot t=0}}\sum_{x\in\{0;1\}^n}(-1)^{x\cdot y}|y\rangle|f(x)\rangle+\frac{1}{2^n}\sum_{\substack{y\in\{0;1\}^n\\y\cdot t=1}}\sum_{x\in\{0;1\}^n}(-1)^{x\cdot y}|y\rangle|f(x)\rangle\end{align}$$ Thus, the probability of measuring $y$ such that $y\cdot t=0$ is given by: $$\begin{align}\mathbb{P}[y\cdot t = 0]&=\left\|\frac{1}{2^n}\sum_{\substack{y\in\{0;1\}^n\\y\cdot t=0}}\sum_{x\in\{0;1\}^n}(-1)^{x\cdot y}|y\rangle|f(x)\rangle\right\|^2\\&=\frac{1}{2^{2n}}\sum_{\substack{y\in\{0;1\}^n\\y\cdot t=0}}\sum_{x,x'\in\{0;1\}^n}(-1)^{\left(x\oplus x'\right)\cdot y}\left\langle f(x)\middle|f\left(x'\right)\right\rangle\\&=\frac{1}{2^{n}}\sum_{x,x'\in\{0;1\}^n}\left\langle f(x)\middle|f\left(x'\right)\right\rangle\underbrace{\frac{1}{2^n}\sum_{\substack{y\in\{0;1\}^n\\y\cdot t=0}}(-1)^{\left(x\oplus x'\right)\cdot y}}_{g\left(x\oplus x'\right)}\\&=\frac{1}{2^{n+1}}\sum_{x,x'\in\{0;1\}^n}\left\langle f(x)\middle|f\left(x'\right)\right\rangle\left(\delta_{x,x'}+\delta_{x',x\oplus t}\right)\\&=\frac{1}{2^{n+1}}\sum_{x\in\{0;1\}^n}1+\frac{1}{2^{n+1}}\sum_{x\in\{0;1\}^n}\langle f(x\oplus t)|f(x)\rangle\\&=\frac12+\frac12\mathbb{P}[f(x)=f(x\oplus t)]\end{align}$$ Note that nowhere in these computation have we used $m$.

  • 1
    $\begingroup$ Thank you! I am ware of works that show that Simon's algorithm still works if Simon's promise is fulfilled only approximately, i.e., if there are other collisions in $f$ as well. See for example here, Theorem 1. So, since the routines in Simon's algorithm work independently of $m$, it should probably be possible to transfer these results to the case that $n \neq m$, yes? $\endgroup$ Mar 8, 2022 at 20:06
  • $\begingroup$ @cryptobeginner I was about to edit my answer because I only thought about this article some times after having posted my answer, I'm editing it! $\endgroup$
    – Tristan Nemoz
    Mar 8, 2022 at 23:38

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.