Recursive Bernstein-Vazirani algorithm

Recently I've found the recursive Bernstein-Vazirani algorithm which is explained quite good in this paper CSE 599d - Quantum Computing The Recursive and Nonrecursive Bernstein-Vazirani Algorithm of Dave Bacon.

However, I still don't understand some points of the algorithm. In the paper it is stated that instead of trying to find some $$s$$ such that given a function $$f$$, we have $$f(x) = x\cdot s \;\text{mod}\;2$$ (this is the non-recursive B-V algorithm), we are interested to find some function $$g:\{0,1\}^{n} \longrightarrow \{0,1\}$$ on $$s$$, that is $$g(s)$$.

It is also stated that the oracle is now two $$n$$ strings, called respectively $$x \in \{0,1\}^n$$ and $$y \in \{0,1\}^n$$, so the function that must be queried first takes the input and then outputs $$s_x \cdot y$$, i.e. the function is $$f:\{0,1\}^n \times \{0,1\}^n \longrightarrow \{0,1\}$$ and is given by $$f(x,y) = s_x \cdot y$$.

The following part is where my doubts arise. When asking what exactly is $$s_x$$, Bacon says that the $$s_x$$ are "$$2^n$$ different bit strings, labeleed by $$x \in \{0,1\}^n$$, with the property that when computing $$g(s_x)$$ we require that these $$2^n$$ bits satisfy $$g(s_x) = x\cdot s$$ for some unknown $$s$$; thus the problem is to identify $$g(s)$$". (A)

But still, I don't understand the role of the different $$s_x$$ strings. Lastly, the paper states that when we are at the last point of the recursion, e.g. suppose we have the $$k=2$$ level problem, that is when we have $$g(s_{x1}) = s\cdot x_1$$, we finally get the hidden string $$s$$. (B)

So the question is: are we trying to find $$g(s)$$ (as in A), or the ultimate goal is still to find the hidden string $$s$$ (as in B)?

So the intuition here is that the function $$f$$ encodes a tiny amount of information: a single $$n$$ bit string. Extracting this information is quantumly easy, but also classically easy. In order to make the problem harder, we might consider a strategy to encode much more information within a function. However, we can't just increase the size of the string, since we can't exactly query a $$2^n$$-bit string in polynomial time. We want to drastically increase the amount of information encoded in a clever way, without enlarging the queries by too much.

To make the problem of harder, we compose it with itself. The idea is instead of directly giving query access to a function $$f_s(x) = x \cdot s$$, we hide the function $$f_s$$ behind yet another secret string. We promise that $$f_s = x \cdot s = g(s_x)$$ for some secret string $$s_x$$. Here we are in the first level.

The ultimate goal is still to compute $$s$$. In order to compute $$g(s)$$ for any possible choice of $$g$$, you would need to know $$s$$. You can assume that $$g(s)$$ is a simple function to compute, but is tricky enough that you can't instantly guess the secret strings from any nice properties of $$g$$. In an extremely crude analogy, you can think of $$g$$ as a very lousy hash.

In order to compute $$s$$, we need to make queries to the function $$f_s(x)$$. We no longer have oracle access to $$f_s(x)$$, but we can compute $$f_s(x)$$ if we can find the string $$s_x$$, then compute $$g(s_x)$$.

The new oracle takes two strings $$x, y$$ and produces $$s_x \cdot y$$. If we fix $$x$$, this is the same as the basic problem. We have a single secret string $$s_x$$, and a single query string $$y$$. We can find $$s_x$$ in $$n$$ classical queries. Once we find $$s_x$$, we can make one "query" to $$f_s(x) = s \cdot x = g(s_x)$$. This "query" of course is done by just calculating $$g(s_x)$$.

Here is an illustrative example: suppose we want to query the string $$10...0$$, in order to find the first bit of $$s$$. To do so, we need to find the secret string corresponding to $$10...0$$. We make queries of the form $$f(10...0, y)$$ in order find all the bits of $$s_x$$, then compute $$g(s_x)$$ to find one bit of $$s$$.

• So, what could be a problem of this type? In the non recursive B-V algorithm, we have a function f(x) that does something and we implement its oracle in order to find the hidden string s. What would be an example of a problem of the recursive version? Will we have a function g or f? Could you give a formal example? In the paper Bacon says that a function g of this type would have to be |x|mod3, but I can't understand how to formulate the example in order to create the oracles Feb 25 at 14:37
• You will need both $g$ and $f$. $g$ is known to the solver, so either we compute it ourselves or we have a second oracle for $g$. This is done so that $g$ does not show up in the runtime in any way. $f(x,y)$ defines the problem because it encodes the hidden strings, in the same way that $f_s(x)$ defines the non-recursive problem. Each unique $f(x, y)$ gives information about the strings $s, s_x$ through its output. In order to create an example of the problem, we: 1. choose a secret $s$, 2. choose string $s_x$ for every x, s.t. $g(s_x) = s \cdot x$, 3. define $f(x, y) = s_x \cdot y$ Feb 25 at 16:48
• Thank you for your answer, but that's not what i meant. What I want is to create an example from scratch; suppose I choose the string s=11 as the solutio: what function g and f do i define, just for the purpose of an example? To claryfi, the non recursive version could implement the function f(x1x2) = x1, given x1,x2 $\in \{0,1\}^n$; but what function can I create for the recursive version (both g and f), that's easy enough to demonstrate the algorithm? Feb 25 at 17:41
• Follow the previous comment. Lets choose $g(x) = |x| mod 3$ for the example. To define $f(x, y)$ compute all the bits $s \cdot x \forall x \in \{0, 1\}$. For each bit, choose a string $s_x$ such that $|s_x| mod 3 = s \cdot x$. From this list of $s_x$, you've defined $f(x, y)$. $f(x, y)$ is essentially defined by the mapping $x \to s_x$, and you are free to choose any list of strings $s_x$, so long as they meet the condition. Feb 27 at 20:21