How Quantum Computers Execute Algorithms

1. The Classical Simulation Barrier

In 1981, at a joint conference hosted by MIT and IBM, physicist Richard Feynman posed a deceptively simple question: Can classical computers simulate the physical universe?

His answer was an unequivocal no.

When classical computers attempt to simulate the behavior of even a modest molecular system—such as the nitrogenase enzyme that fixes atmospheric nitrogen, or the electron orbitals in a high-temperature superconductor—they hit an impenetrable mathematical wall.

Consider a physical system composed of N interacting quantum particles (such as electrons with spin-up and spin-down orientations). In classical physics, if you have N coins, their complete physical state can be described with exactly N bits of information (each coin is either heads or tails, 0 or 1).

In quantum mechanics, however, the system does not reside in a single discrete state. Due to the principle of quantum superposition and entanglement, the system exists as a continuous linear combination across all 2^N possible configurations simultaneously:

Where each c_k is a complex number (c_k = a_k + i b_k) representing the probability amplitude of that configuration.

+---------------------------------------------------------------------------------------+
|                       THE EXPONENTIAL STATE SPACE EXPLOSION                           |
+---------------------------------------------------------------------------------------+
|  Qubits (N)   | Configurations (2^N) | Classical RAM Required to Store State Vector   |
|  10           | 1,024                | 16 Kilobytes                                   |
|  20           | 1,048,576            | 16 Megabytes                                   |
|  30           | 1,073,741,824        | 16 Gigabytes (High-end laptop)                 |
|  40           | 1.099 x 10^12        | 16 Terabytes (Enterprise server rack)          |
|  50           | 1.125 x 10^15        | 16 Petabytes (World-class supercomputer)       |
|  100          | 1.267 x 10^30        | Exceeds all digital storage media on Earth     |
|  300          | 2.037 x 10^90        | Exceeds the total number of atoms in universe  |
+---------------------------------------------------------------------------------------+

To store the exact quantum state of just 50 entangled particles using standard double-precision floating-point numbers requires 16 petabytes of RAM. To store the state of 300 particles requires more numbers than there are elementary particles in the observable universe (10⁸⁰).

Classical supercomputers do not fail because their processors are too slow; they fail because the mathematical language of classical physics (scalar bits and deterministic state transitions) is dimensionally insufficient to describe the geometry of quantum reality.

As Feynman famously observed:

"Nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical!"

A quantum computer is not a classical supercomputer running at hyper-speed. It is a completely distinct computational paradigm. Instead of using electrical voltages to represent 0s and 1s, it uses physical quantum objects—superconducting aluminum circuits, trapped atomic ions, or individual photons—and manipulates their wavefunctions using the laws of quantum mechanics.

---

2. The Qubit: Geometry of the Bloch Sphere

In classical computing, as established in How a CPU Executes an Instruction and How CMOS Transistors Form Logic Gates, the fundamental unit of information is the bit. A bit is a physical switch: a transistor channel is either conducting (high voltage, logical 1) or non-conducting (low voltage, logical 0). It is binary, discrete, and deterministic:

In quantum computing, the fundamental primitive is the quantum bit, or qubit. A qubit is a two-level quantum mechanical system.

By convention, the two basis states are written using Paul Dirac's bra-ket notation:

• |0⟩ = (10) (the ground or computational zero state)
• |1⟩ = (01) (the excited or computational one state)

A qubit does not have to be strictly in state |0⟩ or strictly in state |1⟩. It can exist in a superposition of both states:

Where α and β are complex numbers called probability amplitudes.

The Born Rule and Normalization

Probability amplitudes are not physical probabilities; they are complex wave numbers. To obtain a real, physical probability, we invoke Max Born's foundational postulate—the Born Rule:

The probability of measuring the qubit in state |0⟩ is the squared magnitude of its amplitude:

The probability of measuring the qubit in state |1⟩ is:

Because a measurement must yield either a 0 or a 1, the total probability must equal 100%:

Visualizing the Qubit: The Bloch Sphere

Because α and β are complex numbers, they contain four real parameters (two real parts and two imaginary parts). The normalization condition |α|² + |β|² = 1 removes one degree of freedom. Furthermore, in quantum mechanics, an overall global phase factor (e^iγ) has no observable physical effect, removing a second degree of freedom.

