-
Book Overview & Buying
-
Table Of Contents
A Practical Guide to Quantum Computing
By :
In this chapter, we have introduced Grover’s algorithm, which tackles the problem of searching through an unsorted list and provides a quadratic speed-up when compared to any classical analogue.
We began by exploring what searching looks like in classical computers, and we saw how the reason behind the speed of classical search procedures lies not just in the speed of classical computers but in the sorting and structuring of data. We thus understood how, when data is not sorted or structured, classical computing is bounded to algorithms with O(N) complexity on the number of queries. On the other hand, quantum computing can use Grover’s algorithm to solve these search problems with O(
) complexity, thus obtaining a quadratic speed-up.
Once the scene was set, we began to explore Grover’s algorithm and we discussed how—after creating a perfectly balanced superposition between all the computational basis states—it consisted in the iterative application...