9.8 The Deutsch-Jozsa algorithm

I will now walk you through another early quantum algorithm that employs oracles. It shows us another form in which we express oracles in quantum circuits. algorithm$Deutsch-Jozsa Deutsch-Jozsa algorithm

Let’s begin with an example. Suppose I buy two standard decks of 52 playing cards. In a separate room where you cannot see me, I create a single deck of 52 cards where one of the following is true:

1. All the cards are red, or all the cards are black.
2. Half the cards (26) are black, and half are red.

We call the first option “constant” and the second “balanced.”

I now go to you and give you the problem of finding out which of the two possibilities is the case for the deck I am holding. You do so by looking at and then discarding cards at the top of the deck.

In the best case, the first card is one color, and the second is the other. Therefore, the...