1
$\begingroup$

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)
$\endgroup$
1
  • $\begingroup$ what's "this" qiskit website? Can you edit the post to include a link? $\endgroup$
    – glS
    Commented Mar 14, 2023 at 12:03

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your explanation, it kind of makes sense if we are allowed to assume that calling the oracle is constant complexity. I have another question that leads on from that where in the classical case would the oracle implemented by comparing all 1 bits and using the AND operator then would the overall complexity be the same as the quantum circuit? because then we would only need one call to the oracle function and the complexity of the function is the same. $\endgroup$
    – timmy1691
    Commented Mar 15, 2023 at 11:42
  • $\begingroup$ @timmy1691 Why would you need a single call to the oracle? The problem's statement assumes that the oracle is a block box, you cannot look up what bits are equal to 1. Even though you perform an AND between the input's and the sercret's bits, you still XOR them together at the end. You thus learn at most 1 bit of information $\endgroup$
    – Tristan Nemoz
    Commented Mar 15, 2023 at 15:19

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.