This leaves exactly two independent real parameters, allowing any pure single-qubit state to be mapped onto the surface of a three-dimensional unit sphere known as the Bloch Sphere:

Where:

• θ ∈ [0, π] represents the polar angle (latitude on the sphere).
• φ ∈ [0, 2π) represents the azimuthal angle (longitude on the sphere), defining the relative phase.

                           THE BLOCH SPHERE
                           
                                |0> (North Pole: theta = 0)
                                 ^
                                 |
                                 |  /  |+> = (|0> + |1>)/sqrt(2)
                                 | /       (theta = pi/2, phi = 0)
                         +-------|-------+
                        /        |        /
                       /         |       /
                      +----------+------+ ---> Y
                     /           |     /
                    /            |    /
                   +-------------+---+
                                 |
                                 v
                                |1> (South Pole: theta = pi)

Look at the extraordinary geometric richness of this sphere:

• North Pole (θ = 0): The classical state |0⟩.
• South Pole (θ = π): The classical state |1⟩.
• The Equator (θ = π/2): States of equal probability (50% chance of 0, 50% chance of 1).
  • On the +X axis (φ = 0): The state |+⟩ = 1√2(|0⟩ + |1⟩).
  • On the −X axis (φ = π): The state |−⟩ = 1√2(|0⟩ − |1⟩).
  • On the +Y axis (φ = π/2): The state |+i⟩ = 1√2(|0⟩ + i|1⟩).

Notice the crucial difference between |+⟩ and |−⟩. Both states have the exact same physical measurement probability (50% 0, 50% 1). Yet they are physically orthogonal states pointing in opposite directions on the Bloch sphere! The difference lies entirely in their relative phase (φ = 0 vs φ = π).

As we will see, it is this relative phase that powers quantum interference.

---

3. Quantum Logic Gates as Unitary Rotations

In a classical microprocessor, computation consists of passing voltages through Boolean logic gates (AND, OR, NOT, NAND).

In a quantum computer, computation consists of rotating the state vector around the Bloch sphere.

Because total probability must be preserved at every step (|α|² + |β|² = 1), any valid quantum operation must be a linear transformation that preserves vector lengths in Hilbert space. In linear algebra, such transformations are represented by Unitary Matrices (U):

Where U^† is the conjugate transpose (Hermitian adjoint) of U.

