Willow: Unpacking the Quantum Leap

When Google unveiled Willow, its latest quantum computer, the headlines were as dramatic as the possibilities: "A quantum leap forward," "The dawn of practical quantum computing". WTF it means?

When Google unveiled Willow, its latest quantum computer (QC), the headlines were as dramatic as the possibilities: "A quantum leap forward," "The dawn of practical quantum computing". WTF it means?

My honest reaction to Willow's headlines was realizing I had no clue what they were really talking about. Yup, quantum computing sounds fancy, but what is it? Is it a more powerful laptop? Is it something completely different? As Cleo Abram puts it: "A quantum computer is not just a faster version of your laptop. It's an entirely different kind of machine designed for an entirely different set of problems."

Quantum computers are not faster computers; they are completely different tools that allow us to explore spaces that classical computers cannot. Source

This post summarizes the rabbit hole I have been in for the last two weeks. It is long and detailed, but as always, it forces me to clarify my thoughts.

Why is it worth entering this 🐰hole now?

Willow caught my attention, and when I started to dig, I soon understood that it was a good time to get up to speed - dummy level - into what QC means. Three key factors have aligned:

1. Technical Breakthroughs: Willow error correction (more on this below) is a giant leap to prove that scalable QC is possible, and as Sam Altman repeats, once you know something can be done, then is an engineering problem.

2. Strategic Necessity: we are in a techno-cold war, and QC is another front.

3. Commercial Potential: Early quantum applications in drug discovery and materials science are showing promise

These three things together tell me that things will move fast going forward, and I definitely don’t want to lose.

What’s a Quantum Computer?

To really unpack Willow’s news, we need to go deep into what is going on in a quantum computer. For that, let’s start by refreshing the basics of classical ones.

Understanding classic computers

At their core, computers are remarkably simple devices consisting of three main components:

• Memory to store information in binary (01001100 01110101 01111010 01101001 01100001)

• An arithmetic unit to perform calculations (2+2=?)

• A control unit to coordinate operations (if xx then)

These three operations can be done using transistors —tiny switches that can be either on (1) or off (0). By chaining these transistors together, we can create basic operations like AND and XOR and eventually build up to “complex” calculations like sums and multiplications. Once you can do multiplications, you can do anything.

Binary addition with Logic Gates, by Shynn Lawrence

For years, we have worked hard to be able to do more and more of these basic operations on our computers with a conceptually simple - technically really challenging - approach, make transistors smaller.

From a transistor made out of a vacuum tube - Awesome Veritasium video on the topic

To trillions of transistors in a tiny chip in only 30 years

And we have come a long way. Modern transistors are incredibly tiny, with leading manufacturers like TSMC and Intel producing 3-nanometer chips (about 1/30,000th the width of a human hair). But we're nearing fundamental physical limits. As transistors approach atomic scales, quantum effects interfere with their operation, and we likely won’t get much more compute from existing technology.

The Quantum Difference: Not Just More Computing Power

The distinction between quantum and classical computers goes far beyond processing power. Certain problems—like factoring large numbers or simulating quantum systems—are inherently better suited for quantum computers. That does not mean that, given infinite computing power, these problems can’t be solved, but there are better ways to do it. Think of it like the difference between boats and cars—it's not that one is "better," they're just designed for fundamentally different environments and purposes.

The fundamental difference between both systems is that while classic computers can be in either 1 or 0, a quantum computer can be simultaneously in all positions. If that does not say much to you, you are not alone. All that comes below is my attempt to make sense of this idea. Let’s start with the two properties of the quantum realm that make this possible

Superposition and Measurement

Unlike classical bits that must be either 0 or 1, quantum bits (qubits) can exist in a superposition of both states. While it's tempting to think of this like a spinning coin, quantum superposition is far stranger. With a spinning coin, we don't know if it's heads or tails until it lands. However, a qubit in superposition is actually in all states simultaneously, with specific probabilities for each state that we can manipulate through quantum operations.

To visualize this, physicists use something called the Bloch sphere. Imagine a globe where the North Pole represents state |0⟩ and the South Pole represents state |1⟩. A classical bit can only be at either pole, but a qubit can exist at any point on the sphere's surface. The latitude and longitude of this point tell us the exact mixture of |0⟩ and |1⟩ states.

Bloch Sphere is an intuitive representation of a qubit - Source Wikipedia

In reality, qubits are described by quantum wavefunctions—mathematical functions representing this complete state of possibilities that result in a probability distribution of the encoded variables. The number of states encoded by these qubits behave like classical bits 2**n

Quantum probability distribution of two physical qubits. Source [1]

But here is the key: when we measure a qubit, it "collapses" to either 0 or 1. That means that the qubit stops being in superposition.

