Nice try Google. You bet we didn’t see that coming. Maybe another move in hopes of getting your stock up? (I have 5 shares 😭)
Unless you’ve been living under a rock, Google released it’s all new Quantum AI Chip- Willow! Google claims it is able to solve one of the hardest benchmark tests in under 5 minutes. To provide context, our existing computers, more commonly called classical computers, would take over 10 septillion years to solve it. That’s more time than the age of our universe. Seeing these results, one might get excited. But what if I say that my laptop is still more efficient if I want to calculate 9892³² or run my Python application. What if I told you that there is a fine line of difference between efficiency and time? And what exactly is a Quantum Computer?
Tag along. I’ll try to sound as less technical as possible.
The Underlying Concept of Quantum Computing
In computers, electrons are the currency. Everything our laptop does- displaying using pixels, CRUDing data, run games, is translated into some form of math that can be simplified and solved using binary 0s and 1s. In classical computers, we have 2 types of bits — 1 or a high and 0 or a low. We can determine, modify or create a high or a low bit by influencing the current, magnetic alignment or voltage of a given circuit.
Our computers calculate these bits over the billions of transistors and capacitors inside its tiny computer chips, and then do some math, and then some more math to finally produce action. A very basic laptop can perform up to 1–2 billion calculations/sec (termed GHz). It is truly an exceptional piece of invention. The question it poses is- if computers already are so fast, what is the need to go faster? I mean, I wouldn’t mind if my Python program takes an extra couple of milliseconds to run. Quantum Computers attempt to change the very fundamentals of how bits are stored.
Any electron has three main properties: mass, charge and spin. If you paid attention in your Physics 101 class, you might recall that any particle with a charge, when spinning on it’s axis, generates a magnetic field. In case of a singleton electron, this value is inconsequential, but when we talk about groups of electrons, the value could be as big as you want. Now, since this is not classical physics, the electrons aren’t spheres spinning about an axis.
The Stern–Gerlach experiments proved a presence of intrinsic momenta in electrons. They observed that 2 silver atoms had distinct, possible angular momenta (momentum about the electron’s center of mass), but no orbital momentum (momentum due to the electron revolving around the nucleus). And since momentum cannot exist without motion, we tend to generalize it to a quantum property termed as spin. The resulting magnetic field generated can be used to calculate the bit value. Now, it is pretty intuitive that there would be 2 types of spins (similar to a 0 or a 1, let’s call them up and down), and rightly so. And we use these spins to determine bit values in our Quantum Computers, compared to the traditional high/low states discussed above.
Since electrons are incredibly tiny particles (or waves), their quantum properties cannot be observed directly, at any given time and we can only calculate probabilistic outcomes of their spin states. Quantum mechanics tells us that an electron does not have a definite spin state until it is measured. Instead, its spin exists in a superposition, meaning it is a combination of all possible states (e.g., spin-up and spin-down) with certain probabilities. This superposition is what gives rise to the concept of a Quantum bit or Qubit, enabling quantum computers to represent and process information in ways and orders classical bits cannot.
Where Quantum Computers have an Edge
Let us talk about classical bits (0s and 1s)- if I want to represent information in 2 bits, they would be as follows: 0 0, 0 1, 1 0, 1 1. These combinations represent four distinct states, but again, each state is only composed of two discrete bits. If my machine wants to process these, it can analyze the first bit and the second bit independently to determine the full state.
Now imagine we have 2 qubits, each of which can exist in a superposition of 2 states (spin-up and spin-down, or ∣0⟩ and ∣1⟩). Together, these qubits can form a superposition of 4 possible combined states: ∣00⟩, ∣01⟩, ∣10⟩, and ∣11⟩. More accurately, the superposition can be shown using arrows as such:
However, unlike classical bits, these states do not exist independently — instead, all 4 states coexist in superposition, each with its own complex probability values. Let us name call them α, β, γ & δ, each of which determine the likelihood of measuring the system in each state. The full quantum state of the 2 qubits is represented as:
In short, for defining 2-spin system, we technically need 4 distinct values, as opposed to classical bits where we need only 2 different bits. If you keep on going calculating for a 3-spin, 4-spin and a 5-spin system, you might find it a bit hard to keep track. You will notice that for a n-spin system, we need 2 to the power n different variables. Shoot it up to 500-spin system, and you would have more bits than there are particles, in our universe. Truly fascinating!
Clearly, this indicates how efficient qubits are. Just give it n classical bits (or variables) and it performs calculations on 2 to the power n bits. By performing such parallel computing on an exponential number of steps, where a simple computer could take 5000000 steps, you might find a quantum computer do that in 2–3 or even 1 step.
Quantum Computer vs Classical Computer
What if I tell you that your laptop is as good as a quantum computer for almost everything that you do right now? Baffled? Don’t be.
Quantum computers are revolutionary, but their true power lies in solving very specific types of problems where quantum phenomena, like superposition and entanglement, provide an advantage. These include tasks like factoring large numbers (important for cryptography and SNDLs), simulating quantum systems (useful in materials science and drug discovery), and optimization problems, and are often termed as Quantum algorithms. For these, quantum computers can potentially outperform classical ones by orders of magnitude.
If you’ve been following this industry for a while, there is no better example than Shor’s Algorithm. In layman terms, they are a set of approaches that attempt to find the prime factors of an integer as big as possible, in polynomial time. It addresses the problem of factoring large integers — a task central to the security of many encryption schemes, such as RSA. Here’s an explanation, starting with why classical computers struggle and why quantum computers excel.
Why Classical Computers Fail
Classically, the most efficient known algorithm to humans, for factoring large integers is the General Number Field Sieve (GNFS). But, even the GNFS has a complexity that grows sub-exponentially with the size of the number N, specifically:
where c is a constant. This complexity means that as N grows, the time required to factor it becomes infeasible. To serve an example, a 2048-bit number (N) would take thousands of years to factor using the GNFS on current classical supercomputers.
The reason classical computers struggle is the lack of efficient algorithms to solve the factorization problem, primarily because they process operations sequentially or in limited parallel. Factorization inherently requires testing divisors or performing modular arithmetic, tasks that scale poorly with N.
Why Quantum Computers Excel
Shor’s Algorithm leverages the fascinating principles of quantum superposition and quantum interference to achieve polynomial time complexity for factoring. The crux of Shor’s algorithm is its ability to reduce factoring to a problem of finding the period (time after which a function repeats itself) of a function. The steps include:
- Reduction to Period Finding: Given an integer N, (say 102301283891283018239182308123) choose another random integer “a” such that the highest common factor or HCF(a,N) = 1. If we find such a number, The task then becomes finding the smallest integer “r” (period) such that:
- Quantum Fourier Transform (or QFT): This is where the magic happens. On a quantum computer can, we can efficiently find this period “r” by preparing a quantum state that represents all possible values of “r”, and convert this into a mathematical functions, and finally using a Fourier Transform to amplify the periodicity of the function.
- Classical Post-Processing: Once the period is found, N can be factored using classical arithmetic.
Mathematical Speed-Up
In Shor’s algorithm, the quantum step — finding the period “r ”— is exponentially faster than classical methods due to the parallelism enabled by superposition and entanglement. The algorithm runs in time:
This is dramatically faster than the GNFS whose runtime was given above. Just to compare, assume my number is 2048 bits, making N = 2048.
Put it in the O() function and you will find out that GNFS takes approximately O(e⁸⁴) where as Shor’s approach rounds up to O(110,000). The difference is in the magnitude of orders of 10. Crazy!
A Twist in the Story
The first is that Willow can reduce errors exponentially as we scale up using more qubits. This cracks a key challenge in quantum error correction that the field has pursued for almost 30 years.
by Hartmut Neven, Founder and Lead, Google Quantum AI
Imagine a random glitch that flips the value of a bit. This will cause an error. To increase tolerance of errors, we can increase the number of bits that hold information. For example- if my information is contained within 5 bits, and 2 bits flip, the information in 3 bits is still conserved. You can handle errors by checking the majority bits and replacing the errored bits with that. But what happens when we move onto 5, 7 or 9 bits. Even though we create a higher tolerance for errors, we also introduce many more ways to cause them.
Taking this to the quantum world, given the number of calculations performed every second plus the impossible task of reversing/manipulating qubit states, the error threshold increases exponentially. Each time a new qubit is added, the margin of error only increases. There needs to be a way diagnose errors without almost having to detect them.
Of course, there is! Russian scientist Alexei Kitaev found a way called the “surface code” that uses a grid of qubits to encode information redundantly. Instead of relying on individual qubits, it uses groups of them to represent a single piece of information. This makes it possible to detect and correct errors without destroying the data.
It’s like having a puzzle where, if one piece is misplaced, you can figure out where it should go by looking at the surrounding pieces. The surface code organizes qubits in such a way that errors are easy to spot and fix.
Willow serves as a testament that this approach has benefitted them, and as one would expect the opposite of, adding more qubits has reduced the error margins.
What’s next!
So much for my first Medium article. I’m only a student so to all the PhDs and cracked scientists, take this with a grain of salt. I’ve always been curious about Physics in general, and it truly brings me to a realization of how much more there is to know.
Next up is about the Random Matrix Theory, Random Circuit Sampling and how Google’s Willow begs to differ.