Simon's problem for linear functions

Abstract

Simon's problem asks the following: determine if a function $f:\{0,1{\}}^n\to \{0,1{\}}^n$ is one-to-one or if there exists a unique $s\in \{0,1{\}}^n$ such that $f(x)=f(x\oplus s)$ for all $x\in \{0,1{\}}^n$, given the promise that exactly one of the two holds. A classical algorithm that can solve this problem for every $f$ requires $2^{\Omega (n)}$ queries to $f$. Simon showed that there is a quantum algorithm that can solve this promise problem for every $f$ using only $\mathcal{O}(n)$ quantum queries to $f$. A matching lower bound on the number of quantum queries was given by Koiran et al., even for functions $f:{\mathbb{F}}_p^n\to {\mathbb{F}}_p^n$. We give a short proof that $\mathcal{O}(n)$ quantum queries is optimal even when we are additionally promised that $f$ is linear. This is somewhat surprising because for linear functions there even exists a classical $n$-query algorithm.

7 pages