This might seem to negate the advantage of superposition—after all, we end up with just a classical bit. But the magic happens before measurement, in how we manipulate these superposition states. Through carefully designed quantum operations, we can make the wavefunction interfere with itself in ways that amplify the probabilities of the answers we're looking for. Introducing quantum interference.

Quantum Operations and Interference

Think about solving a maze. A classical computer would try one path at a time, systematically exploring each option. A quantum computer, through superposition, can represent all paths simultaneously. However, the real quantum advantage isn’t just "trying everything at once"—parallel classical computers can attempt that too. The unique power of quantum computing comes from interference.

Interference is the result of manipulating the qubits to force the combined wavefunction to return the desired results - Source [2]

Interference in quantum computing works like waves in water: waves can add together (constructive interference) or cancel each other out (destructive interference). By carefully designing quantum operations, we manipulate the qubits to interfere in such a way that the paths leading to wrong answers cancel each other out, while the paths leading to the correct answer reinforce each other. When we measure the qubits, the probability of getting the right answer has been amplified, making it much more likely to appear.

Imagine dropping pebbles into a pond to find the shortest path in a maze. Each pebble creates ripples, and as the ripples overlap, they interact. For paths that lead to dead ends (wrong answers), the ripples cancel each other out through destructive interference. But for the correct path, the ripples align perfectly, creating a strong, visible wave (constructive interference). When you measure the waves, you’re most likely to detect the strongest one—the correct solution. This is how quantum computing cleverly narrows down the possibilities.

Entanglement

One final property before we go to an algorithm.

Entanglement is the capacity for two qubits to get their states correlated. In other words, if you have two entangled qubits and measure one, you immediately know the result of the other, regardless of how far apart they are (which can be very far). Einstein called this "spooky action at a distance."

🐰 - Faster than light communication?

In quantum computing, qubits are influenced through carefully designed operations like interference and quantum gates, which manipulate their states intentionally within a controlled system. However, when it comes to entanglement, the situation is different. While two entangled qubits share a correlation such that measuring one instantly determines the state of the other, this process is inherently random, and randomness cannot be used to encode or transmit meaningful information. Unlike the deliberate manipulation of qubits in a quantum computer, you can't control the state of one entangled qubit to influence its partner in a specific way. To communicate meaningful information, a classical channel is still required to interpret or synchronize measurement results, which is constrained by the speed of light. Therefore, entanglement alone does not enable faster-than-light communication, even though it reveals a profound and instantaneous connection between particles.

Quantum Gates: The Building Blocks of Quantum Computation

Quantum gates are the fundamental building blocks of quantum computation, just as classical gates (AND, OR, NOT) are for classical computers. They are tools designed to manipulate qubits, harnessing their quantum properties like superposition and entanglement.

Single-qubit gates, such as the Hadamard (H) gate, create superposition, while Pauli (X, Y, Z) gates rotate qubits along the Bloch sphere. Phase gates (S and T) add specific phase angles to the quantum state. Multi-qubit gates unlock the true potential of quantum computing by enabling interaction between qubits. For instance, the CNOT gate (a quantum XOR) flips a target qubit based on a control qubit's state, while the SWAP gate exchanges the states of two qubits. Gates like the Toffoli (CCNOT) and CZ extend these operations to three or more qubits, allowing for intricate quantum circuits. Together, these gates form the foundation for building quantum algorithms.

Universal Quantum Computation

Here's where it gets interesting: just like how NAND gates can build any classical computation, a small set of quantum gates can approximate any quantum operation. The most common universal gate sets are:

1. Clifford + T: The Hadamard, CNOT, and T gates

2. H + CNOT + Toffoli

This means we can build general-purpose quantum computers that can, in theory, implement any quantum algorithm. However, there's a catch: unlike classical gates which are perfect, quantum gates are prone to errors. Each gate operation introduces small imperfections that can accumulate. This is why error correction (like what Willow achieves) is so crucial.

Quantum Gates and its unitary matrixes. Quantum gates are represented as unitary matrixes as a way to reflect the probabilistic nature of the wavefunction and its reversibility (the Ctrl + Z of the quantum world)

How Gates Create Algorithms

Quantum algorithms are built by carefully arranging these gates into circuits. For example:

1. Start with qubits in state |0⟩

2. Use H gates to create a superposition that become the inputs of our problem

3. Apply multi-qubit gates to create entanglement and interference

4. Measure the result

Think of it like a quantum choreography—each gate is a specific move, and the sequence of moves creates the dance that solves our problem.

The cryptography example or how QC will break the internet

The most immediate and profound impact of quantum computing will likely be in cryptography. To understand why, we need to dive into how current encryption works and why quantum computers pose such a unique threat.

How RSA Works: The Foundation of Modern Encryption

