Quantum Computing

Hilbert space $H$ adalah ruang vektor kompleks dengan:

• Inner product: $\langle\phi|\psi\rangle = c$ (bilangan kompleks)
• Norm: $||\psi|| = \sqrt{\langle\psi|\psi\rangle}$
• Completeness: semua limit Cauchy konvergen di dalam ruang

Untuk QC, kita pakai $H = \mathbb{C}^2$ (1 qubit) atau $H = \mathbb{C}^{2^n}$ (n qubit).

$|\psi\rangle$ dan $e^{i\theta} |\psi\rangle$ mewakili state fisik yang SAMA.

Kenapa? Karena semua observasi (probabilitas) bergantung pada $|\langle\phi|\psi\rangle|^2$, dan phase global hilang saat di-kuadratkan.

Konsekuensi: Bloch sphere adalah ruang proyektif $\mathbb{CP}^1$, bukan bola 3D penuh.

Semua single-qubit gate adalah elemen $SU(2)$: matriks $2 \times 2$ unitary dengan determinant = 1.

$U = \exp\left(-i \frac{\theta_x X + \theta_y Y + \theta_z Z}{2}\right)$

Ini adalah rotasi 3D di Bloch sphere dengan sudut $\theta$ di sekitar sumbu $(\theta_x, \theta_y, \theta_z)$.

$R_x(\theta) = \exp(-i \theta X / 2) = \cos(\theta/2)I - i\sin(\theta/2)X$

$R_y(\theta) = \exp(-i \theta Y / 2) = \cos(\theta/2)I - i\sin(\theta/2)Y$

$R_z(\theta) = \exp(-i \theta Z / 2) = \cos(\theta/2)I - i\sin(\theta/2)Z$

$i \hbar \frac{d|\psi\rangle}{dt} = H |\psi\rangle$

Untuk $H$ time-independent:

$|\psi(t)\rangle = U(t) |\psi(0)\rangle = \exp(-i H t / \hbar) |\psi(0)\rangle$

Hamiltonian total (dalam frame berotasi):

$H = (\Delta/2)Z + (\Omega/2)(\cos(\phi)X + \sin(\phi)Y)$

di mana:

• $\Delta$ = detuning (selisih frekuensi drive dengan frekuensi qubit)
• $\Omega$ = Rabi rate (kekuatan drive)
• $\phi$ = phase drive

Jika $\Delta = 0$ (on resonance): $H = (\Omega/2)\cos(\phi)X + (\Omega/2)\sin(\phi)Y$

Ini adalah rotasi di equator Bloch sphere!

$|ab\rangle = |a\rangle \otimes |b\rangle$

Contoh untuk 2 qubit:

$|00\rangle = |0\rangle \otimes |0\rangle = [1, 0]^T \otimes [1, 0]^T = [1, 0, 0, 0]^T$

$|01\rangle = |0\rangle \otimes |1\rangle = [1, 0]^T \otimes [0, 1]^T = [0, 1, 0, 0]^T$

Umum: $(\alpha|0\rangle + \beta|1\rangle) \otimes (\gamma|0\rangle + \delta|1\rangle)$

$= \alpha\gamma|00\rangle + \alpha\delta|01\rangle + \beta\gamma|10\rangle + \beta\delta|11\rangle$

Product State (Bisa difaktorkan):

$|\psi\rangle = (|0\rangle + |1\rangle) / \sqrt{2} \otimes |0\rangle = (|00\rangle + |10\rangle) / \sqrt{2}$

Ini adalah superposisi, tapi BUKAN entanglement. Qubit kedua selalu 0.

Entangled State (TIDAK bisa difaktorkan):

$|\Phi^+\rangle = (|00\rangle + |11\rangle) / \sqrt{2}$

Tidak bisa ditulis sebagai $|a\rangle \otimes |b\rangle$ untuk sembarang $|a\rangle, |b\rangle$!

Jika qubit pertama 0, qubit kedua PASTI 0. Jika pertama 1, kedua PASTI 1.

