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)?


1 Answer 1


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$.

  • $\begingroup$ 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 $\endgroup$
    – aghin
    Commented Feb 25 at 14:37
  • $\begingroup$ 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$ $\endgroup$
    – xzkxyz
    Commented Feb 25 at 16:48
  • $\begingroup$ 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? $\endgroup$
    – aghin
    Commented Feb 25 at 17:41
  • $\begingroup$ 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. $\endgroup$
    – xzkxyz
    Commented Feb 27 at 20:21

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.