How would one determine the worst-case asymptotic complexity ($\theta$) of a Bernstein-Vazirani circuit encoding the secret 1111?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ So it would be $\theta(n^2)$? $\endgroup$ Commented May 5, 2021 at 2:16
-
$\begingroup$ more like $n$. You only have at most $n$ CNOT gates... $\endgroup$– KAJ226Commented May 5, 2021 at 2:27
-
$\begingroup$ So the number of gates is all that matters? $\endgroup$ Commented May 5, 2021 at 2:28
-
$\begingroup$ 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... $\endgroup$– KAJ226Commented May 5, 2021 at 4:23
-
$\begingroup$ The complexity for an oracle-based problem simply counts the number of calls to the oracle. It does not count the number of other gates applied. $\endgroup$ Commented May 5, 2021 at 6:44