Setiap bipartite state bisa ditulis sebagai:

$|\psi\rangle = \sum_i \lambda_i |i_A\rangle \otimes |i_B\rangle$

di mana $\lambda_i$ adalah Schmidt coefficients (real, non-negative, sum to 1).

Jika hanya SATU $\lambda_i = 1$ (yang lain 0): product state.

Jika lebih dari SATU $\lambda_i > 0$: entangled.

Entanglement entropy = $-\sum_i \lambda_i^2 \log(\lambda_i^2)$

Set of projectors $\{P_i\}$ yang memenuhi:

• $P_i^2 = P_i$ (idempotent)
• $P_i^\dagger = P_i$ (Hermitian)
• $\sum_i P_i = I$ (complete)
• $P_i P_j = 0$ untuk $i \neq j$ (orthogonal)

Probabilitas outcome $i$: $p(i) = \langle\psi|P_i|\psi\rangle$

State setelah outcome $i$: $|\psi'\rangle = P_i|\psi\rangle / \sqrt{p(i)}$

$P_0 = |0\rangle\langle 0| = \begin{pmatrix}1&0\\0&0\end{pmatrix}$ (projector ke $|0\rangle$)

$P_1 = |1\rangle\langle 1| = \begin{pmatrix}0&0\\0&1\end{pmatrix}$ (projector ke $|1\rangle$)

Untuk state $|\psi\rangle = \alpha|0\rangle + \beta|1\rangle$:

$p(0) = |\alpha|^2, p(1) = |\beta|^2$

Setelah measurement:

• Jika outcome 0: state menjadi $|0\rangle$
• Jika outcome 1: state menjadi $|1\rangle$

Set of operators $\{E_i\}$ (POVM elements) yang memenuhi:

• $E_i \geq 0$ (positive semidefinite)
• $\sum_i E_i = I$ (complete)

Tidak perlu orthogonal! Tidak perlu projector!

Probabilitas: $p(i) = \langle\psi|E_i|\psi\rangle$

POVM tidak menentukan post-measurement state. Untuk itu, perlu instrument (Kraus operators).

Contoh: Weak measurement dengan $E_0 = (1+\epsilon)P_0 + (1-\epsilon)P_1, E_1 = I - E_0$.

Untuk state $|\psi\rangle$ dan measurement basis $\{|\phi_i\rangle\}$:

$p(\text{outcome} = i) = |\langle\phi_i|\psi\rangle|^2$

di mana $\langle\phi_i|\psi\rangle$ = overlap antara state dan basis outcome.

Konsekuensi: Amplitudo kompleks, tapi probabilitas selalu REAL dan NON-NEGATIVE.

Total probabilitas: $\sum_i p(i) = \sum_i |\langle\phi_i|\psi\rangle|^2 = \langle\psi|\sum_i|\phi_i\rangle\langle\phi_i||\psi\rangle = \langle\psi|I|\psi\rangle = 1$.

Setelah outcome dengan projector $P_i$:

$|\psi'\rangle = P_i |\psi\rangle / \sqrt{\langle\psi|P_i|\psi\rangle}$

Pembagian dengan $\sqrt{p}$ untuk re-normalisasi (total probabilitas harus tetap 1).

Ini adalah NON-UNITARY process! Measurement adalah satu-satunya non-unitary operation di QC.

State: $|\psi\rangle = 0.6|0\rangle + 0.8|1\rangle$

Measure di Z basis:

$p(0) = |0.6|^2 = 0.36$, state' = $|0\rangle$

$p(1) = |0.8|^2 = 0.64$, state' = $|1\rangle$

Measure di X basis ($|+\rangle = (|0\rangle+|1\rangle)/\sqrt{2}, |-\rangle = (|0\rangle-|1\rangle)/\sqrt{2}$):

$p(+) = |\langle+|\psi\rangle|^2 = |(0.6+0.8)/\sqrt{2}|^2 = 0.98$

