Classical Computing Recap¶
Time: 25 minutes | Difficulty: 🟢 Beginner
Overview¶
Before we dive into the quantum world, let's make sure we understand classical computing. Quantum computing builds on these foundations - and understanding the classical approach helps us appreciate why quantum is revolutionary.
Think of this as a quick refresher: bits, gates, circuits, and algorithms. If you've ever programmed a computer, you already know most of this intuitively!
The Classical Bit: The Foundation¶
What is a Bit?¶
A bit (binary digit) is the smallest unit of information in classical computing.
It has exactly two possible values:
- 0 (off, false, low voltage)
- 1 (on, true, high voltage)
Physical Implementation: - Transistor: High voltage = 1, low voltage = 0 - Hard drive: Magnetic direction (north/south) - CD/DVD: Pit or land on the surface - RAM: Capacitor charged (1) or discharged (0)
Why Binary?¶
Why do computers use binary instead of decimal (0-9)?
Engineering simplicity: - Easy to distinguish two states (on/off) - Reliable: Small voltage fluctuations don't cause errors - Fast: Quick switching between two states
Analogy: It's easier to build a reliable light switch (on/off) than a reliable dimmer with 10 precise brightness levels.
Representing Information¶
Everything in a computer is ultimately bits:
Number 5: 0000 0101
Letter 'A': 0100 0001
Color red: 1111 1111 0000 0000 0000 0000 (RGB)
This text: Thousands of bits
Key Insight: With enough bits, you can represent anything - numbers, text, images, videos, even quantum states!
Classical Gates: The Building Blocks¶
Logic Gates¶
Logic gates are the fundamental operations that manipulate bits. They're the "atoms" of classical computation.
Basic Gates¶
1. NOT Gate (Inverter)
Flips the bit. Simple!2. AND Gate
Output is 1 only if both inputs are 1.Analogy: Two switches in series - light only turns on if both switches are on.
3. OR Gate
Output is 1 if either input is 1.Analogy: Two switches in parallel - light turns on if either switch is on.
4. XOR Gate (Exclusive OR)
Output is 1 if inputs are different.Use case: This is how computers add binary numbers!
Universal Gates¶
NAND Gate (NOT-AND)
Amazing fact: You can build ANY logical operation using only NAND gates! This is called functional completeness.
Why it matters: Chip manufacturers can focus on making really good NAND gates, then combine them to do anything.
From Gates to Computation¶
Addition Example:
Adding two bits: A + B
- Sum = A XOR B
- Carry = A AND B
This simple circuit, called a half adder, is the basis for all arithmetic in computers!
Classical Circuits: Combining Gates¶
What is a Circuit?¶
A circuit is a collection of gates connected together to perform a more complex operation.
Simple Example: Full Adder¶
A full adder adds three bits: A, B, and a carry-in.
Inputs: A, B, Carry-In
Outputs: Sum, Carry-Out
Implementation:
- Use two half adders
- Use one OR gate
- Total: 5 gates
Why it matters: Chain 32 full adders together, and you can add 32-bit numbers. That's how your CPU does arithmetic!
Circuit Properties¶
1. Deterministic - Same input → Always same output - No randomness (ignoring hardware errors)
2. Irreversible (usually) - AND gate: (0,1) → 0 and (0,0) → 0 - Given output 0, you can't determine the original input - Information is lost
3. Sequential Composition - Output of one gate becomes input to another - Build complex operations from simple parts
Modern Processors¶
Intel Core i9 (example): - ~10 billion transistors - Organized into billions of logic gates - Organized into functional units: - Arithmetic Logic Unit (ALU) - Control Unit - Memory - Cache
All built from simple gates!
Classical Algorithms: Solving Problems¶
What is an Algorithm?¶
An algorithm is a step-by-step procedure to solve a problem.
Recipe analogy:
Making toast:
1. Take bread slice
2. Put in toaster
3. Set timer to 2 minutes
4. Press start
5. Wait for pop
6. Remove toast
Algorithm Complexity¶
Not all algorithms are created equal. We measure them by how they scale with input size.
Time Complexity¶
How long does it take?
Constant Time: O(1)
Linear Time: O(n)
def find_max(array):
max_val = array[0]
for item in array: # Check each element once
if item > max_val:
max_val = item
return max_val
Quadratic Time: O(n²)
def bubble_sort(array):
for i in range(len(array)):
for j in range(len(array)): # Nested loop!
# Compare and swap
Exponential Time: O(2ⁿ)
Time doubles when you add just one element!The Wall: Intractable Problems¶
Some problems have no known efficient (polynomial time) classical algorithms:
1. Traveling Salesman (TSP) - Problem: Find shortest route through n cities - Classical: O(n!) - factorial time - 20 cities: ~2.4 × 10¹⁸ operations - 25 cities: ~15 × 10²⁴ operations (universe age worth of computation!)
2. Integer Factorization - Problem: Find prime factors of large number - Classical: Exponential time for general case - Use case: RSA encryption relies on this being hard!
3. Database Search (Unstructured) - Problem: Find item in unsorted database - Classical: O(n) - must check each item - Quantum: O(√n) with Grover's algorithm!
Classical Computing Strengths¶
What Classical Computers Do Best¶
1. Precise, Deterministic Tasks - Accounting, word processing, databases - When you need exact answers
2. Sequential Logic - Following complex rules - Control flow (if/then/else)
3. Random Access Memory - Quick access to any data - Efficient data structures
4. Stability - Results are reproducible - No need for extreme cooling - Mature technology
Real-World Performance¶
Modern Classical Supercomputers:
Frontier (USA, 2023): - 1.2 exaFLOPS (1.2 × 10¹⁸ operations/second) - 9.2 million CPU cores - 21 megawatts power consumption - Size of a basketball court
Impressive! But... - Still can't simulate 100 quantum particles - Still can't factor large numbers efficiently - Still can't solve many optimization problems
Classical Computing Limitations¶
Fundamental Limits¶
1. Physical Limits
Transistor Size:
When transistors get too small, electrons "tunnel" through barriers.Speed Limits:
2. Energy Limits
Landauer's Principle: - Erasing one bit generates minimum heat: kT ln(2) - At room temperature: ~3 × 10⁻²¹ joules per bit - Sounds small, but multiplied by billions of operations per second...
Modern CPU: - ~100 watts power consumption - Most becomes heat - Requires active cooling
3. Algorithmic Limits
Some problems are fundamentally hard: - No classical algorithm can solve them efficiently - Adding more transistors doesn't help - This is where quantum computing enters!
The Memory Wall¶
Simulating Quantum Systems:
To classically simulate n qubits: - Need 2ⁿ complex numbers - Each complex number: ~16 bytes
20 qubits: ~16 MB (easy)
30 qubits: ~16 GB (manageable)
40 qubits: ~16 TB (very expensive)
50 qubits: ~16 PB (world's largest supercomputers)
60 qubits: ~16 EB (more than all of Earth's data)
300 qubits: More numbers than atoms in universe
This is why we need quantum computers to understand quantum systems!
Key Differences: Classical vs Quantum (Preview)¶
| Aspect | Classical | Quantum |
|---|---|---|
| Basic unit | Bit (0 or 1) | Qubit (0 and 1 simultaneously) |
| State | Definite | Probabilistic superposition |
| Operations | Logic gates | Quantum gates |
| Correlation | Independent or classically correlated | Entangled |
| Measurement | Read value without changing it | Measurement changes the state |
| Copying | Easy (copy/paste) | Impossible (no-cloning theorem) |
| Reversibility | Usually irreversible | All gates reversible |
| Scaling | Linear (n bits → n separate values) | Exponential (n qubits → 2ⁿ amplitudes) |
Don't worry if quantum concepts seem strange - that's what the rest of this course is for!
Summary: Why This Matters¶
Understanding classical computing gives us:
1. Appreciation for Quantum Advantage - Quantum isn't just "faster classical" - It's a fundamentally different computational model
2. Hybrid Thinking - Most practical quantum algorithms use both classical and quantum - Classical computers control quantum computers
3. Problem Recognition - Which problems benefit from quantum? - When is classical still the best choice?
4. Common Language - Many quantum concepts have classical analogs - Gates, circuits, algorithms
Key Takeaways¶
- Bits are the foundation of classical computing (0 or 1)
- Logic gates (AND, OR, NOT, etc.) manipulate bits
- Circuits combine gates to perform complex operations
- Algorithms have different scaling behavior (O notation)
- Fundamental limits exist for classical computers
- Physical: transistor size, speed, heat
- Algorithmic: some problems are inherently hard
- Quantum computing offers a different approach for specific problems
Check Your Understanding¶
Question 1: What makes NAND gates special?
Answer
NAND gates are **functionally complete** - you can build any logical operation using only NAND gates. This makes chip manufacturing simpler.Question 2: Why can't classical computers efficiently simulate 100 qubits?
Answer
To simulate n qubits classically requires tracking 2ⁿ complex numbers. For 100 qubits, that's 2¹⁰⁰ ≈ 10³⁰ numbers - far more than any classical computer can store in memory.Question 3: What's the difference between O(n) and O(2ⁿ)?
Answer
- **O(n)** is linear: double input size → double time - **O(2ⁿ)** is exponential: add one to input size → double time Exponential algorithms become intractable very quickly!Question 4: If you chain 8 full adders together, what size numbers can you add?
Answer
8-bit numbers (0 to 255). Each full adder handles one bit position.What's Next?¶
Now that we understand how classical computers work, we're ready to explore the quantum world:
Next: Quantum Mechanics Basics - Wave-particle duality - Superposition principle - Quantum measurement - The foundations of quantum computing
Related: - Why Quantum Computing? - Problems classical computers struggle with - The Qubit - The quantum analog of the bit
Additional Resources¶
Books: - Code by Charles Petzold - Beautiful explanation of how computers work from first principles - The Elements of Computing Systems by Nisan & Schocken - Build a computer from NAND gates up
Online: - Nand2Tetris - Build a computer from scratch - Ben Eater's YouTube - Building computers on breadboards - Crash Course Computer Science
Interactive: - Logic.ly - Visual logic gate simulator - Digital - Circuit simulation tool
💡 Pro Tip: The best way to understand classical computing is to build something! Try implementing a half-adder in your favorite programming language, or play with a logic gate simulator.
Ready to enter the quantum realm? Let's go! 🚀