Today's internet security largely relies on RSA encryption, which is based on a beautifully simple idea: multiplying two large prime numbers is easy, but reversing that multiplication—factoring the product into its original primes—is computationally hard. This means there is no known algorithm that can solve it efficiently. For example, multiplying 17 and 23 to get 391 is straightforward. However, if you're given 391 and asked to find its prime factors, the task becomes exponentially more difficult as the numbers grow larger.

Modern RSA encryption uses numbers with hundreds or even thousands of digits. To be precise, 2048-bit RSA keys correspond to numbers with about 600 digits, while 4096-bit keys reach around 1200 digits. The difficulty of factoring these massive numbers is what keeps your private communications secure. Classical computers would need millions of years to break RSA encryption by brute force, trying one combination at a time.

Initially, I found this hard to grasp. For some reason, I thought there couldn’t be that many prime numbers within the range of RSA encryption limits. But the Prime Number Theorem tells us that while the density of prime numbers decreases as numbers grow larger (which makes sense), the total count remains astronomically high. Applying this theorem, we estimate around 10ⁱ²³⁴ primes within the range used by RSA encryption, leading to approximately 10²⁴⁶⁸ combinations of prime pairs. Clearly, not a problem for pen and paper.

Enter Shor's Algorithm

That encryption cannot be broken with classic computing, or at least there is no known algorithm that can do it efficiently, depends on how many attempts, on average, you would need to do to randomly find the two prime factors composing the encryption key.

Shor’s Algorithm, developed in 1994, fundamentally changes the game. This quantum algorithm can factor large numbers exponentially faster than classical methods (sqrt(N)), which is a much much nicer computational function.

Instead of brute-forcing each possibility, Shor's algorithm transforms the problem into finding the periodicity of a mathematical function. Using quantum superposition, the algorithm evaluates all possibilities simultaneously, leveraging quantum interference to amplify the correct periodic patterns while canceling out incorrect ones. The core step, a quantum Fourier transform, extracts the periodicity efficiently, which is then used to deduce the prime factors through classical post-processing. This process enables exponential speedup, reducing tasks that would take millions of years for classical computers into hours on a sufficiently powerful quantum computer.

Shor's algorithm seeks to amplify the wavefunction to surface the periodicity of the public key module - source [2]

To make matters worse, adversaries can capture encrypted data now and decrypt it later once quantum technology matures—a strategy known as “store now, decrypt later.” This makes quantum-resistant encryption an urgent priority.

Why This Matters: The Quantum Threat

Under this paradigm, no secret is safe, and to make matters worse, there is the “store now, decrypt later” threat. Adversaries could capture encrypted data today and store it, waiting for quantum computers capable of breaking RSA to mature (your PornHub habits are not safe no matter how much VPN you use). This makes transitioning to quantum-resistant encryption methods a pressing priority.

Tapping into our current optical fiber is relatively easy. You can’t understand the data, but you can see it. With the right QC, decrypting that data will be possible in the future - source

Qubit Overhead and Breaking RSA

Today’s qubits are not perfect, requiring significant redundancy to form a single reliable, error-corrected logical qubit. To break RSA encryption with 2048-bit keys, a quantum computer would theoretically need approximately 4000 logical qubits for the primary computation, plus an additional 2000 qubits for intermediate calculations—resulting in a total of 6000 logical qubits in a perfect system. However, due to the imperfections of current qubits, this number grows significantly.

Current quantum systems require around 1000 physical qubits to create a single logical qubit, meaning a practical system for breaking RSA would need roughly 6 million physical qubits. This staggering number highlights the challenge of scalability. Willow’s advancements in error correction reduce the overhead needed by enabling “below-threshold” error rates, where adding more qubits improves reliability rather than compounding errors, getting us closer to solving this problem.

The Willow Breakthrough

The significance of Google's Willow quantum computer lies in its ability to overcome one of quantum computing's biggest challenges: error correction. Quantum states are incredibly fragile, and maintaining them long enough to perform useful computations has been a major hurdle. This challenge has been so fundamental that many skeptics questioned whether practical quantum computers were even possible.

Hello, I am Willow

Previous quantum computers faced a cruel irony: while adding more qubits theoretically increased their computational power, it also made them more prone to errors. Each additional qubit increased the likelihood of the system losing its quantum properties through decoherence. It's like trying to build a house of cards in a room full of fans - the taller you build, the more likely everything is to collapse.

This is where Willow's breakthrough becomes truly revolutionary. For the first time, Google has demonstrated "below-threshold" error correction, meaning that as you add more physical qubits, the system becomes more reliable rather than less. Now, we can theoretically scale up quantum computers while simultaneously making them more stable. This doesn't just solve a technical problem - it proves that large-scale quantum computers are actually possible. As Sam Altman often says about transformative technologies: once you know something can be done, it becomes an engineering problem rather than a scientific one.

Why is below threshold so important?