$p(-) = |\langle-|\psi\rangle|^2 = |(0.6-0.8)/\sqrt{2}|^2 = 0.02$

Hasil BERBEDA tergantung basis! Ini adalah "contextuality" kuantum.

Untuk operator $O_{AB}$ di $H_A \otimes H_B$:

$\rho_A = \text{Tr}_B(O_{AB}) = \sum_j \langle j_B|O_{AB}|j_B\rangle$

di mana $\{|j_B\rangle\}$ adalah basis B (sembarang).

Intuisi: "summing out" atau "averaging over" degrees of freedom B.

Jika sistem AB di state murni $|\psi_{AB}\rangle$, reduced DM untuk A:

$\rho_A = \text{Tr}_B(|\psi_{AB}\rangle\langle\psi_{AB}|)$

Contoh untuk Bell state $|\Phi^+\rangle = (|00\rangle + |11\rangle)/\sqrt{2}$:

$\rho_A = \text{Tr}_B(|\Phi^+\rangle\langle\Phi^+|) = (|0\rangle\langle0| + |1\rangle\langle1|) / 2 = I/2$

Ini adalah MAXIMAL MIXED state! Meskipun joint state murni!

Von Neumann entropy: $S(\rho_A) = -\text{Tr}(\rho_A \log(\rho_A)) = 1$ bit.

Ini adalah ukuran entanglement antara A dan B!

Untuk |psi_AB> = sigma_i lambda_i |i_A> ⊗ |i_B>:

rho_A = sigma_i lambda_i^2 |i_A><i_A|

Eigenvalues dari rho_A adalah lambda_i^2 (Schmidt coefficients squared).

Jika hanya SATU lambda_i = 1: rho_A adalah pure state (product state).

Jika banyak lambda_i > 0: rho_A adalah mixed state (entangled).

$\rho = \sum_i p_i |\psi_i\rangle\langle\psi_i|$

Sifat wajib:

• $\rho^\dagger = \rho$ (Hermitian)
• $\text{Tr}(\rho) = 1$ (trace 1)
• $\rho \geq 0$ (positive semidefinite)

Pure state: $\text{Tr}(\rho^2) = 1$

Mixed state: $\text{Tr}(\rho^2) < 1$

Maximally mixed: $\rho = I/d$ ($d$ = dimensi ruang)

Untuk observable $O$:

$\langle O\rangle = \text{Tr}(\rho O) = \sum_i p_i \langle\psi_i|O|\psi_i\rangle$

Ini berlaku untuk pure dan mixed state!

Contoh: Untuk $\rho = I/2$ (maximally mixed 1-qubit):

$\langle Z\rangle = \text{Tr}((I/2) Z) = (1/2) \text{Tr}(Z) = 0$

Tidak ada preferensi ke $|0\rangle$ atau $|1\rangle$ (random).

$\rho(t) = U(t) \rho(0) U^\dagger(t)$

Untuk Hamiltonian $H$:

$d\rho/dt = -(i/\hbar) [H, \rho]$ (Liouville-von Neumann eq)

Ini adalah analog Schrödinger equation untuk density matrix.

$[H, \rho] = H\rho - \rho H$ adalah commutator.

$d\rho/dt = -(i/\hbar)[H, \rho] + \sum_k \gamma_k (L_k \rho L_k^\dagger - (1/2)\{L_k^\dagger L_k, \rho\})$

di mana:

• $H$ = Hamiltonian sistem (term unitary)
• $L_k$ = jump operators (operator "collapse")
• $\gamma_k$ = rates (kecepatan proses dissipatif)
• $\{A, B\} = AB + BA$ (anti-commutator)

Term kedua adalah LINDBLAD DISSIPATOR (non-unitary!).

$L = \sigma_- = |0\rangle\langle 1|$ (lowering operator)

$\gamma = 1/T_1$ (relaxation rate)

Lindblad term:

$D[\rho] = (1/T_1) (\sigma_- \rho \sigma_+ - (1/2)\{\sigma_+ \sigma_-, \rho\})$

di mana $\sigma_+ = |1\rangle\langle 0|$ (raising operator).

Efek: Populasi $|1\rangle$ bocor ke $|0\rangle$ secara eksponensial.

$\rho_{11}(t) = \rho_{11}(0) e^{-t/T_1}$

$L = \sigma_z = |0\rangle\langle 0| - |1\rangle\langle 1|$

$\gamma_\phi = 1/T_\phi$ (dephasing rate)

Lindblad term:

$D[\rho] = (1/T_\phi) (\sigma_z \rho \sigma_z - \rho)$

Efek: Off-diagonal elements (coherence) decay.

$\rho_{01}(t) = \rho_{01}(0) e^{-t/T_\phi}$

Populasi (diagonal) TIDAK berubah, tapi phase information hilang.

Jika set gate $G$ adalah universal dan dense di $SU(2)$, maka untuk sembarang target unitary $U$:

Bisa dibuat pendekatan $U'$ dari $G$ dengan error $\epsilon$

Panjang circuit (gate count) $\sim O(\log^c(1/\epsilon))$

di mana $c \sim 3$ (konstanta Solovay-Kitaev).

Konsekuensi: Bisa compile sembarang algorithm ke gate finite!

Trade-off: Lebih akurat = lebih banyak gate.

Clifford + T (Populer di FTQC):

• Clifford: H, S, CNOT (bisa disimulasikan klasik dengan Gottesman-Knill)
• T gate: memberikan "non-Clifford resource" untuk universalitas

Universal di hardware:

• Semua rotasi + CNOT (teori)
• Di hardware: {RX, RZ, CZ} atau { microwave drive, flux gate }

Kunci: Clifford + SATU non-Clifford = universal.

Exact universal: Setiap unitary bisa dibuat EXACT (jarang ada)

Approximate universal: Setiap unitary bisa didekati ARBITRARY close (semua gate set realistic!)

Contoh: {H, T} adalah approximate universal, bukan exact.

Untuk algoritma seperti Shor, perlu akurasi ~10^(-12), jadi butuh banyak T gate!

Width = Jumlah qubit fisik yang digunakan

Depth = Jumlah time step (minimal, gate yang paralel dihitung 1)

Contoh:

• H pada semua 10 qubit: width=10, depth=1 (bisa paralel!)
• CNOT cascade: width=2, depth=N (harus serial)

Trade-off: Lebih banyak qubit = bisa paralel lebih banyak = reduce depth.

1. High-level algorithm (misal: QFT, Shor)

↓

2. Decompose ke gate set universal {H, T, CNOT}

↓

3. Synthesize ke native gate hardware {RX, RZ, CZ}

↓

4. Mapping ke konektivitas hardware (insert SWAP jika perlu)

↓

5. Optimization (cancel inverses, merge rotations)

↓

6. Pulse-level optimization (optional, untuk NISQ)

Hardware qubit punya konektivitas TERBATAS (bukan all-to-all).

Contoh konektivitas:

• Linear: qubit i hanya terhubung ke i-1 dan i+1
• 2D grid (surface code): setiap qubit terhubung ke 4 neighbor
• All-to-all: jarang (trapped ion mendekati ini)

Jika CNOT butuh qubit jauh: insert SWAP gates!

SWAP(i,j) = 3 CNOT (atau lebih efficient di beberapa hardware).

Routing overhead bisa BESAR: 3x-10x depth increase.

Di NISQ, noise ~1% per gate. 100 gate = 63% survival rate.

Strategi optimasi:

• Cancel gate inverse: $R_z(\theta) R_z(-\theta) = I$
• Merge rotation: $R_z(a) R_z(b) = R_z(a+b)$
• Qubit permutation: pilih mapping awal yang baik
• Peephole optimization: optimasi sub-circuit lokal

Goal: minimize depth TANPA mengubah logika algorithm!