A critical physical consequence of unitarity is that all quantum logic gates are inherently reversible: you can always run a quantum gate backward by applying its adjoint U^†. (Unlike classical NAND gates, which discard input information and dissipate heat according to Landauer's principle).

Let us examine the foundational single-qubit quantum gates:

The Pauli-X Gate (Quantum NOT)

The Pauli-X gate represents a 180^∘ (π radians) rotation around the X-axis of the Bloch sphere:

Applying X flips the basis states:

The Pauli-Z Gate (Phase Flip)

The Pauli-Z gate rotates the state vector by 180^∘ around the Z-axis:

Applying Z leaves |0⟩ untouched, but flips the phase of |1⟩:

Notice what happens when Z is applied to the equatorial superposition state |+⟩:

The Pauli-Z gate swung the state vector from the front of the sphere to the back!

The Hadamard Gate (H): The Gateway to Superposition

The single most celebrated gate in quantum algorithms is the Hadamard Gate. It performs a 90^∘ rotation around the Y-axis followed by a 180^∘ rotation around the X-axis:

When applied to the pure classical state |0⟩, the Hadamard gate creates an equal superposition:

When applied to state |1⟩:

Because H is unitary and Hermitian (H = H^† = H⁻¹), applying it a second time reverses the operation:

---

4. Multi-Qubit Systems and Quantum Entanglement

When we combine multiple qubits, their collective state is formed by the Kronecker tensor product (⊗) of their individual vector spaces.

For a two-qubit system, the four computational basis states are:

A general two-qubit state is:

With ∑ |c_ij|² = 1.

The Controlled-NOT (CNOT) Gate

To perform meaningful computation, qubits must interact. The primary two-qubit entangling gate is the Controlled-NOT (CNOT) gate:

The CNOT gate acts on two qubits: a Control Qubit (|c⟩) and a Target Qubit (|t⟩):

• If the control qubit is |0⟩, the target qubit is left unchanged.
• If the control qubit is |1⟩, the target qubit is flipped (X applied).

Control: |c> ────────■──────── |c>
                     │
Target:  |t> ───────(+)─────── |c ⊕ t>

Forging an Entangled Bell State

Watch what happens when we combine a Hadamard gate and a CNOT gate in sequence:

1. Start with both qubits in the ground state:

2. Apply a Hadamard gate to Qubit 1:

3. Apply a CNOT gate with Qubit 1 as control and Qubit 2 as target:
   • The term |00⟩ has control |0⟩, so target remains |0⟩ → |00⟩.
   • The term |10⟩ has control |1⟩, so target flips to |1⟩ → |11⟩.

This resulting state |Ψ⁺⟩ is one of the four Bell States.

Notice something profound: This state cannot be factored back into individual qubit states!

The two qubits are now entangled. Neither qubit has a definite state of its own. If you measure Qubit 1 and observe a 0, the wavefunction collapses instantaneously, and Qubit 2 will measure 0 with 100% certainty—even if the two qubits are separated across light-years.

---

5. The Fatal Fallacy: Why "Parallel Universe" Computing is a Myth

At this point, many popular science accounts present a seductive, fundamentally flawed explanation:

"A classical computer tests combinations one at a time. A quantum computer with 50 qubits tries all 2⁵⁰ combinations in parallel! It explores every path at once and instantly picks the best one."

This explanation is not merely an oversimplification; it completely misses the physical reality of quantum mechanics.

Suppose you create an equal superposition across all N-bit numbers using N Hadamard gates:

And suppose you compute some complex function f(x) into an output register:

It is true that the mathematical state vector now contains the evaluation of f(x) for all 2^N inputs.

However, you cannot read the state vector directly!

To extract information from a quantum computer, you must perform a physical measurement. According to the Born rule, the moment you measure the register, the entire superposition collapses into a single random output state |x_k⟩ |f(x_k)⟩ with probability:

You do not get all 2^N answers. You get one single random answer!

If quantum algorithms relied on pure superposition, a quantum computer would be completely useless: running the algorithm would be mathematically equivalent to picking a random number out of a hat. A classical computer guessing randomly would achieve the exact same performance.

The True Secret: Quantum Interference

If quantum computing is not massive parallel guessing, how does it achieve exponential speedups?

The answer is Interference.

In quantum mechanics, probability amplitudes (c_k) are complex numbers that have both a magnitude and a phase:

When multiple computational paths lead to the same final state, their amplitudes add together like physical waves:

• Constructive Interference: If two paths arrive with the same phase (φ₁ ≈ φ₂), their wave crests reinforce each other:

• Destructive Interference: If two paths arrive out of phase (φ₁ = φ₂ + π), their amplitudes have opposite signs:

+---------------------------------------------------------------------------------------+
|                       THE CORE MECHANISM OF QUANTUM ALGORITHMS                        |
+---------------------------------------------------------------------------------------+
|  1. Initialize all qubits into equal superposition.                                   |
|  2. Encode the problem into a unitary transformation (an Oracle).                     |
|  3. The Oracle flips the PHASES of wrong answers relative to correct answers.         |
|  4. Apply an interference transformation (e.g. Hadamard or Quantum Fourier Transform).|
|  5. DESTRUCTIVE INTERFERENCE: Bad answers cancel out to zero amplitude.               |
|  6. CONSTRUCTIVE INTERFERENCE: Correct answer reinforces to ~100% probability.        |
|  7. Measure: The wavefunction collapses to the correct answer with high certainty!   |
+---------------------------------------------------------------------------------------+

A quantum algorithm is not a search across parallel universes; it is an orchestrated symphony of wave interference. The entire craft of quantum algorithm design consists of choreographing unitary matrix rotations such that incorrect answers cancel each other out through destructive interference, while the single correct answer concentrates virtually all the probability amplitude onto itself.

---

6. The End-to-End Quantum Execution Cycle

Let us trace how a real-world quantum algorithm executes from classical compiler to physical dilution refrigerator:

Let us inspect the physical engineering occurring at each tier:

1. The Classical Host and Circuit Compilation

A quantum algorithm is written in high-level programming frameworks (such as Qiskit, Cirq, or PennyLane). The compiler takes abstract mathematical unitary gates (H, X, Z, CNOT) and decomposes them into the native gate set supported by the physical hardware.

For a superconducting quantum processor, the native single-qubit gates are typically continuous microwave rotations around the X and Y axes (R_x(θ), R_y(θ)), while two-qubit gates are realized via cross-resonance pulses or tunable capacitive couplers (CZ or iSWAP gates).

2. The Cryogenic Hardware Stack

The physical Quantum Processing Unit (QPU) resides at the bottom plate of a dilution refrigerator cooled by a mixture of Helium-3 and Helium-4 isotopes to approximately 15 millikelvin (−273.135^∘C)—colder than deep interstellar space (2.7 K).

Why is extreme cold necessary? At room temperature, ambient thermal energy is:

The energy gap between the |0⟩ and |1⟩ states of a superconducting qubit oscillating at 5.0 GHz is governed by Planck's constant (h):

At room temperature, thermal noise is 1,000 times larger than the qubit energy gap! Thermal photons would instantly shake the qubit out of its delicate quantum state. At 15 millikelvin, however, thermal energy drops well below Δ E, freezing out stray thermal excitations.

               THE CRYOGENIC TEMPERATURE TIERS
               
     Room Temp (300 K)  ──► Classical Control Electronics & AWGs
            │
            ▼ (50 K Plate)
            │
            ▼ (4 Kelvin Plate) ──► Pulse Attenuators & Cryo-amplifiers
            │
            ▼ (0.8 Kelvin Still)
            │
            ▼ (100 mK Cold Plate)
            │
            ▼ (15 Millikelvin Base Plate) ──► QPU (Superconducting Chip)

3. The Control Layer: Microwave Pulses

There are no physical wires carrying logical 1s and 0s inside the QPU. Instead, the Arbitrary Waveform Generator (AWG) synthesizes precisely calibrated microwave pulses at microwave frequencies (4.0 to 8.0 GHz) shaped with Gaussian envelopes:

• A microwave pulse resonant with the qubit's transition frequency lasting for a duration of 20 nanoseconds rotates the state vector by exactly 90^∘ (creating a Hadamard-equivalent superposition).
• Changing the microwave carrier phase shifts the axis of rotation from X to Y.
• A pulse with twice the duration (40 ns) rotates the vector by 180^∘ (executing a Pauli-X gate).

4. Readout and Measurement

To measure the final state, a microwave tone is sent down a transmission line coupled to a dedicated readout resonator adjacent to each qubit.

Due to the dispersive interaction between the qubit and the resonator, the resonant frequency of the cavity shifts slightly depending on whether the qubit is in state |0⟩ or state |1⟩:

When the readout pulse reflects off the cavity, its phase and amplitude are altered by this frequency shift. The reflected signal passes through a High Electron Mobility Transistor (HEMT) cryogenic amplifier, travels up the refrigerator, and is demodulated by an analog-to-digital converter at room temperature. The host computer classifies the resulting IQ signal to output a classical bit: 0 or 1.

---

7. Case Study: Shor's Algorithm and the Fall of RSA

The power of quantum interference is demonstrated most dramatically by Shor's Factoring Algorithm, discovered by Peter Shor at Bell Labs in 1994.

Modern global telecommunications, banking security, and internet encryption (RSA public-key cryptography, as detailed in How Public Key Cryptography Works) rely on a single empirical assumption: Multiplying two large prime numbers p and q to produce N = p · q is easy, but factoring N back into p and q is practically impossible.

For a 2048-bit RSA modulus, the best known classical algorithm—the General Number Field Sieve (GNFS)—requires sub-exponential time:

Factoring a 2048-bit number classically would take millions of years of aggregate compute time across all supercomputers on Earth.

Shor's algorithm factors N in polynomial time:

On a fault-tolerant quantum computer, factoring a 2048-bit RSA key takes hours.

How Shor's Algorithm Works: Reduction to Period Finding

Peter Shor made a brilliant mathematical connection: Factoring an integer can be reduced to finding the period of a periodic mathematical function.

By Euler's totient theorem, if you pick a random integer a coprime to N (1 < a < N and gcd(a, N) = 1), the sequence generated by modular exponentiation:

is strictly periodic! That is, there exists an integer r (called the period or order) such that:

If we can find this period r, and if r is an even number, we can rewrite the equation:

This means that the product (a^r/2 − 1)(a^r/2 + 1) is an exact multiple of N = p · q. Unless a^r/2 ≡ −1 pmod N, the factors p and q must be shared between these two terms!

We can then compute the greatest common divisor using Euclid's classical algorithm in microseconds:

The factoring problem is solved!

               SHOR'S PERIOD-FINDING CONVERSION
               
    RSA Challenge: Factor N = 15. Pick random a = 7.
    
    x  | a^x mod 15
    ---+-----------
    0  | 7^0 mod 15 = 1
    1  | 7^1 mod 15 = 7
    2  | 7^2 mod 15 = 49 mod 15 = 4
    3  | 7^3 mod 15 = 343 mod 15 = 13
    4  | 7^4 mod 15 = 2401 mod 15 = 1   <--- REPEATS!
    5  | 7^5 mod 15 = 7
    
    --> The period is r = 4.
    --> a^(r/2) = 7^(4/2) = 7^2 = 49.
    --> Factor 1 = gcd(49 - 1, 15) = gcd(48, 15) = 3!
    --> Factor 2 = gcd(49 + 1, 15) = gcd(50, 15) = 5!

Why Classical Computers Cannot Find the Period

Classically, to find the period r of a^x pmod N for a 2048-bit number, the period r can be as large as 10⁶⁰⁰. A classical computer would have to evaluate a^x pmod N an exponential number of times.

The Quantum Fourier Transform (QFT) Solution

Shor's algorithm finds the period in a single quantum circuit:

In Step 4, the Inverse Quantum Fourier Transform performs an exponential Fourier transform across the state space using only O(n²) quantum gates.

Just like an optical diffraction grating causes light waves to interfere destructively everywhere except at sharp, constructive interference peaks corresponding to the grating spacing, the QFT causes all non-periodic probability amplitudes to cancel out to zero. The wave peaks reinforce strictly at integer multiples of the fundamental frequency:

Measuring the register yields k. A classical host running the continued fractions algorithm extracts r in milliseconds, shattering the cryptographic security of the underlying key.

---

8. The Decoherence Problem and Quantum Error Correction

If quantum algorithms offer such profound mathematical speedups, why aren't quantum computers running in every data center today?

The answer is Decoherence.

A classical silicon transistor is robust: a bit 1 contains approximately 10,000 to 50,000 conduction electrons. If three stray electrons leak away due to thermal fluctuations, the voltage remains high, and the bit is unaffected.

A qubit, by contrast, is an individual quantum state. It is infinitely sensitive to its surrounding environment. Stray electromagnetic radiation, microscopic vibrations from cryogenic pumps, material impurities in the silicon substrate, and cosmic rays constantly interact with the qubit, destroying its quantum phase:

1. Energy Relaxation Time (T₁): The time it takes for an excited state |1⟩ to decay down to the ground state |0⟩, losing its energy to the substrate. In state-of-the-art superconducting qubits, T₁ ≈ 50 to 300 microseconds.
2. Dephasing Time (T₂): The time it takes for the relative phase angle φ on the Bloch sphere to randomize due to magnetic field fluctuations. Typically, T₂ ≤ 2 T₁.

When a qubit dephases, the relative phase differences that make destructive interference possible are erased. The quantum computer degenerates into a noisy classical random number generator.

+---------------------------------------------------------------------------------------+
|                              THE DECOHERENCE TIME LIMIT                               |
+---------------------------------------------------------------------------------------+
|  Gate Execution Time (Microwave Pulse) : ~20 to 50 Nanoseconds                        |
|  Qubit Coherence Lifespan (T1, T2)     : ~100 to 200 Microseconds                     |
|                                                                                       |
|  --> Maximum Circuit Depth             : ~2,000 to 5,000 Gates before state decay.    |
+---------------------------------------------------------------------------------------+

Quantum Error Correction (QEC)

In classical computing, error correction is simple: if you fear bit flips, you can use triple modular redundancy (copy bit b into b b b; if one flips to 0 1 0, take the majority vote).

In quantum computing, this is strictly forbidden by the No-Cloning Theorem (Wootters, Zurek, and Dieks, 1982): It is physically impossible to create an identical copy of an arbitrary unknown quantum state.

Furthermore, you cannot measure the physical qubits to see if an error occurred, because measuring them would collapse the superposition!

To solve this apparent paradox, physicists invented Topological Surface Codes.

Instead of copying states, surface codes entangle a single "Logical Qubit" across an array of hundreds or thousands of "Physical Data Qubits" and "Syndrome Ancilla Qubits":

                  THE 2D SURFACE CODE LATTICE
                  
                 D ────── S_z ────── D
                 │         │         │
                S_x ────── D ────── S_x
                 │         │         │
                 D ────── S_z ────── D
                 
     D   = Physical Data Qubits (Store the entangled logical state)
     S_z = Z-Syndrome Ancilla Qubits (Detect X bit-flip errors)
     S_x = X-Syndrome Ancilla Qubits (Detect Z phase-flip errors)

The ancilla qubits are coupled to neighboring data qubits and measured millions of times per second. Crucially, the ancilla measurements do not measure the data qubits directly; they measure the parity (eigenvalue of the Pauli operators) between adjacent data qubits.

This reveals the error syndrome (whether an error occurred and where it is located) without revealing any information about the stored quantum data itself. A classical decoder running in real time tracks the errors and applies corrective software adjustments.

To build a fault-tolerant quantum computer capable of running Shor's algorithm on 2048-bit numbers will require approximately 2,000 to 4,000 logical qubits—which, at current physical error rates (10⁻³), translates to a physical machine containing between 1 million and 4 million physical superconducting qubits.

---

9. Architectural Comparison: Classical vs. Quantum Computing

To synthesize our understanding, we can contrast the physical and algorithmic paradigms across both computational universes:

Architectural Dimension	Classical Digital Computing	Quantum Computing
Fundamental Information Unit	Classical Bit: b ∈ {0, 1}	Quantum Bit (Qubit): |ψ⟩ = α |0⟩ + β |1⟩
State Space Scaling	Linear: N bits store N binary values	Exponential: N qubits span 2N-dimensional Hilbert space
Fundamental Operators	Irreversible Boolean logic gates (NAND, NOR, AND)	Reversible Unitary matrix rotations (H, X, Z, CNOT)
Primary Computational Engine	Deterministic electric potential transitions	Constructive and Destructive Wave Interference
Measurement Behavior	Non-destructive; read-state is deterministic	Wavefunction collapse governed by Born Rule (P = |ck|2)
Copying Information	Trivial (infinite fan-out and copying)	Impossible (forbidden by No-Cloning Theorem)
Operating Environment	Room temperature (300 K) silicon chip	Cryogenic Dilution Refrigerator (15 millikelvin) or ultra-high vacuum
Algorithmic Advantage	Superior for serial, branching, deterministic tasks	Exponential speedups for Period Finding, Simulation, Optimization

---

10. Summary: The Physics of Information

For over a century, computer science treated information as an abstract mathematical entity, decoupled from the underlying laws of physical reality. Alan Turing, Claude Shannon, and John von Neumann formulated their theories assuming that computation was fundamentally an exercise in discrete symbolic manipulation.

Quantum computing revealed that this assumption was incomplete.

                    THE QUANTUM COMPUTING EQUATION
+-------------------------------------------------------------------+
|  Quantum Advantage  =  Exponential Hilbert State Vector          |
|                        x Unitary Reversible Gate Rotations        |
|                        x Destructive Cancellation of Errors       |
|                        x Constructive Reinforcement of Truth      |
+-------------------------------------------------------------------+

Information is not abstract. Information is physical. The universe does not compute with binary bits; it computes with quantum probability amplitudes, continuous relative phases, and non-local entanglement.

A quantum computer does not achieve its power by brute-force parallel calculation. It achieves its power by turning a mathematical problem into a physical wave interference experiment. By aligning the geometry of an algorithm with the fundamental quantum architecture of nature itself, it solves problems that would remain forever unyielding to all the classical silicon chips that could ever be manufactured in our universe.