9 Deutsch-Jozsa algorithm

 

This chapter covers

  • Obtaining information from classical functions
  • Function evaluations vs. function properties
  • Quantum gates that correspond to classical black box functions
  • Understanding the Deutsch algorithm and the Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm that we discuss in this chapter demonstrates some of the characteristics of typical quantum algorithms. The direct practical use cases may be limited, but the algorithm is a great tool for explaining the logic that quantum algorithms often follow.

9.1 When the solution is not the problem

Do you know if the number 168,153 can be divided by 3? There are a number of ways to find out. For example, you can simply take a calculator and obtain the result:

168153 / 3 = 56051

The result of the division is 56,051. But that was not the question. Actually, we don’t care about this result. But thanks to this evaluation, we know the real answer: there are no digits after the decimal point, so we can conclude the number can indeed be divided by 3.

There is another simple approach to find the answer to this question, and you might know this simple trick: take the sum of the individual digits that compose the number, and see if that sum can be divided by 3. If so, the original number can be divided by 3 as well. Let’s do that:

1 + 6 + 8 + 1 + 5 + 3 = 24

Since 24 can be divided by 3, we can conclude that 168,153 can also be divided by 3.

9.2 Properties of functions

 
 

9.2.1 Constant and balanced functions

 
 
 
 

9.3 Reversible quantum gates

 
 
 

9.3.1 Experimental evidence

 
 
 
 

9.3.2 Mathematical proof

 
 

9.4 Defining an oracle

 
 

9.5 From functions to oracles

 
 

9.5.1 Constant functions

 
 
 
 

9.5.2 Balanced functions

 
 

9.6 Deutsch algorithm

 

9.7 Deutsch-Jozsa algorithm

 
 
 

9.8 Conclusion

 
 

Summary

 
 
sitemap

Unable to load book!

The book could not be loaded.

(try again in a couple of minutes)

manning.com homepage
test yourself with a liveTest