Advanced Quantum Computing

# qc Knowledge Pack

## Fundamentals of qc
Unlike class comp which uses bits (0 or 1), qc uses quantum bits (qbs). A qb can represent 0, 1, or both simultaneously due to quantum phenomena, enabling qc to solve certain complex problems exponentially faster than class supercomputers.

### sup
The principle that a qb exists in a linear combination of states until meas. 
- Mathematically represented as `|ψ⟩ = α|0⟩ + β|1⟩`, where α and β are complex prob amps. The sum of their absolute squares (`|α|^2 + |β|^2`) must equal 1.
- Upon meas, the qb's state collapses to either 0 (with prob `|α|^2`) or 1 (with prob `|β|^2`).
- Crucially, sup allows a qc with N qbs to represent `2^N` states simultaneously. A 300-qb sys can represent more states than there are atoms in the observable universe.

### ent
A quantum phenomenon where two or more qbs become fundamentally linked. 
- If two qbs are entangled, measuring the state of one instantaneously determines the state of the other, regardless of the physical distance between them (Einstein's "spooky action at a distance").
- This allows qbs to share information instantly and serves as the backbone for quantum teleportation and exponential computational speedups.

### int
Quantum amps are complex numbers and can exhibit int. 
- **Constructive int**: Correct answers have their prob amps amplified.
- **Destructive int**: Incorrect answers have their prob amps cancel each other out.
- The goal of every quantum alg is to choreograph the gates so that the wrong answers destructively interfere (approaching 0 prob) and the correct answer constructively interferes (approaching 100% prob) before meas.

## quantum-gates
Unlike class logic gates (AND, OR, NOT), quantum gates are reversible and represented by unitary matrices acting on qb state vectors.

- **Pauli-X (X)**: The quantum equivalent of the class NOT gate. Flips `|0⟩` to `|1⟩` and vice versa. It rotates the state by π radians around the X-axis of the Bloch sphere.
- **Pauli-Y (Y) & Pauli-Z (Z)**: Rotations around the Y and Z axes. The Z gate flips the phase of the `|1⟩` state without changing the probs (leaves `|0⟩` alone, changes `|1⟩` to `-|1⟩`).
- **Hadamard (H)**: The gate that creates sup. Applying H to `|0⟩` yields an equal sup of `|0⟩` and `|1⟩` (often denoted as `|+⟩`). Applying H twice returns the state to the original.
- **CNOT (Controlled-NOT)**: A two-qb gate crucial for ent. It applies an X gate to the target qb *if and only if* the control qb is in state `|1⟩`.

## Breakthrough quantum algs

### Shor's alg (1994)
A polynomial-time quantum alg for integer factorization. 
- **The Class Problem**: Factoring a 2048-bit number (the basis of RSA crypt used to secure the internet) would take a class supercomputer millions of years. It's an exponentially hard problem.
- **The Quantum Solution**: Shor's alg uses Quantum Phase Estimation and the Quantum Fourier Transform to find the period of a modular exponential function, which directly yields the prime factors.
- **Impact**: A sufficiently large, fault-tolerant qc running Shor's alg will break RSA, Diffie-Hellman, and Elliptic Curve crypt completely in a matter of hours. This threat has spawned the field of Post-Quantum crypt (PQC).

### Grover's alg (1996)
A quantum alg for searching an unsorted database.
- **The Class Problem**: Searching an unsorted list of N items takes O(N) time (you have to check every item).
- **The Quantum Solution**: Grover's alg uses amp amplification to find the target item in O(√N) time.
- **Impact**: While not an exponential speedup like Shor's, a quadratic speedup is massive for large datasets. It also halves the effective key length of symmetric block ciphers like AES. AES-256 is required to provide the equivalent security against a quantum attacker that AES-128 provides against a class attacker.

## Hardware and Challenges

### Decoherence and err
qbs are extremely fragile. Interaction with the environment (heat, electromagnetic radiation) causes them to lose their quantum state (decoherence) before the comp finishes.
- **NISQ Era**: We are currently in the Noisy Intermediate-Scale Quantum era. Modern qcs have 50-1000 noisy qbs without err.
- **err**: To build a fault-tolerant qc, we need err. This requires encoding one "logical" qb into hundreds or thousands of "physical" qbs. A 100-logical-qb machine might require 100,000 physical qbs to operate reliably. Creating stable surface codes and topological qbs (like Majorana fermions) are major areas of research.

### Modalities
Various physical systems are used to construct qbs, each with pros and cons:
1. **Superconducting Circuits** (IBM, Google): Fast operation, but must be cooled to near absolute zero (~15 milliKelvin).
2. **Trapped Ions** (Quantinuum, IonQ): Individual atoms trapped by electromagnetic fields. Very long coherence times and high fidelity, but slower gate operations and harder to scale than solid-state chips.
3. **Photonic** (PsiQuantum): Uses photons. Can operate at room temperature and is easily networked (quantum internet), but difficult to perform two-qb gates probabilistically.
4. **Silicon Spin qbs** (Intel): Leverages existing semiconductor manufacturing to isolate the spin of a single electron in silicon. High potential for massive scalability.