Worst Case Asymptotic Complexity of Berstein-Vazirani

How would one determine the worst-case asymptotic complexity ($$\theta$$) of a Bernstein-Vazirani circuit encoding the secret 1111?

Given a secret n-bit string $$s = s_1 s_2 \cdots s_n$$ where $$s_i \in \{0,1\}$$ the worst case scenario for the Oracle (when all your secret bits are non-zero) is that you will have a circuit depth $$n$$ of $$n$$ layers of $$CNOT$$ gates. This is because at each $$s_i \neq 0$$, there will be a CNOT gate from the qubit $$q_{s_i}$$ to the ancilla qubit.
• So it would be $\theta(n^2)$? May 5 '21 at 2:16
• more like $n$. You only have at most $n$ CNOT gates... May 5 '21 at 2:27
• The circuit complexity basically counts the number of quantum gates from a given gate set to execute a certain unitary operator... here, the number of gates to encode the secret bit string (to encode the Oracle) scales at worst as $O(n)$. With that said, the Bernstein Vazirani algorithm has $O(1)$ run-time complexity since you only need one execution to get the result, given that you have a `'real' quantum computer... May 5 '21 at 4:23