Understanding the Bernstein-Vazirani implementation from the qiskit website

Question

My question is with regards to the implementation from the Qiskit textbook.

From my understanding the algorithm is for finding out what an unknown bit-string is which in the classical case requires N operations where N is the length of the string.

My question is in the below snippet, is it not doing N operations within the oracle function? Can someone explain where the speedup is happening?

Because in the classical case you can apply the oracle function anyways, as in check every bit in the string similar to what the oracle is doing. I feel like I am missing something, so would be great if someone can help. Thank you.

# Apply the inner-product oracle
s = s[::-1] # reverse s to fit qiskit's qubit ordering
for q in range(n):
    if s[q] == '0':
        bv_circuit.i(q)
    else:
        bv_circuit.cx(q, n)

Answer 1

The Bernstein-Vazirani algorithm is an oracular problem: you suppose that you are given an oracle that implements a function $f$ such that there is a secret $s$ such that $f(x)=x\cdot s$. Crucially, you assume that the oracle runs in $O(1)$ time. What really matters then is how many evaluations of $f$ the quantum algorithm runs and compare it with how many evaluations the classical algorithm runs.

In this particular case, one might argue that the oracle in the Bernstein-Vazirani algorithm will always run in $O(n)$ time, because it will simply be implemented with CNOT on the bits of $s$ that are equal to 1. However, note that one might argue the very same thing for the classical evaluation of $f$. Thus, if you take into account the time required for evaluating $f$, then the quantum algorithm runs in time $O(n)$, while the classical one runs in time $O\left(n^2\right)$. Thus, you still get a quadratic speed-up.

However, allow me to reiterate that it's not the "right" way to consider this problem. The only goal of the Bernstein-Vazirani algorithm is to show an oracular separation between two classes of complexity. As such, what really matters is the number of calls to the oracle, rather than its actual implementation. Under this point of view, the classical algorithm runs $n$ calls to the oracle, while the quantum algorithm issues a single one.