6. Quantum Information Basics

The quantum bit (qubit) is the fundamental unit:

Where $\alpha, \beta \in \mathbb{C}$

Classical bit vs. Qubit:

• Classical: One of two definite states (0 or 1)
• Quantum: Superposition of $|0\rangle$ and $|1\rangle$ until measured
• Information content: Qubit described by 2 continuous parameters (sphere), classical bit by 1 discrete value
• Measurement: Destroys superposition, yields 0 or 1 probabilistically

Physical realizations:

• Photon polarization: $|H\rangle, |V\rangle$
• Electron spin: $|\uparrow\rangle, |\downarrow\rangle$
• Atomic levels: $|g\rangle, |e\rangle$ (ground, excited)
• Superconducting circuits: charge or flux states

Theorem: It is impossible to create an identical copy of an arbitrary unknown quantum state.

Proof sketch:

Suppose cloning operation exists: $\hat{U}|\psi\rangle|0\rangle = |\psi\rangle|\psi\rangle$

For two states $|\phi\rangle$ and $|\chi\rangle$:

This implies $\langle\phi|\chi\rangle \in \{0, 1\}$ - only orthogonal or identical states can be cloned!

Implications:

• Quantum information cannot be perfectly copied
• Eavesdropping on quantum communication is detectable
• Quantum teleportation destroys original state
• Fundamental to quantum cryptography security

Single-qubit gates (unitary 2×2 matrices):

Pauli gates:

Hadamard gate:

Phase gate:

Two-qubit gate - CNOT (controlled-NOT):

Flips target qubit $t$ if control qubit $c = 1$; creates entanglement!

Universal gate sets: Any quantum operation can be approximated by sequences of gates from a universal set

Examples:

• $\{H, T, \text{CNOT}\}$ - commonly used
• $\{\text{CNOT}, $ all single-qubit gates$\}$
• Continuous: $\{R_x(\theta), R_z(\theta), \text{CNOT}\}$

Example circuit - Bell state preparation:

Input: $|00\rangle$

Apply $H$ to first qubit: $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle) \otimes |0\rangle$

Apply CNOT: $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle) = |\Phi^+\rangle$

Solovay-Kitaev theorem: Any unitary can be approximated to precision $\epsilon$ using $O(\log^c(1/\epsilon))$ gates from universal set

1. Deutsch-Jozsa Algorithm:

Problem: Determine if function $f: \{0,1\}^n \to \{0,1\}$ is constant or balanced

Classical: requires $2^{n-1} + 1$ queries

Quantum: 1 query (exponential speedup!)

2. Grover's Search Algorithm:

Search unsorted database of $N$ items

Classical: $O(N)$ queries

Quantum: $O(\sqrt{N})$ queries (quadratic speedup)

3. Shor's Factoring Algorithm:

Factor $N$-digit number

Classical (best known): sub-exponential $\exp(O(N^{1/3}))$

Quantum: polynomial $O(N^3)$ (exponential speedup!)

Uses quantum Fourier transform to find period of modular exponentiation

Implication: Breaks RSA cryptography (motivates post-quantum crypto)

BB84 Protocol (Bennett & Brassard 1984):

1. Alice sends random qubits in random bases ($\{|0\rangle, |1\rangle\}$ or $\{|+\rangle, |-\rangle\}$)
2. Bob measures in random bases
3. Alice and Bob publicly compare basis choices (not results)
4. Keep only bits where bases matched (~50%)
5. Check subset for errors (eavesdropper detection)
6. If error rate low, use remaining bits as secret key

Security:

• Eavesdropper (Eve) must measure qubits, causing disturbance
• No-cloning theorem prevents perfect copying
• Uncertainty principle: measuring in one basis randomizes conjugate basis
• Information-theoretic security (not computational)

Modern QKD operates over 100+ km fiber, even via satellite

1. Superdense Coding:

Send 2 classical bits using 1 qubit + shared entanglement

1. Alice and Bob share Bell state $|\Phi^+\rangle$
2. Alice applies $\mathbb{I}, X, Z,$ or $iY$ to encode 00, 01, 10, or 11
3. Alice sends her qubit to Bob
4. Bob performs Bell measurement, decodes 2 bits

2. Quantum Teleportation:

Transfer unknown state $|\psi\rangle$ using entanglement + 2 classical bits

1. Share Bell pair between Alice and Bob
2. Alice performs Bell measurement on $|\psi\rangle$ and her half of pair
3. Alice sends 2-bit result to Bob classically
4. Bob applies conditional unitary, obtains $|\psi\rangle$

Original state destroyed (no cloning), requires classical channel (no FTL)

3. Entanglement Swapping:

Create entanglement between particles that never interacted - basis for quantum repeaters and quantum internet

Holevo bound: Maximum classical information extractable from quantum states

Can't extract more than 1 classical bit from 1 qubit (despite continuous parameters)

Quantum channel capacity:

• Classical capacity: $C = \max_{\rho} \chi(\rho)$
• Quantum capacity: $Q = \max_{\rho} [S(\mathcal{N}(\rho)) - S_E]$ (coherent information)
• Entanglement-assisted: Can exceed unassisted capacities

Quantum data compression: $n$ qubits in ensemble compressible to $nS(\rho)$ qubits (Schumacher compression)

1. Circuit Model:

Sequence of quantum gates on qubits (standard model)

2. Adiabatic Quantum Computing:

Slowly evolve from easy initial Hamiltonian to problem Hamiltonian; ground state encodes solution

3. Measurement-Based (One-Way):

Prepare cluster state, perform adaptive measurements - computation emerges from measurement pattern

4. Topological:

Encode qubits in non-local topological degrees of freedom (anyons); inherently fault-tolerant

All models polynomially equivalent in computational power

Complexity classes:

• BQP: Bounded-error Quantum Polynomial time - problems solvable efficiently on quantum computer
• P: Classical polynomial time
• NP: Non-deterministic polynomial time

Believed hierarchy:

Quantum computers more powerful than classical, but probably can't solve NP-complete problems efficiently

Quantum supremacy: Demonstrated in 2019 (Google) - quantum computer solved problem intractable for classical supercomputer