1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ So it would be $\theta(n^2)$? $\endgroup$ May 5, 2021 at 2:16
  • $\begingroup$ more like $n$. You only have at most $n$ CNOT gates... $\endgroup$
    – KAJ226
    May 5, 2021 at 2:27
  • $\begingroup$ So the number of gates is all that matters? $\endgroup$ 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$
    – KAJ226
    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$
    – DaftWullie
    May 5, 2021 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.