12. Classical Logic: Logic Gates
Classical Logic: Logic Gates
You established why standard classical gates fail in a quantum system (information loss/irreversibility). Now, we look at the specific gates that serve as the direct mathematical blueprint for quantum circuits.
Goal: Use logic gates that take N inputs and produce N outputs, where the input can always be uniquely determined from the output.
1. The Controlled-NOT (CNOT)
The Controlled-NOT (CNOT) gate is the most fundamental two-bit reversible gate. It is the direct precursor to its quantum counterpart.
| Control (A) | Target (B) | Output (A') | Output (B') |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 |
Rule: The Control bit remains unchanged (A' = A). The Target bit is flipped only if the Control bit is 1 (B' = B ⊕ A, where ⊕ is XOR).
Significance: Because the CNOT preserves the control bit and the operation on the target depends deterministically on the control, you can perfectly reverse this operation.
2. Universal Reversible Logic
A set of gates is universal if any logical function can be built using only those gates. Classical irreversible sets are universal (e.g., NAND alone or NOR alone). For reversible logic, we need more complex gates to achieve universality:
- Toffoli (CCNOT): A 3-bit gate (2 controls, 1 target). It flips the target only if both control bits are 1. The Toffoli gate alone is universal for all classical reversible computation.
- Fredkin (CSWAP): A 3-bit gate that swaps two target bits only if the control bit is 1.
The CNOT and Toffoli are crucial because they demonstrate that reversible logic is sufficient to perform any classical computation, and they are the two most important multi-qubit gates in any quantum circuit.