4
$\begingroup$

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?

$\endgroup$
1
  • 2
    $\begingroup$ Think of $s \cdot x$ as a dot product. Here $11$ means the vector \begin{pmatrix} 1 \\ 1 \end{pmatrix} and so $\begin{pmatrix} 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} 1 \\ 1 \end{pmatrix} = 1\cdot 1 + 1 \cdot 1$ and then $2 \mod 2 = 0$. $\endgroup$
    – KAJ226
    Mar 11 at 16:16
4
$\begingroup$

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*}

$\endgroup$
1
  • 1
    $\begingroup$ Thank you - I had searched for "bitwise multiplication" in case there was another approach (like this one) that I hadn't thought of, but didn't have much success. This now works. I appreciate this is more a basic classical computing question (and therefore should have been trivial), but it was blocking my understanding of the quantum solution... $\endgroup$ Mar 11 at 11:32
3
$\begingroup$

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$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.