Chapter 10
Quantum Search

In Chapter 9, ​Alice in Quantumland—Quantum Cryptography​, you saw how a circuit that essentially duplicates back-to-back quantum gates collapses qubits to their original states thereby permitting recovery of a secret message. Quantum effects get even more tantalizing when applied to applications such as the optimal routing of airliners, detecting the presence of cancer cells in medical images, or even simply making you rent another movie or buy another book. In each of these cases, classical computer algorithms churn through millions of possibilities to come up with a flight schedule, correctly diagnose diseases, or offer up movie or book choices that nudge you to another click-to-buy. But quantum computers hold the promise of simultaneously evaluating all these millions of combinations and identifing the correct one in just a handful of steps. The techniques you’ll see here are impossible to conduct with classical computers.

Harnessing these quantum effects, however, gets more intricate than the applications you worked with earlier. In ​Design a Teleporting Circuit​, although you could potentially teleport hundreds of qubits, the quantum entanglement effects are localized in groups of a few qubits. As with teleporting, in Chapter 9, ​Alice in Quantumland—Quantum Cryptography​, the mechanism to share cryptographic keys that can’t be meddled with, again, relies on quantum effects restricted to groups of a couple of qubits. In searching for solutions across a large number of possibilities, the quantum effects are intertwined across the entire gamut of all possible quantum states—you can’t break up the problem and apply quantum effects in smaller chunks.

To design quantum-based search algorithms, you need to shed the “classical” ways of thinking and develop a new mindset. In this chapter, you’ll begin that transformation.

Working with Simple Applications

To better illustrate the quantum effects in search problems, we’ll work with simple applications. This will help build your intuition instead of getting caught in mathematical minutiae. But you should bear in mind that the concepts you’ll learn can be extended to larger problems. Also, although the quantum technology and hardware is evolving rapidly, we’re limited, when compared to classical machines, by the number of qubits we can program with. Working with smaller problems for which you can develop quantum circuits will let you see how quantum effects are introduced for yourself—a far more satisfying approach than just a theoretical exposition. So rather than just showing you how to hook up S gates and gates that demonstrate arbitrary quantum behavior and leaving this chapter out of the book entirely, I wanted to at least give you a taste for how quantum computing can be brought to bear on applications that search through a vast number of permutations. This way, you’ll ready to solve industrial scale problems when larger quantum computers become available.