The word quantum computing has been overused in the likes of artificial intelligence, but how much truth do the preachers of apocalypse hold? In this post, we shall explore how quantum computing works and what its consequences for cryptography would be.
How do quantum computers work?
Most people have heard that the way quantum computers work is by acting on all the bits at once instead of one by one, as classical computers do. This helps people vaguely understand how it works, but it violates the nature of quantum mechanics. One of the key concepts in quantum mechanics is the abandonment of determinism. We no longer know things, we just know the roof probability that a certain thing will happen. In this sense, when we evaluate a quantum circuit, we apply the function multiple times and get the most probable state that the system ends up in. This process can be performed multiple times thanks to the superposition principle.
The superposition principle is another misunderstood concept in quantum computing. A more rigorous (but not too formal) way to think of it is like a vector. We can have a list of real numbers (or complex!) that dictate the probability we will end up in a certain state. So, for example, if I have two states, |0⟩ and |1⟩, I can have the vector (0.6, 0.8) respectively. The probability to measure it is given by the square of the components. In this case, it will be more probable that when I measure the system, I end up with state |1⟩ than |0⟩. This also fundamentally changes the system, and now instead of being in the state (0.6, 0.8), it is in the state (0, 1).
So, if we need to compute this operation thousands of times, how is it claimed to be faster than a classical computer? In more advanced quantum mechanical terms, it is thanks to the properties of the Hilbert space that these states live in and the tensor product. But what this essentially means is that these functions can be applied to the whole vector. In classical computing, we would have to check component by component—so if we have a list of thousands of elements, the run time will increase linearly. If we increase the number of elements by 1000, the run time is multiplied by 1000. This is not the case for quantum computers. Since we’re applying the function to each state at the same time, the time does not increase so steeply.
More visually, what a quantum computer does is a process very similar to a Galton box. The system measures and gives back the state it has measured many times, so it eventually settles into the most probable one. A video can be seen below.
Grover’s Algorithm
Grover’s Algorithm is the most well-known quantum algorithm and the one said to break classical cryptography. This process is infamous for being hard to understand, but I’ll try to explain it as intuitively as possible.
This algorithm was intended to solve problems which are easy to check if they’re right, but for which we don’t know the general formula. A good example would be a sudoku. We do not know the specific solution, but we can check if it’s correct very easily. In cryptography, a method that works like this is hashing. In these protocols, you input a string and get back a long and random string of characters. This problem is only known to be solvable by brute force (trying every single combination).
If it’s a long string of information, it can take on average hundreds of years to find the correct one that contains the key we want. We measure this using something called algorithm complexity. This tells us how the time it takes to execute an algorithm scales as you add more elements it has to analyze. The information perceived in the following graph is what’s worrying the whole world.
I want you to try to guess which one is the classical algorithm and which one is Grover’s Algorithm.
Shows the comparison between classical algorithms and Grover’s algorithm in terms of the complexity by the number of tries. Made using Desmos.
As you probably guessed, the red one corresponds to Grover’s Algorithm. However, it’s not time to worry. Looking more technically at the algorithm, the function described by Grover’s is √N for N elements. The graph might look alarming, but it’s not as bad as it seems, there’s still hope that these quantum algorithms won’t break everything.
An example of this is the most popular hashing algorithm: SHA-256. It’s particular because it generates a string of 64 characters, which corresponds to 256 bits. You might think there’s a logical way to reverse-engineer the algorithm, but it’s been found that the easiest way to break it is brute force. To see how these strings are different, look at the different hashes created for almost the same string:
- String: Grover’s algorithm
- Hash: 09e439aab9702e3f126ec226933df4ac799bed1cdf33d469124bb43413493651
- String: Grovers algorithm
- Hash: 4ba0f872874546b1712424b09f2c96c2ae7a4000eac69a72107be325bb9fd02a
So it makes sense how one would use brute force. However, this entails going through 2256 combinations. Grover’s algorithm reduces this to 2128. For reference, here are the size comparisons:
- 2²⁵⁶: 115792089237316195423570985008687907853269984665640564039457584007913129639936
- 2¹²⁸: 340282366920938463463374607431768211456
It’s quite a bit smaller, but if a quantum computer had the same power as a classical one, it would still take a lot of time.
In conclusion, Quantum computing and cryptography is a powerful combo, and we can already see its effects in algorithms like Grover’s. However, despite the looming threat, physical and power limitations are still a big challenge before quantum computers can reach the capacity that classical ones have. That said, every year these machines are getting faster, and more money is being poured into improving them. So the future looks interesting. It’s not the apocalyptic vision some sensationalists are trying to sell you, but a hopeful one.
Bibliography
EMN178. “SHA256 Online.” EMN178 Online Tools. Accessed May 5, 2025.
https://emn178.github.io/online-tools/sha256.html.
Wikipedia contributors. “Galton Board.” Wikipedia. Last modified April 24, 2025. https://en.wikipedia.org/wiki/Galton_board.
TalentQ-ES. “Grover’s Algorithm – Introduction.” Fault-Tolerant Algorithms. Accessed May 5, 2025. https://talentq-es.github.io/Fault-Tolerant-Algorithms/docs/Part_01_Fault-tolerant_Algorithms/Chapter_03_01_Grover_portada_myst.html.
