Key Takeaway - DJ

Let’s summarize the technique we have learned in the Deutsch-Jozsa algorithm and hint at other algorithms that utilize it to achieve better time complexities than their classical counterparts.

We’ve seen our first practical quantum algorithm in-depth throughout this chapter. However, you might be thinking that that algorithm might not be that useful in itself, and you wouldn’t be wrong in thinking so. But in it lies an immensely powerful technique.

The Deutsch-Jozsa algorithm teaches us that we can exploit the power of superposition using oracles. Since its inception, other algorithms using the same intuition have cropped. The Bernstein-Vazirani Algorithm can guess a bit-string in O(1)O(1) using a very similar approach. There’s also Simon’s Algorithm, which asks a similar question to the Deutsch-Jozsa Algorithm, that is, given a function ff, how can we efficiently determine if ff is one-to-one or two-to-one? Again, the solution, as you would expect, is along the same lines as that for the DJ algorithm with comparable time complexity.

Get hands-on with 1200+ tech skills courses.