While a classical computer can operate just fine in your pocket or backpack, quantum systems are disrupted by practically anything in their environment. Temperature fluctuations, electromagnetic fields, mechanical vibrations, cosmic rays, and even the simple act of observation can cause decoherence - the loss of quantum properties. This extreme sensitivity exists because quantum states like superposition and entanglement require perfect environmental isolation. It's similar to trying to balance a pencil on its tip - the slightest breeze or vibration will make it fall. This is why the images we often see of 'quantum computers' showing large octopus-like machines are somewhat misleading - those aren't actually the quantum computer itself, but rather the elaborate infrastructure needed to protect the qubits. Those massive structures contain the cooling systems (bringing temperatures close to absolute zero), magnetic shielding, vacuum chambers, and control electronics needed to isolate the actual quantum chip (which is typically smaller than a coin) from the chaotic outside world. While the quantum operations themselves are highly energy efficient, the overhead required to enable those operations makes current quantum computers massive energy consumers.

All that infrastructure is what protects the qubits from noise. The qubits fit in a chip no bigger than a credit card.

The Road Ahead

While Willow represents a significant breakthrough, the road to practical quantum computers still faces major hurdles. We need to scale up from today's hundreds of qubits to millions of reliable ones. Current coherence times - how long qubits maintain their quantum states - are measured in milliseconds, which limits the complexity of possible computations. And perhaps most importantly, we're still discovering what problems quantum computers are truly good at, with only a handful of practical quantum algorithms developed so far.

Yet the field's rapid progress is undeniable. The fact that industries are already implementing quantum-resistant cryptography shows we're not just theorizing about quantum computers - we're actively preparing for their arrival. The quantum future isn't a question of if, but when.

Old Veritasium prediction on when RSA will be broken. In orange the number of qubits needed to break RSA, in blue the available. Not about if, but when.

How else will QC change the world?

While cryptography and Shor's algorithm often dominate discussions about quantum computing (partly because of their dramatic security implications), the true potential of quantum computers extends far beyond breaking encryption. As breakthroughs like Willow's error correction bring us closer to reliable quantum systems, a whole new world of applications becomes possible. Let’s look at some nicer-than-cracking-your banking password applications

Optimization Problems

Quantum computers excel at solving certain types of optimization problems. The Quantum Approximate Optimization Algorithm (QAOA) can tackle complex logistics, portfolio management, and scheduling problems by exploring vast solution spaces simultaneously.

Graphical representation of QAOA - source

For example, imagine a supply chain problem with millions of possible configurations. A quantum computer could identify the optimal configuration far more efficiently than any classical method by leveraging superposition and interference.

Molecular Simulation

Simulating quantum systems (like complex molecules) is extremely difficult for classical computers - in fact, the computational requirements grow exponentially with each additional particle. Even modeling a relatively simple molecule with just 30 atoms quickly becomes intractable for our most powerful supercomputers. This is where quantum computers offer a fundamental advantage. Since they operate using the same quantum principles that govern molecules, they can naturally simulate these systems. While AI systems like AlphaFold have made remarkable progress in specific areas like protein structure prediction, quantum computers could revolutionize entire fields. In materials science, they could help design new superconductors that work at room temperature, more efficient solar panels, or better batteries for electric vehicles. In drug discovery, they could simulate how potential drug molecules interact with target proteins at the quantum level, dramatically accelerating the development of new treatments for diseases like cancer or Alzheimer's. The power of quantum simulation isn't just about speed - it's about being able to explore molecular interactions at a level of detail that's simply impossible with classical computers.

Conclusion

Let's be real - quantum computers aren't the magical 'does everything faster' machines that headlines make them out to be. They're weird, finicky beasts that need to be cooled to near absolute zero just to function, and we still barely understand what they'll be truly good at. But that's exactly what makes them fascinating.

While you won't be running Microsoft Excel on a quantum computer anytime soon (nor would you want to), they open up entirely new possibilities - from breaking the encryption that powers our digital world to simulating molecules in ways that could revolutionize drug discovery. Willow's breakthrough shows us that practical quantum computers aren't just a physicist's dream anymore - they're becoming an engineer's headache.

This post reflects my two-week descent into the quantum rabbit hole. Like most things quantum - and in life-, the more you learn, the weirder it gets. It was useful for me to get some intuition, but especially to learn how much I don’t know about this fascinating world.

Now, if you'll excuse me, I need to encrypt all my embarrassing teenage photos before these things become practical.

The most fascinating comprehensive representation by Dominic Wallman

Further Reading

More sources

[1] The Map of Quantum Computing

[2] How Quantum Computers Break The Internet... Starting Now

[3] Quanta Magazine: Quantum Computers Cross Critical Error Threshold

[4] My Quantum Computer Rabbit hole Youtube Playlist