Deutsch’s Algorithm

Classical computers solve problems. If they didn’t solve any problems, we’d call them “classical waste.”

So, what about quantum computers? Are there any problems that quantum computers can solve? If you’ve read Chapters 1 to 6, you may be suspicious.

Chapters 1 to 4 describe qubits, but those chapters say nothing about problems you can solve with those qubits. Chapters 5 and 6 show you how to move qubits around, but neither of those chapters involves a question-and-answer scenario. You can ask a classical computer whether 15 equals 3 times 5. Could you ask a quantum computer to do that?

In this chapter, we pose a question and a quantum computer provides an answer. The question concerns binary-valued functions, and the answer comes courtesy of something called Deutsch’s algorithm.

When you read about Deutsch’s algorithm, your first impression may be that this algorithm is a complete waste of resources...