I am stuck on the following question.

Let $S$ be the $span${s1, s2, ... , sk} such that $S$ is a $k$-dimensional subspace of {0, 1}n. Let 𝑓:{0,1}𝑛→{0,1}𝑛 be a function so that $f(x) = f(y)$ if and only if $x-y$$S$. Prove there is an algorithm that learns $S$ with $O(n)$ quantum queries to $f$.

It seems like this is just like Simon's problem, except with multiple s instead of just one. The problem I'm having is solving it in $O(n)$. Wouldn't we have to run Simon's algorithm $k$ times since there are $k$ entries in $S$? In other words, there are $k$ number of s strings we have to find, right? Where am I going wrong?


1 Answer 1


Your intuition is right that you want to run Simon's algorithm. But you only need to run it once. Let me give you the main steps of the argument (leaving some details for you to fill in).

In the standard version of Simon's algorithm, you've got one hidden binary string $s$. Each possible outcome $z$ of your measurement has a term in its amplitude of $1+(-1)^{z\cdot s}$. If you perform the same calculation for your new function, I believe you'll get an equivalent factor of the form $$ \prod_{i=1}^k(1+(-1)^{z\cdot s_i}). $$ Hence, the only outcomes $z$ which you'll get satisfy $z\cdot s_i$ for all $i$. You repeat this a few times to build up several $z$s. However, the size of the space that you're trying to build up information about is $2^{n-k}$ instead of $2^{n-1}$, so it should take you fewer attempts to find spanning basis elements.


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.