11. Classical Logic: Boolean Algebra
Classical Logic: Boolean Algebra
You have established the mathematical framework. Now we must understand the fundamental computational constraints that force us to use quantum mechanics.
1. Boolean Algebra: The Classical Baseline
Boolean Algebra is the math of logic. It describes the relationship between discrete states represented by a bit: True (1) or False (0). The entire classical computer is built from simple, truth-table driven gates:
- AND ($A \land B$): Output is 1 only if both inputs are 1.
- OR ($A \lor B$): Output is 1 if either input is 1.
- NOT ($\neg A$): Flips the input.
- Bit values: True = 1, False = 0.
Classical logic gates and their truth tables.
2. The Problem: Irreversibility
Most classical gates, such as AND and OR, are irreversible. This means you cannot uniquely determine the input from the output. When a gate is irreversible, it loses information. This lost information is linked to thermodynamic entropy, and for every bit of information lost, the operation must dissipate energy (Landauer's Principle).
Quantum computing is based on unitary operations (matrices that conserve probability/vector length), and all unitary operations are mathematically reversible. To create a quantum algorithm, we must use logic that is also reversible.
3. The Bridge: Reversible Logic
In quantum circuits, gates are constructed such that the input state can always be recovered from the output state. They do not lose information.
For example, the Pauli-X gate (Quantum NOT) is reversible: if you apply it twice, you get back to the original state ($X^2 = I$). All quantum gates must be part of a reversible system.