Learning about the foundational oracle-based quantum algorithm

We learned in the previous section that the very early quantum algorithms illustrated quantum speedup vis-à-vis classical systems in relation to a simple problem. In this section, we will expand on this to look at a more complex problem, which we can speed up or increase the advantages over classical systems. To do this, we will learn about another oracle-based algorithm, Bernstein-Vazirani. The difference between this one and the previous foundational algorithms is that the Bernstein-Vazirani algorithm will identify a hidden bit string using an oracle function in a single query.

Learning about the Bernstein-Vazirani algorithm

Originally invented in 1992 by Ethan Bernstein and Umesh Vazirani, the Bernstein-Vazirani algorithm extends the Deutsch-Jozsa algorithm to a generalization to find an unknown or secret bit string. Where the Deutsch-Jozsa algorithm worked to solve the problem of determining whether a given...