In the last story, we explored how quantum physics can be exploited to have Qubits and also Quantum Gates. Now, let’s see what we can do with that.
But before we do that, we need to take one step back to explain another thing. Google’s chip Sycamore that I talked about last time uses 53 Qubits to achieve - as they claim - quantum supremacy. However, there are companies such as the Canadian firm D-Wave Systems that has sold such a 128 Qubit Computer in 2011 already and a system with as much as 2048 Qubits in 2019. Aren’t they miles ahead?
Well, we are actually mixing two things here. Because, what D-Wave has actually built is a quantum annealing machine. Quantum annealing means that there are no actual transformations applied on the Qubits. Instead the only operation that can be performed is the search for a global energetical minimum. This is very useful to solve optimization tasks. However, it is not a general purpose quantum computer as modeled by the Quantum Turing Machine as a general model for computability.
So, let’s finally talk about the real thing: How can I benefit from quantum computing as a programmer. There have been algorithms developed for quantum computers before the hardware has been developed. Actually, there is one - Grover’s algorithm - for which it has been formally proven that quantum computers outperform classical ones.
The task we are talking about is search within an unsorted database. With classical computers this task can be performed in O(n) by - there is no better way - linearly going through all entries. With Grover’s algorithm this can be solved in O(√n). Everyone who works with large datasets will know from experience that this really makes a difference. As for the search in unsorted datasets, Grover’s algorithm can generally be applied to NP-hard problems.
There is quite some complex math behind that algorithm. Leaving that all aside the algorithm facilitates the quantum effect, that a quantum register, as a series of Qubits can take all possible values at once in its superposition state. We then need a helper function - our Oracle - that can tell if a possible solution is the correct one or not. Again - in quantum terms - we can use this to check all possible solutions at the same time. If a candidate is a valid solution, it’s contribution to the superposition is changed in a way that it can later be measured. At the end, we need to dissolve the superposition to measure the correct answer. You can imagine that it is a bit more complex when you look at the details, but let’s leave it like that for now and briefly talk about yet another specific field of quantum computing.
Quantum computations are probabilistic processes. This means there is no guarantee that the correct result will indeed be measured. Well - does this make any sense at all? Yes! Because we can repeat the entire procedure to conduct several measurements of the result and to step by step eliminate uncertainty towards a high confidence.
In the next story we will have a look at another quantum computing algorithm and the severe implications it will have on our today’s computer systems.