Worked example of Bernstein-Vazirani - understanding bitwise product

Question

From chapter 3.3 or the Qiskit Textbook, I'm trying to follow the worked example of the quantum solution for Bernstein-Vazirani.

I'm having trouble with what I think should be a trivial bit of classical computation - specifically, the bitwise product $s\cdot x$

In the problem description, the black-box function takes the form: $$f(x)=s \cdot x \mod2$$ Given the example and separate videos, I think what this is doing is a logical AND between every bit in the string $s$ and the input $x$, then calculating $\mod2$ of the result to populate the single output. This would make sense as it would mean the classical solution would require you to run the function with each input bit set in turn to determine the value of $s$.

Where I'm struggling is the subsequent worked example, where we have the string $s=11$ and the quantum oracle output is being defined as:$$|\upsilon _{2} \rangle=\frac{1}{2}((-1)^{00\cdot11}|00\rangle+(-1)^{01\cdot11}|01\rangle+(-1)^{10\cdot11}|10\rangle+(-1)^{11\cdot11}|11\rangle)$$ I'm fine with, this, but then it simplifies to:$$|\upsilon_2\rangle=\frac{1}{2}(|00\rangle-|01|\rangle-|10\rangle+|11\rangle)$$ My problem with this is the signs preceding each state. As $|01\rangle$ and $|10\rangle$ are negative and the rest are positive, that means that the exponents $(00\cdot11)$ and $(11\cdot11)$ are even values (or 0), while $(01\cdot11)$ and $(10\cdot11)$ are odd.

I can't see any way that this happens. If I apply the logical AND described above, I get: $$00\cdot11=00=0$$ $$01\cdot11=01=1$$ $$\color{red}{10\cdot11=10=2}$$ $$\color{red}{11\cdot11=11=3}$$ These last two would give me the wrong signs. I've also tried multiplication of the equivalent decimal values, but that doesn't work either. What's the correct mechanism for calculating $nn\cdot nn$ in this equation?

Answer 1

Usually, when you have two bitstrings $i$ and $j$ of size $n$, the product $i.j$ corresponds to $i.j = \sum\limits_{k = 1}^{n}i_kj_k$, so here you have the following results :

\begin{align*} & 00.11 = 0\times 1 + 0\times1 = 0 \\ & 01.11 = 0\times 1 + 1\times1 = 1 \\ & 10.11 = 1\times 1 + 0\times1 = 1 \\ & 11.11 = 1\times 1 + 1\times1 = 2 = 0 \mod 2 \end{align*}

Answer 2

I would add that function $f(x) = s \cdot x \mod 2$ for $s$ and $x$ being $n$ bit strings can be rewriten as $$ f(x) = x_1 \times s_1 \oplus x_2 \times s_2 \oplus \dots \oplus x_n \times s_n, $$

where $\times$ is logical AND between two bits $x_i$ and $s_i$ and $\oplus$ is XOR function.

So, for $s = 11$ we have:

• $11 \cdot 00 = 1 \times 0 \oplus 1 \times 0 = 0 \oplus 0 = 0$
• $11 \cdot 01 = 1 \times 0 \oplus 1 \times 1 = 0 \oplus 1 = 1$
• $11 \cdot 10 = 1 \times 1 \oplus 1 \times 0 = 1 \oplus 0 = 1$
• $11 \cdot 11 = 1 \times 1 \oplus 1 \times 1 = 1 \oplus 1 = 0$