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)