Syllabus quantum computing (3)
GIAI ĐOẠN 4 - QUANTUM ALGORITHMS (120 ngày, Ngày 361–480)
MODULE 4.1 - DEUTSCH-JOZSA ALGORITHM (Ngày 361–370)
Ngày 361: Giới thiệu Mô hình Oracle
Mục tiêu: Hiểu "black box function" (oracle) - mô hình dùng xuyên suốt toàn Giai đoạn 4.
Lý thuyết: Oracle U_f: |x⟩|y⟩ → |x⟩|y⊕f(x)⟩, tại sao phải mã hóa kiểu XOR để giữ tính khả nghịch (liên hệ Giai đoạn 3).
Thực hành: Viết oracle U_f cho hàm f(x) = x (1 bit) dưới dạng ma trận 4x4.
Ngày 362: Deutsch's Problem - Phiên bản 1 Qubit
Mục tiêu: Làm quen bài toán lượng tử đầu tiên trong lịch sử có ưu thế so với cổ điển.
Lý thuyết: f: {0,1}→{0,1}; hỏi f có constant hay balanced mà chỉ cần 1 lần gọi oracle (cổ điển cần 2 lần).
Thực hành: Liệt kê cả 4 hàm f khả dĩ (2 constant, 2 balanced).
Ngày 363: Deutsch's Algorithm - Mạch và Phân tích
Mục tiêu: Thiết kế và hiểu mạch giải Deutsch's problem.
Lý thuyết: Mạch H⊗H → U_f → H, dùng ancilla qubit khởi tạo |1⟩ (kỹ thuật phase kickback lần đầu xuất hiện).
Thực hành: Tính tay toàn bộ trạng thái qua từng bước mạch cho 1 hàm f constant cụ thể.
Ngày 364: Deutsch-Jozsa Problem - Tổng quát hóa n Qubit
Mục tiêu: Mở rộng bài toán cho f: {0,1}^n → {0,1}, đảm bảo f constant hoặc balanced.
Lý thuyết: Cổ điển cần tối đa 2^(n-1)+1 lần gọi oracle trong trường hợp xấu nhất; lượng tử chỉ cần 1 lần.
Thực hành: Đọc Nielsen & Chuang mục 1.4.4, ghi chú phát biểu bài toán tổng quát.
Ngày 365: Deutsch-Jozsa Algorithm - Thiết kế Mạch
Mục tiêu: Thành thạo mạch tổng quát cho n qubit.
Lý thuyết: H⊗n → U_f → H⊗n trên n qubit đầu, đo toàn bộ; kết quả toàn 0 ⟺ f constant.
Thực hành: Vẽ mạch đầy đủ cho n=3.
Ngày 366: Deutsch-Jozsa Algorithm - Chứng minh Đúng đắn
Mục tiêu: Tự chứng minh được vì sao đo ra toàn 0 khi và chỉ khi f constant.
Lý thuyết: Khai triển biên độ xác suất đo |0⟩^n dùng tổng Σ(-1)^f(x), dùng lại kỹ thuật tổng trực giao.
Thực hành: Hoàn thành chứng minh từng bước bằng ký hiệu của riêng bạn.
Ngày 367: Quantum Parallelism
Mục tiêu: Hiểu khái niệm cốt lõi giải thích ưu thế lượng tử ở đây.
Lý thuyết: H⊗n|0⟩^n tạo superposition đều của tất cả 2^n input; U_f đánh giá f trên toàn bộ đồng thời (nhưng không trích xuất trực tiếp được - chỉ dùng gián tiếp qua giao thoa).
Thực hành: Viết 1 đoạn giải thích vì sao "tính f trên mọi input cùng lúc" không tự động cho phép đọc ra mọi kết quả (liên hệ Holevo bound, Giai đoạn 2 Ngày 275).
Ngày 368: Phase Kickback - Kỹ thuật Quan trọng
Mục tiêu: Nắm vững kỹ thuật sẽ tái sử dụng trong hầu hết thuật toán còn lại của Giai đoạn 4.
Lý thuyết: Khi ancilla ở trạng thái |−⟩, U_f "đá" pha (-1)^f(x) ngược lại vào qubit input thay vì chỉ đổi ancilla.
Thực hành: Chứng minh U_f|x⟩|−⟩ = (-1)^f(x)|x⟩|−⟩ bằng tính toán trực tiếp.
Ngày 369: Cài đặt Deutsch-Jozsa bằng Simulator
Mục tiêu: Chạy thuật toán đầu tiên trên simulator tự viết ở Giai đoạn 3.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt oracle cho 2 hàm f (1 constant, 1 balanced) trên simulator, chạy Deutsch-Jozsa, xác nhận kết quả đo đúng như dự đoán.
Ngày 370: Ôn tập + Kiểm tra Module 4.1
Mục tiêu: Củng cố toàn bộ module và tự đánh giá.
Lý thuyết: Tổng hợp ngày 361–369.
Thực hành: Bài test 10 câu bao quát Module 4.1.
MODULE 4.2 - BERNSTEIN-VAZIRANI ALGORITHM (Ngày 371–380)
Ngày 371: Giới thiệu Bài toán Bernstein-Vazirani
Mục tiêu: Làm quen bài toán tìm secret string s ẩn trong hàm f(x) = s·x mod 2.
Lý thuyết: Phát biểu bài toán, oracle U_f dựa trên tích vô hướng nhị phân.
Thực hành: Cho s = 101, tính f(x) cho toàn bộ 8 giá trị x có thể.
Ngày 372: So sánh Độ phức tạp Cổ điển vs Lượng tử
Mục tiêu: Thấy rõ ưu thế: cổ điển cần n lần gọi oracle, lượng tử chỉ cần 1 lần.
Lý thuyết: Cổ điển phải hỏi f(e_i) cho từng bit cơ sở i để dựng lại s; lượng tử lấy được cả s cùng lúc.
Thực hành: Viết thuật toán cổ điển tìm s bằng n lần gọi f, đếm số lần gọi cho n=5.
Ngày 373: Thiết kế Mạch Bernstein-Vazirani
Mục tiêu: Nhận ra mạch gần như giống hệt Deutsch-Jozsa (dùng lại toàn bộ Module 4.1).
Lý thuyết: Cùng cấu trúc H⊗n → U_f → H⊗n, chỉ khác oracle.
Thực hành: Vẽ mạch cho n=3, s=101.
Ngày 374: Chứng minh Đúng đắn Thuật toán
Mục tiêu: Tự chứng minh kết quả đo chính là s.
Lý thuyết: Dùng lại kỹ thuật phase kickback (Ngày 368) và khai triển tổng Σ(-1)^(s·x) x |x⟩.
Thực hành: Hoàn thành chứng minh từng bước, xác nhận kết quả đo = s với xác suất 1.
Ngày 375: Oracle Construction cho Bernstein-Vazirani
Mục tiêu: Thành thạo xây oracle U_f từ s cho trước dưới dạng mạch CNOT.
Lý thuyết: Với mỗi bit s_i = 1, đặt CNOT từ qubit i vào ancilla.
Thực hành: Vẽ mạch oracle tường minh cho s = 1011.
Ngày 376: Liên hệ Bernstein-Vazirani với Deutsch-Jozsa
Mục tiêu: Nhìn thấy Bernstein-Vazirani là 1 trường hợp con đặc biệt trong họ bài toán oracle.
Lý thuyết: f(x) = s·x luôn balanced (trừ s=0), Deutsch-Jozsa chỉ phân biệt constant/balanced còn Bernstein-Vazirani tìm ra chính xác s.
Thực hành: Viết 1 đoạn so sánh 2 bài toán: input, output, độ mạnh của kết luận rút ra.
Ngày 377: Cài đặt bằng Simulator
Mục tiêu: Chạy thuật toán trên simulator tự viết.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt oracle cho s=101 trên simulator, chạy thuật toán, xác nhận đo ra đúng s.
Ngày 378: Test với Nhiều Secret String Khác nhau
Mục tiêu: Kiểm chứng tính tổng quát của cài đặt.
Lý thuyết: Không có thêm.
Thực hành: Chạy simulator cho 5 giá trị s khác nhau (bao gồm s=0 và s=toàn 1), xác nhận luôn đúng.
Ngày 379: Ôn tập Module 4.2
Mục tiêu: Củng cố toàn bộ module.
Lý thuyết: Tổng hợp.
Thực hành: 6 bài tập.
Ngày 380: Kiểm tra kiến thức Module 4.2
Mục tiêu: Tự đánh giá trước khi sang Simon's Algorithm.
Lý thuyết: Không có.
Thực hành: Bài test 10 câu.
MODULE 4.3 - SIMON'S ALGORITHM (Ngày 381–395)
Ngày 381: Giới thiệu Bài toán Simon
Mục tiêu: Làm quen bài toán khó hơn hẳn - tìm chu kỳ ẩn s trong hàm 2-to-1.
Lý thuyết: f: {0,1}^n → {0,1}^n với f(x) = f(y) ⟺ y = x⊕s (s≠0); tìm s.
Thực hành: Xây 1 ví dụ hàm f cụ thể cho n=2, s=11, liệt kê toàn bộ ánh xạ.
Ngày 382: So sánh Độ phức tạp - Đây là Bước ngoặt
Mục tiêu: Hiểu vì sao Simon's algorithm là thuật toán đầu tiên cho ưu thế mũ (exponential speedup) thực sự, chứ không chỉ tuyến tính như Bernstein-Vazirani.
Lý thuyết: Cổ điển cần Ω(2^(n/2)) lần gọi (theo birthday paradox); lượng tử chỉ cần O(n) lần.
Thực hành: Viết 1 đoạn giải thích áp dụng birthday paradox vào việc tìm va chạm f(x)=f(y) bằng cổ điển.
Ngày 383: Oracle cho Simon's Problem
Mục tiêu: Hiểu cấu trúc oracle 2-to-1 phức tạp hơn các module trước.
Lý thuyết: U_f: |x⟩|0⟩ → |x⟩|f(x)⟩, lần này output register cần n qubit (không chỉ 1 ancilla).
Thực hành: Xây bảng oracle tường minh cho ví dụ n=2, s=11 ở Ngày 381.
Ngày 384: Thiết kế Mạch Simon Algorithm
Mục tiêu: Thành thạo mạch: H⊗n trên input → U_f → đo output register → H⊗n trên input → đo.
Lý thuyết: Khác Deutsch-Jozsa/Bernstein-Vazirani ở chỗ có bước đo giữa chừng (measure output register).
Thực hành: Vẽ mạch đầy đủ cho n=2.
Ngày 385: Chứng minh - Mỗi Lần chạy cho ra y Vuông góc với s
Mục tiêu: Hiểu bản chất thống kê của thuật toán - mỗi lần chạy chỉ cho 1 phương trình, cần lặp nhiều lần.
Lý thuyết: Sau đo, trạng thái input sụp đổ về superposition của {x, x⊕s}; áp H⊗n cho ra y sao cho y·s = 0 mod 2.
Thực hành: Hoàn thành chứng minh từng bước cho ví dụ n=2, s=11.
Ngày 386: Giải Hệ Phương trình Tuyến tính trên GF(2)
Mục tiêu: Học kỹ thuật classical post-processing bắt buộc để hoàn thiện thuật toán.
Lý thuyết: Sau khi thu thập n-1 phương trình y_i·s=0 độc lập tuyến tính, giải hệ trên trường GF(2) (nhị phân) để tìm s.
Thực hành: Giải hệ 2 phương trình tuyến tính trên GF(2) bằng tay cho ví dụ cụ thể.
Ngày 387: Ôn lại Linear Algebra trên GF(2)
Mục tiêu: Nhận ra linear algebra trên GF(2) khác linear algebra trên số thực đã học ở Giai đoạn 0 (không có khái niệm "độ lớn", phép cộng = XOR).
Lý thuyết: Định nghĩa vector space trên GF(2), độc lập tuyến tính trên GF(2).
Thực hành: Kiểm tra 3 tập vector nhị phân có độc lập tuyến tính trên GF(2) không.
Ngày 388: Phân tích Số lần Chạy Cần thiết
Mục tiêu: Chứng minh cần trung bình O(n) lần chạy mạch lượng tử để có đủ n-1 phương trình độc lập.
Lý thuyết: Xác suất 1 vector ngẫu nhiên trên GF(2)^n độc lập với các vector đã có.
Thực hành: Tính xác suất kỳ vọng cần bao nhiêu lần thử để có đủ n-1 phương trình độc lập cho n=5.
Ngày 389: Ý nghĩa - Simon's Algorithm là Tiền đề của Shor's Algorithm
Mục tiêu: Nhìn thấy trước cấu trúc sẽ tái sử dụng ở Module 4.6.
Lý thuyết: Shor's algorithm dùng đúng ý tưởng "tìm chu kỳ ẩn" của Simon, nhưng trên nhóm Z thay vì Z_2^n, và cần QFT thay vì chỉ H⊗n.
Thực hành: Viết 1 đoạn so sánh cấu trúc bài toán Simon và bài toán period-finding sẽ gặp ở Ngày 445–446.
Ngày 390: Cài đặt Oracle cho Simon
Mục tiêu: Bắt đầu chuỗi ngày cài đặt trên simulator.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt oracle U_f cho hàm 2-to-1 với s cho trước (n=2 hoặc 3) trên simulator.
Ngày 391: Cài đặt Phần Lượng tử của Thuật toán
Mục tiêu: Hoàn thiện mạch lượng tử.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt hàm chạy 1 lần mạch Simon, trả về 1 giá trị y quan sát được.
Ngày 392: Cài đặt Phần Classical Post-processing
Mục tiêu: Hoàn thiện bước giải hệ GF(2).
Lý thuyết: Không có thêm.
Thực hành: Viết hàm Python giải hệ phương trình tuyến tính trên GF(2) (Gaussian elimination modulo 2) để tìm s từ tập các y thu thập được.
Ngày 393: Test Full Pipeline Simon's Algorithm
Mục tiêu: Kiểm chứng toàn bộ thuật toán end-to-end.
Lý thuyết: Không có thêm.
Thực hành: Chạy full pipeline (lặp mạch lượng tử nhiều lần + giải GF(2)) cho 3 giá trị s khác nhau, xác nhận tìm đúng s.
Ngày 394: Ôn tập Tổng hợp Module 4.3
Mục tiêu: Kết nối oracle → mạch lượng tử → GF(2) post-processing thành một pipeline liền mạch.
Lý thuyết: Vẽ sơ đồ khối toàn bộ pipeline.
Thực hành: 8 bài tập tổng hợp.
Ngày 395: Kiểm tra kiến thức Module 4.3
Mục tiêu: Tự đánh giá trước khi sang Grover's Algorithm.
Lý thuyết: Không có.
Thực hành: Bài test 12 câu bao quát Module 4.3.
MODULE 4.4 - GROVER'S ALGORITHM (Ngày 396–420)
Ngày 396: Bài toán Tìm kiếm Không có Cấu trúc
Mục tiêu: Làm quen bài toán ứng dụng thực tế rộng nhất trong toàn Giai đoạn 4.
Lý thuyết: Cho N phần tử không sắp xếp, tìm phần tử thỏa điều kiện f(x)=1 (giả sử duy nhất 1 nghiệm).
Thực hành: Viết thuật toán cổ điển brute-force, xác nhận độ phức tạp trung bình O(N/2).
Ngày 397: Mục tiêu Lượng tử - O(√N)
Mục tiêu: Thấy trước đích đến: ưu thế bậc hai (quadratic speedup), khác hẳn ưu thế mũ của Simon/Shor.
Lý thuyết: So sánh O(N) cổ điển vs O(√N) lượng tử; với N=10^6, cổ điển cần ~500000 bước, lượng tử chỉ cần ~1000 bước.
Thực hành: Tính số bước cần thiết cho N = 10^4, 10^6, 10^9 với cả 2 cách tiếp cận.
Ngày 398: Oracle cho Grover - Đánh dấu Phase
Mục tiêu: Học dạng oracle mới: đánh dấu nghiệm bằng phase âm thay vì flip ancilla.
Lý thuyết: U_f|x⟩ = -|x⟩ nếu x là nghiệm, |x⟩ nếu không (dùng phase kickback với ancilla |−⟩ như Ngày 368).
Thực hành: Viết ma trận U_f cho bài toán tìm kiếm 4 phần tử với nghiệm x=10.
Ngày 399: Grover Diffusion Operator - Khái niệm
Mục tiêu: Học toán tử thứ hai cần thiết cho thuật toán.
Lý thuyết: D = 2|s⟩⟨s| - I với |s⟩ là superposition đều; ý nghĩa "phản xạ quanh giá trị trung bình" (inversion about the mean).
Thực hành: Đọc Nielsen & Chuang mục 6.1, ghi chú ý nghĩa trực giác của diffusion operator.
Ngày 400: Grover Diffusion Operator - Ma trận và Ý nghĩa Hình học
Mục tiêu: Thành thạo cài đặt D = H⊗n(2|0⟩⟨0|-I)H⊗n.
Lý thuyết: Phân rã D thành gate cơ bản: H⊗n, phase flip quanh |0⟩^n, H⊗n.
Thực hành: Viết ma trận D tường minh cho n=2 (N=4).
Ngày 401: Amplitude Amplification - Trực giác Hình học
Mục tiêu: Hiểu vì sao 2 phép phản xạ liên tiếp tương đương 1 phép quay.
Lý thuyết: Trong mặt phẳng 2 chiều span bởi |nghiệm⟩ và |không-nghiệm⟩, oracle và diffusion mỗi cái là 1 phép phản xạ; 2 phản xạ = 1 phép quay góc 2θ.
Thực hành: Vẽ hình minh họa (trên giấy) quá trình quay của vector trạng thái qua 2-3 vòng lặp Grover.
Ngày 402: Amplitude Amplification - Chứng minh Toán học
Mục tiêu: Tự chứng minh công thức góc quay θ với sin(θ) = 1/√N.
Lý thuyết: Phân tích trạng thái ban đầu |s⟩ theo 2 thành phần trực giao (nghiệm và không-nghiệm), suy ra công thức góc.
Thực hành: Hoàn thành chứng minh từng bước cho N=4, xác nhận 1 vòng lặp Grover cho xác suất thành công =1 (trường hợp đặc biệt).
Ngày 403: Số lần Lặp Tối ưu
Mục tiêu: Thành thạo công thức k ≈ π√N/4.
Lý thuyết: Suy ra công thức từ góc quay 2θ mỗi vòng lặp, cần quay tổng góc ≈ π/2.
Thực hành: Tính số lần lặp tối ưu cho N = 16, 100, 1000000.
Ngày 404: Grover's Algorithm - Full Circuit cho 1 Target
Mục tiêu: Vẽ và hiểu toàn bộ mạch hoàn chỉnh.
Lý thuyết: H⊗n khởi tạo → lặp k lần (Oracle → Diffusion) → đo.
Thực hành: Vẽ mạch đầy đủ cho N=4, k=1 (giải cụ thể toàn bộ trạng thái từng bước).
Ngày 405: Chứng minh Đúng đắn Đầy đủ
Mục tiêu: Tổng hợp toàn bộ chứng minh Ngày 401–403 thành 1 bài chứng minh hoàn chỉnh.
Lý thuyết: Không có thêm.
Thực hành: Tự viết lại toàn bộ chứng minh Grover's algorithm từ đầu đến cuối không nhìn tài liệu.
Ngày 406: Overshooting
Mục tiêu: Hiểu hệ quả khi lặp quá số lần tối ưu.
Lý thuyết: Vì amplitude amplification là phép quay tuần hoàn, lặp quá nhiều làm xác suất thành công giảm trở lại (quay qua khỏi đỉnh).
Thực hành: Tính xác suất thành công cho k = k_optimal, k_optimal+2, k_optimal+5 với N=100, vẽ đồ thị minh họa dao động.
Ngày 407: Grover với Nhiều Target
Mục tiêu: Mở rộng cho trường hợp M nghiệm (M>1).
Lý thuyết: Công thức góc quay mới sin(θ)=√(M/N), số lần lặp tối ưu ≈ π√(N/M)/4.
Thực hành: Tính số lần lặp tối ưu khi N=1000, M=10.
Ngày 408: Grover khi Không biết Trước Số lượng Solutions
Mục tiêu: Làm quen kỹ thuật xử lý khi M chưa biết (giới thiệu sơ lược thuật toán "quantum counting" liên quan).
Lý thuyết: Chiến lược tăng dần số lần lặp thử (exponential search over k) để không cần biết M trước.
Thực hành: Đọc tóm tắt chiến lược này, ghi chú ý tưởng chính.
Ngày 409: Ôn tập Lý thuyết Grover
Mục tiêu: Củng cố ngày 396–408.
Lý thuyết: Tổng hợp.
Thực hành: 10 bài tập lý thuyết Grover.
Ngày 410: Cài đặt Oracle cho Bài toán Tìm kiếm Cụ thể
Mục tiêu: Bắt đầu chuỗi ngày cài đặt.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt oracle đánh dấu phase cho 1 giá trị target cụ thể trên simulator (n=2, sau đó n=3).
Ngày 411: Cài đặt Diffusion Operator
Mục tiêu: Hoàn thiện thành phần thứ hai của thuật toán.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt hàm
diffusion_operator(n)trên simulator, kiểm thử bằng cách áp lên 1 state đã biết trước kết quả.
Ngày 412: Cài đặt Full Grover Algorithm
Mục tiêu: Ghép nối toàn bộ pipeline.
Lý thuyết: Không có thêm.
Thực hành: Viết hàm
grover_search(oracle, n, iterations)chạy đầy đủ thuật toán và trả về kết quả đo.
Ngày 413: Test Grover trên Không gian Tìm kiếm Nhỏ
Mục tiêu: Kiểm chứng cài đặt bằng trường hợp đã biết trước xác suất thành công.
Lý thuyết: Không có thêm.
Thực hành: Chạy Grover cho N=4 và N=8, đo 1000 lần, xác nhận tỷ lệ thành công khớp với tính toán lý thuyết ở Ngày 402.
Ngày 414: Test Grover trên Không gian Tìm kiếm Lớn hơn
Mục tiêu: Xác nhận công thức số lần lặp tối ưu đúng trong thực nghiệm.
Lý thuyết: Không có thêm.
Thực hành: Chạy Grover cho N=64 với nhiều giá trị k khác nhau, vẽ đồ thị xác suất thành công theo k, xác nhận đỉnh tại k ≈ π√N/4.
Ngày 415: Grover's Algorithm là Tối ưu - BBBV Theorem
Mục tiêu: Biết đến định lý chứng minh Grover đạt lower bound (không thể nhanh hơn O(√N) bằng bất kỳ thuật toán lượng tử nào).
Lý thuyết: Giới thiệu sơ lược Bennett-Bernstein-Brassard-Vazirani theorem (không chứng minh chi tiết).
Thực hành: Đọc tóm tắt định lý, ghi chú ý nghĩa: Grover là tối ưu, không chỉ là "một cách hay".
Ngày 416: Ứng dụng Grover - Tìm kiếm Cơ sở Dữ liệu, SAT Solving
Mục tiêu: Thấy ứng dụng thực tế rộng của thuật toán.
Lý thuyết: Grover có thể dùng làm subroutine cho nhiều bài toán NP (SAT, tìm collision, tối ưu tổ hợp).
Thực hành: Viết 1 trang mô tả cách áp dụng Grover vào bài toán 3-SAT nhỏ.
Ngày 417: Ứng dụng Grover - Liên hệ tới An ninh Mật mã
Mục tiêu: Hiểu hệ quả thực tế quan trọng nhất của Grover với ngành mật mã (khác Shor - chỉ giảm an toàn 1 nửa số bit, không phá vỡ hoàn toàn).
Lý thuyết: AES-256 dưới tấn công Grover chỉ còn tương đương độ an toàn AES-128; đây là lý do NIST khuyến nghị tăng gấp đôi độ dài khóa đối xứng cho kỷ nguyên hậu lượng tử.
Thực hành: Viết 1 đoạn giải thích tại sao Grover "nguy hiểm" hơn với mật mã đối xứng nhưng ít nghiêm trọng hơn Shor với RSA.
Ngày 418: Đọc bổ sung - Nielsen & Chuang Chương 6
Mục tiêu: Lấp lỗ hổng lý thuyết trước khi kiểm tra.
Lý thuyết: Đọc lại toàn bộ chương 6 (Quantum Search Algorithms).
Thực hành: Ghi chú tổng hợp 2 trang.
Ngày 419: Ôn tập Tổng hợp Module 4.4
Mục tiêu: Kết nối Oracle → Diffusion → Amplitude Amplification → Ứng dụng thành một mạch logic liền.
Lý thuyết: Vẽ sơ đồ tổng thể.
Thực hành: 12 bài tập tổng hợp.
Ngày 420: Kiểm tra kiến thức Module 4.4
Mục tiêu: Tự đánh giá tổng thể trước khi sang Quantum Fourier Transform.
Lý thuyết: Không có.
Thực hành: Bài test 18 câu bao quát Module 4.4, kèm 1 bài thực hành viết code Grover cho 1 oracle mới.
MODULE 4.5 - QUANTUM FOURIER TRANSFORM (Ngày 421–440)
Ngày 421: Classical Discrete Fourier Transform - Ôn lại
Mục tiêu: Ôn lại nền tảng DFT trước khi học phiên bản lượng tử.
Lý thuyết: Công thức DFT, ý nghĩa chuyển đổi giữa miền thời gian/không gian và miền tần số.
Thực hành: Tính DFT của 1 vector 4 phần tử bằng tay, kiểm chứng bằng
numpy.fft.fft.
Ngày 422: Quantum Fourier Transform - Định nghĩa
Mục tiêu: Học phiên bản lượng tử của DFT, áp dụng lên biên độ của state vector thay vì dữ liệu cổ điển.
Lý thuyết: QFT|x⟩ = (1/√N)Σ_y e^(2πixy/N)|y⟩.
Thực hành: Đọc Nielsen & Chuang mục 5.1, ghi chú định nghĩa.
Ngày 423: QFT - Ma trận và Tính chất Unitary
Mục tiêu: Thành thạo biểu diễn ma trận QFT cho n nhỏ.
Lý thuyết: Ma trận QFT là unitary (đã ngầm định vì đây là gate hợp lệ); kiểm chứng cho N=2 (chính là Hadamard!).
Thực hành: Viết ma trận QFT cho N=4, xác nhận tính unitary bằng cách nhân với ma trận liên hợp chuyển vị.
Ngày 424: So sánh QFT vs Classical FFT
Mục tiêu: Hiểu rõ điểm khác biệt quan trọng: QFT nhanh hơn về số gate, nhưng không thể đọc trực tiếp toàn bộ output (do Holevo bound).
Lý thuyết: QFT cần O(n²) gate (n=log N) so với FFT cổ điển O(N log N) = O(n2^n); nhưng QFT chỉ hữu ích khi kết hợp với đo lường có mục đích cụ thể (như phase estimation).
Thực hành: Tính và so sánh số phép toán cần thiết cho N=1024 giữa QFT (theo số gate) và FFT cổ điển.
Ngày 425: Thiết kế Mạch QFT - Hadamard + Controlled Phase Gates
Mục tiêu: Thành thạo cấu trúc mạch chuẩn.
Lý thuyết: Mỗi qubit áp H rồi loạt controlled-phase gate CP(2π/2^k) với các qubit sau.
Thực hành: Vẽ mạch QFT đầy đủ cho n=3 qubit.
Ngày 426: Thiết kế Mạch QFT - Swap Qubits Cuối cùng
Mục tiêu: Hoàn thiện mạch, hiểu vì sao cần đảo thứ tự qubit ở bước cuối.
Lý thuyết: Do cấu trúc đệ quy của thuật toán, kết quả ra theo thứ tự ngược, cần SWAP (đã học Ngày 325) để sửa lại.
Thực hành: Bổ sung các gate SWAP vào mạch Ngày 425, kiểm chứng thứ tự qubit đúng.
Ngày 427: Chứng minh Đúng đắn Mạch QFT
Mục tiêu: Tự chứng minh mạch cho đúng công thức QFT.
Lý thuyết: Khai triển tích tensor của các trạng thái sau mỗi tầng Hadamard/controlled-phase, đối chiếu với công thức nhị phân của QFT.
Thực hành: Hoàn thành chứng minh cho n=2 từng bước.
Ngày 428: Inverse QFT
Mục tiêu: Học phiên bản nghịch đảo, sẽ dùng trực tiếp ở Shor's algorithm.
Lý thuyết: QFT† - đảo ngược thứ tự mạch, đổi dấu góc phase.
Thực hành: Vẽ mạch inverse QFT cho n=3 từ mạch QFT Ngày 425–426.
Ngày 429: Cài đặt QFT bằng Simulator
Mục tiêu: Chạy QFT trên simulator tự viết.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt hàm
qft(n)sinh mạch QFT trên simulator, áp lên 1 state cụ thể.
Ngày 430: Test QFT - So sánh với DFT Cổ điển
Mục tiêu: Kiểm chứng cài đặt bằng cách đối chiếu kết quả biên độ với
numpy.fft.Lý thuyết: Không có thêm.
Thực hành: So sánh vector biên độ đầu ra của QFT simulator với kết quả
numpy.fft.fftcho cùng 1 input, xác nhận khớp (sai khác chuẩn hóa).
Ngày 431: Ôn tập QFT
Mục tiêu: Củng cố ngày 421–430.
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập QFT.
Ngày 432: Phase Estimation - Động lực và Bài toán
Mục tiêu: Làm quen bài toán trung tâm sẽ dẫn trực tiếp tới Shor's algorithm.
Lý thuyết: Cho unitary U và eigenstate |u⟩ với eigenvalue e^(2πiθ), ước lượng θ.
Thực hành: Đọc Nielsen & Chuang mục 5.2, ghi chú phát biểu bài toán.
Ngày 433: Phase Estimation - Thiết kế Mạch
Mục tiêu: Thành thạo cấu trúc mạch 2 phần: controlled-U^(2^k) rồi inverse QFT.
Lý thuyết: Register "counting" ở trạng thái superposition điều khiển các lũy thừa của U áp lên eigenstate; sau đó inverse QFT trích xuất θ.
Thực hành: Vẽ mạch phase estimation đầy đủ cho 3-bit counting register.
Ngày 434: Phase Estimation - Chứng minh Đúng đắn
Mục tiêu: Tự chứng minh mạch cho ra θ với xác suất cao.
Lý thuyết: Kết nối trực tiếp với chứng minh QFT (Ngày 427) - trạng thái counting register sau bước controlled-U chính là QFT của θ mã hóa nhị phân.
Thực hành: Hoàn thành chứng minh từng bước cho trường hợp θ biểu diễn chính xác bằng số bit hữu hạn.
Ngày 435: Độ chính xác và Số Qubit Cần thiết
Mục tiêu: Hiểu đánh đổi giữa số qubit counting register và độ chính xác ước lượng θ.
Lý thuyết: Với t qubit, sai số ước lượng θ giảm theo 2^(-t); công thức xác suất thành công.
Thực hành: Tính số qubit cần thiết để ước lượng θ với sai số < 10^-3.
Ngày 436: Cài đặt Phase Estimation bằng Simulator
Mục tiêu: Chạy thuật toán trên simulator tự viết.
Lý thuyết: Không có thêm.
Thực hành: Cài đặt phase estimation cho 1 gate U đơn giản (ví dụ gate T với θ=1/8 đã biết trước) trên simulator.
Ngày 437: Test Phase Estimation với Unitary Đơn giản
Mục tiêu: Kiểm chứng độ chính xác cài đặt.
Lý thuyết: Không có thêm.
Thực hành: Chạy phase estimation cho gate T, S, Z (θ lần lượt = 1/8, 1/4, 1/2), xác nhận kết quả đo khớp giá trị θ đã biết.
Ngày 438: Ứng dụng Phase Estimation - Tiền đề cho Shor's Algorithm
Mục tiêu: Nhìn thấy cầu nối trực tiếp sang Module 4.6.
Lý thuyết: Order-finding (bài toán lõi của Shor) chính là 1 trường hợp áp dụng Phase Estimation lên toán tử modular multiplication.
Thực hành: Viết 1 đoạn giải thích tại sao "tìm chu kỳ của a^x mod N" có thể quy về "ước lượng pha của 1 eigenvalue".
Ngày 439: Ôn tập Tổng hợp Module 4.5
Mục tiêu: Kết nối QFT → Inverse QFT → Phase Estimation.
Lý thuyết: Vẽ sơ đồ liên hệ toàn module.
Thực hành: 10 bài tập tổng hợp.
Ngày 440: Kiểm tra kiến thức Module 4.5
Mục tiêu: Tự đánh giá tổng thể trước khi sang Shor's Algorithm - module dài và khó nhất syllabus.
Lý thuyết: Không có.
Thực hành: Bài test 15 câu bao quát Module 4.5.
MODULE 4.6 - SHOR'S ALGORITHM (Ngày 441–480)
Ngày 441: Giới thiệu Bài toán Phân tích Thừa số Nguyên tố
Mục tiêu: Hiểu bài toán integer factorization và vì sao nó quan trọng.
Lý thuyết: Cho N = p×q (p, q nguyên tố), tìm p và q.
Thực hành: Phân tích thừa số 3 số nhỏ bằng tay (ví dụ 15, 21, 35).
Ngày 442: RSA Cryptosystem - Ôn lại Cơ chế
Mục tiêu: Hiểu vì sao factoring khó lại chính là nền tảng an toàn của RSA.
Lý thuyết: Khóa công khai (N,e), khóa riêng d, an toàn dựa trên độ khó phân tích N=p×q.
Thực hành: Thực hiện 1 vòng mã hóa/giải mã RSA hoàn chỉnh bằng tay với số nhỏ (N=15).
Ngày 443: Độ khó Cổ điển của Factoring
Mục tiêu: Hiểu tại sao factoring được coi là "khó" theo nghĩa thực tế dù không chứng minh được là NP-hard.
Lý thuyết: Thuật toán cổ điển tốt nhất (General Number Field Sieve) có độ phức tạp sub-exponential.
Thực hành: Đọc tóm tắt về GNFS, ghi chú độ phức tạp xấp xỉ.
Ngày 444: Ý tưởng Cốt lõi của Shor
Mục tiêu: Nắm bức tranh tổng thể trước khi đi vào chi tiết.
Lý thuyết: Quy bài toán factoring về bài toán order-finding (tìm chu kỳ của hàm modular exponentiation) - bước quy giản này hoàn toàn cổ điển.
Thực hành: Đọc Nielsen & Chuang mục 5.3.1, ghi chú sơ đồ tổng thể 4 bước của Shor's algorithm.
Ngày 445: Order-Finding Problem
Mục tiêu: Định nghĩa chính xác bài toán con cần giải bằng lượng tử.
Lý thuyết: Order của a modulo N là số r nhỏ nhất sao cho a^r ≡ 1 (mod N).
Thực hành: Tính order của a=2 modulo N=15 bằng tay (liệt kê 2^1, 2^2,... mod 15).
Ngày 446: Liên hệ Order-Finding với Period-Finding
Mục tiêu: Nhận ra order-finding chính là bài toán tìm chu kỳ của hàm f(x) = a^x mod N.
Lý thuyết: f(x) tuần hoàn với chu kỳ r; kết nối trực tiếp với Simon's algorithm (Module 4.3) - cùng dạng bài toán nhưng trên nhóm khác.
Thực hành: Vẽ đồ thị f(x) = 2^x mod 15 cho x=0..10, quan sát tính tuần hoàn.
Ngày 447: Số học Modular - Ôn tập
Mục tiêu: Đảm bảo nền tảng số học đủ vững (nếu Giai đoạn 0 chưa phủ đủ).
Lý thuyết: Modular arithmetic, gcd, thuật toán Euclid mở rộng.
Thực hành: Tính gcd(48,18) bằng thuật toán Euclid, tìm nghịch đảo modular của 3 mod 7.
Ngày 448: Continued Fractions
Mục tiêu: Học kỹ thuật classical post-processing bắt buộc để trích xuất r từ kết quả đo Phase Estimation.
Lý thuyết: Thuật toán continued fraction expansion tìm phân số p/q gần nhất với 1 số thực cho trước với mẫu số giới hạn.
Thực hành: Áp dụng continued fraction expansion bằng tay cho 1 số thập phân cụ thể, tìm phân số xấp xỉ tốt nhất.
Ngày 449: Modular Exponentiation - Thuật toán Cổ điển
Mục tiêu: Học thuật toán "square-and-multiply" hiệu quả để tính a^x mod N.
Lý thuyết: Độ phức tạp O(log x) thay vì O(x) phép nhân.
Thực hành: Cài đặt hàm Python
mod_exp(a, x, N)bằng square-and-multiply, kiểm thử với vài giá trị.
Ngày 450: Modular Exponentiation - Mạch Lượng tử (Giới thiệu)
Mục tiêu: Hiểu sơ lược đây là phần "tốn kém" nhất về số gate trong toàn bộ Shor's algorithm.
Lý thuyết: Cần xây mạch controlled modular multiplication; độ phức tạp mạch O((log N)²) đến O((log N)³) tùy cách cài đặt.
Thực hành: Đọc tóm tắt về độ phức tạp mạch, ghi chú (không cần tự thiết kế mạch chi tiết ở mức sản xuất).
Ngày 451: Period-Finding bằng Quantum Phase Estimation - Thiết kế Tổng thể
Mục tiêu: Ghép nối Module 4.5 (Phase Estimation) với bài toán order-finding.
Lý thuyết: Áp dụng Phase Estimation lên unitary U_a: |y⟩ → |ay mod N⟩; eigenvalue của U_a liên hệ trực tiếp với r.
Thực hành: Viết sơ đồ khối tổng thể: counting register + Phase Estimation + inverse QFT + đo + continued fractions.
Ngày 452: Period-Finding - Chi tiết Mạch
Mục tiêu: Thành thạo cấu trúc mạch đầy đủ (dùng lại QFT từ Module 4.5).
Lý thuyết: Controlled-U_a^(2^k) cho từng qubit counting register, sau đó inverse QFT.
Thực hành: Vẽ sơ đồ mạch tổng thể cho trường hợp N=15, a=7.
Ngày 453: Chứng minh Đúng đắn Period-Finding
Mục tiêu: Tự chứng minh kết quả đo counting register cho ra thông tin về r.
Lý thuyết: Kết quả đo xấp xỉ j/r × 2^t cho j ngẫu nhiên; dùng continued fractions để trích r từ đó.
Thực hành: Hoàn thành chứng minh từng bước cho ví dụ N=15, a=7, r=4.
Ngày 454: Từ Period tới Factor
Mục tiêu: Hoàn thiện bước cuối cùng quy từ r về p, q.
Lý thuyết: Công thức: nếu r chẵn, tính gcd(a^(r/2)-1, N) và gcd(a^(r/2)+1, N) cho ra 2 thừa số không tầm thường.
Thực hành: Áp dụng công thức cho N=15, a=7, r=4, tính ra p=3, q=5.
Ngày 455: Điều kiện Thành công
Mục tiêu: Hiểu thuật toán không phải lúc nào cũng thành công ngay lần đầu.
Lý thuyết: Cần r chẵn và a^(r/2) ≢ -1 (mod N); nếu không thỏa, phải chọn lại a ngẫu nhiên và thử lại.
Thực hành: Kiểm tra điều kiện này cho 3 giá trị a khác nhau với N=15, xác định trường hợp nào thất bại.
Ngày 456: Xác suất Thành công và Số Lần Lặp lại
Mục tiêu: Định lượng độ tin cậy tổng thể của thuật toán.
Lý thuyết: Với a ngẫu nhiên, xác suất thỏa điều kiện thành công ≥ 1/2; do đó số lần thử kỳ vọng là hằng số nhỏ.
Thực hành: Tính xác suất thành công sau k lần thử độc lập với xác suất mỗi lần ≥ 1/2, cho k=1,2,3.
Ngày 457: Ví dụ Đầy đủ - Phân tích N=15
Mục tiêu: Đi qua toàn bộ 4 bước của thuật toán cho ví dụ kinh điển nhất trong lịch sử (cũng là ví dụ đã chạy trên phần cứng thật đầu tiên).
Lý thuyết: Tổng hợp lại toàn bộ Module 4.6 từ đầu cho N=15.
Thực hành: Tự giải hoàn chỉnh bằng tay: chọn a, tính order r, kiểm tra điều kiện, tính gcd, ra kết quả p=3, q=5.
Ngày 458: Ví dụ Đầy đủ - Phân tích N=21
Mục tiêu: Củng cố bằng ví dụ thứ hai để chắc chắn hiểu quy trình, không chỉ nhớ đáp án N=15.
Lý thuyết: Không có thêm.
Thực hành: Tự giải hoàn chỉnh bằng tay cho N=21, tìm p=3, q=7.
Ngày 459: Ôn tập Lý thuyết Shor - Phần 1
Mục tiêu: Củng cố ngày 441–450 (bối cảnh, quy giản bài toán, modular exponentiation).
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập.
Ngày 460: Ôn tập Lý thuyết Shor - Phần 2
Mục tiêu: Củng cố ngày 451–458 (phase estimation cho order-finding, continued fractions, ví dụ đầy đủ).
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập.
Ngày 461: Cài đặt Modular Exponentiation Classical
Mục tiêu: Bắt đầu chuỗi ngày cài đặt full pipeline.
Lý thuyết: Không có thêm (dùng lại Ngày 449).
Thực hành: Hoàn thiện và kiểm thử kỹ hàm
mod_exp(a, x, N).
Ngày 462: Cài đặt Mạch Quantum Order-Finding (Đơn giản hóa)
Mục tiêu: Cài đặt phần lượng tử cho N nhỏ (không cần mạch modular exponentiation tối ưu cấp sản xuất).
Lý thuyết: Với N nhỏ (≤ 21), có thể cài đặt trực tiếp U_a như 1 ma trận hoán vị (permutation matrix) thay vì mạch chi tiết.
Thực hành: Cài đặt U_a dưới dạng ma trận hoán vị cho N=15, tích hợp vào Phase Estimation đã xây ở Ngày 436.
Ngày 463: Cài đặt Continued Fractions Algorithm
Mục tiêu: Hoàn thiện bước classical post-processing cuối cùng.
Lý thuyết: Không có thêm.
Thực hành: Viết hàm Python
continued_fraction(x, max_denominator)trích xuất phân số p/q gần nhất.
Ngày 464: Tích hợp Toàn bộ Pipeline Shor's Algorithm
Mục tiêu: Ghép nối tất cả các thành phần đã cài đặt.
Lý thuyết: Không có thêm.
Thực hành: Viết hàm
shor_factor(N)gọi tuần tự: chọn a ngẫu nhiên → quantum order-finding → continued fractions → kiểm tra điều kiện → tính gcd.
Ngày 465: Test Full Pipeline với N=15
Mục tiêu: Kiểm chứng cài đặt bằng ví dụ đã giải tay ở Ngày 457.
Lý thuyết: Không có thêm.
Thực hành: Chạy
shor_factor(15)nhiều lần, xác nhận luôn trả về {3,5} (có thể cần thử lại a vài lần).
Ngày 466: Test Full Pipeline với N=21
Mục tiêu: Kiểm chứng tính tổng quát của cài đặt.
Lý thuyết: Không có thêm.
Thực hành: Chạy
shor_factor(21), xác nhận trả về {3,7}.
Ngày 467: Debug và Tối ưu hóa Cài đặt
Mục tiêu: Rà soát và sửa các trường hợp biên (a không nguyên tố cùng N, r lẻ...).
Lý thuyết: Không có thêm.
Thực hành: Thêm xử lý edge case vào
shor_factor, viết thêm unit test cho N=35.
Ngày 468: Phân tích Độ phức tạp Shor's Algorithm
Mục tiêu: Thành thạo phân tích độ phức tạp tổng thể O((log N)³) (hoặc tốt hơn tùy cài đặt modular exponentiation).
Lý thuyết: Tổng hợp độ phức tạp từng thành phần: QFT O((log N)²), modular exponentiation O((log N)²-³).
Thực hành: Viết bảng phân tích độ phức tạp từng bước của thuật toán.
Ngày 469: So sánh Độ phức tạp Shor vs Cổ điển
Mục tiêu: Định lượng rõ mức độ "cách mạng" của kết quả này.
Lý thuyết: Polynomial O((log N)³) của Shor so với sub-exponential của GNFS (Ngày 443).
Thực hành: Tính thời gian ước lượng cần thiết để factor 1 số 2048-bit bằng cả 2 phương pháp (dùng số liệu tham khảo từ tài liệu), so sánh.
Ngày 470: Hệ quả với RSA và An ninh Mạng Hiện tại
Mục tiêu: Hiểu bối cảnh thực tế: vì sao đây là động lực lớn nhất thúc đẩy đầu tư vào quantum computing.
Lý thuyết: RSA, ECC (elliptic curve cryptography) đều dựa trên các bài toán mà thuật toán kiểu Shor giải được hiệu quả (discrete log cũng vậy).
Thực hành: Đọc tổng quan về "Q-Day" (thời điểm quantum computer đủ mạnh phá RSA), ghi chú các ước tính hiện tại.
Ngày 471: Post-Quantum Cryptography - Giới thiệu Sơ lược
Mục tiêu: Nhìn trước sang giải pháp đối phó (chủ đề sẽ không đào sâu trong syllabus này nhưng cần biết đến).
Lý thuyết: Các họ thuật toán được cho là kháng lượng tử: lattice-based, hash-based, code-based cryptography; chuẩn NIST PQC.
Thực hành: Đọc tổng quan ngắn về NIST PQC standardization, ghi chú 3 thuật toán đã được chuẩn hóa.
Ngày 472: Đọc bổ sung - Nielsen & Chuang Chương 5
Mục tiêu: Lấp lỗ hổng lý thuyết trước khi kiểm tra.
Lý thuyết: Đọc lại toàn bộ chương 5 (The Quantum Fourier Transform and its Applications).
Thực hành: Ghi chú tổng hợp 3 trang.
Ngày 473: Đọc Paper Gốc Shor 1994
Mục tiêu: Lần đầu tiếp cận trực tiếp một paper nghiên cứu gốc quan trọng (chuẩn bị kỹ năng cho Giai đoạn 12).
Lý thuyết: Đọc ít nhất abstract và introduction của paper "Algorithms for Quantum Computation: Discrete Logarithms and Factoring" (Shor, 1994).
Thực hành: Viết tóm tắt 1 trang bằng lời riêng, đối chiếu với những gì đã học trong Module 4.6.
Ngày 474: Ôn tập Tổng hợp Shor's Algorithm
Mục tiêu: Kết nối toàn bộ 4 bước: quy giản cổ điển → order-finding lượng tử → continued fractions → gcd.
Lý thuyết: Vẽ sơ đồ tổng thể toàn bộ thuật toán từ đầu đến cuối.
Thực hành: 10 bài tập tổng hợp.
Ngày 475: Bài tập Tổng hợp - Period-Finding
Mục tiêu: Luyện tập chuyên sâu phần lượng tử.
Lý thuyết: Không có thêm.
Thực hành: 6 bài tập tính toán liên quan Phase Estimation áp dụng cho order-finding.
Ngày 476: Bài tập Tổng hợp - Factor Extraction
Mục tiêu: Luyện tập chuyên sâu phần classical post-processing.
Lý thuyết: Không có thêm.
Thực hành: 6 bài tập continued fractions + gcd cho các giá trị N, a, r khác nhau.
Ngày 477: Ôn tập Tổng hợp Module 4.6
Mục tiêu: Củng cố toàn bộ module trước khi kiểm tra.
Lý thuyết: Tổng hợp ngày 441–476.
Thực hành: 12 bài tập tổng hợp.
Ngày 478: Kiểm tra kiến thức Module 4.6
Mục tiêu: Tự đánh giá tổng thể.
Lý thuyết: Không có.
Thực hành: Bài test 20 câu bao quát Module 4.6, kèm 1 bài thực hành chạy
shor_factorcho 1 N mới (ví dụ 33).
Ngày 479: Sửa Lỗ hổng Kiến thức
Mục tiêu: Khắc phục điểm yếu phát hiện từ bài test Ngày 478.
Lý thuyết: Ôn có trọng điểm các chủ đề sai nhiều nhất.
Thực hành: Làm lại bài tập tương ứng các chủ đề còn yếu.
Ngày 480: Tổng kết Giai đoạn 4
Mục tiêu: Xác nhận sẵn sàng chuyển sang Giai đoạn 5 (Quantum Complexity Theory).
Lý thuyết: Ôn lại toàn bộ 6 module: Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, QFT, Shor - nhấn mạnh mạch phát triển logic xuyên suốt (oracle → phase kickback → amplitude amplification → period-finding).
Thực hành: Bài kiểm tra tổng hợp 30 câu bao quát toàn Giai đoạn 4; đảm bảo cả 4 thuật toán chính (Deutsch-Jozsa, Grover, QFT/Phase Estimation, Shor) đều đã chạy đúng trên simulator tự viết trước khi bước sang Giai đoạn 5, vì các thuật toán này sẽ được dùng làm ví dụ minh họa liên tục cho lớp phức tạp BQP.
GIAI ĐOẠN 5 - QUANTUM COMPLEXITY THEORY (60 ngày, Ngày 481–540)
PHẦN A - BQP: BOUNDED-ERROR QUANTUM POLYNOMIAL TIME (Ngày 481–500)
Ngày 481: Ôn tập Complexity Theory Cổ điển
Mục tiêu: Kết nối lại với Giai đoạn 0 (Module 0.4) trước khi mở rộng sang lượng tử.
Lý thuyết: Ôn lại P, NP, PSPACE, sơ đồ bao hàm P ⊆ NP ⊆ PSPACE.
Thực hành: Tự vẽ lại sơ đồ Venn các lớp phức tạp cổ điển không nhìn tài liệu.
Ngày 482: Giới thiệu BQP - Định nghĩa Hình thức
Mục tiêu: Học định nghĩa chính xác của lớp phức tạp trung tâm trong quantum computing.
Lý thuyết: BQP = lớp bài toán quyết định giải được bởi mạch lượng tử kích thước polynomial, với xác suất đúng ≥ 2/3.
Thực hành: Đọc Nielsen & Chuang mục 3.2 (hoặc tài liệu Watrous tương ứng), ghi chú định nghĩa.
Ngày 483: BQP và Mối quan hệ với P, NP, PSPACE
Mục tiêu: Định vị BQP trong bức tranh tổng thể các lớp phức tạp.
Lý thuyết: Sơ đồ bao hàm hiện tại được biết: P ⊆ BQP ⊆ PSPACE; quan hệ BQP với NP chưa được biết rõ (không chứng minh được BQP ⊆ NP hay ngược lại).
Thực hành: Vẽ sơ đồ Venn cập nhật gồm cả BQP, đánh dấu rõ quan hệ nào đã chứng minh, quan hệ nào còn là giả thuyết mở.
Ngày 484: Bounded Error - Ý nghĩa Ngưỡng 2/3
Mục tiêu: Hiểu vì sao ngưỡng xác suất cụ thể (2/3) không quan trọng bằng khả năng khuếch đại độ chính xác.
Lý thuyết: Error reduction bằng cách lặp lại thuật toán k lần và lấy đa số (majority vote).
Thực hành: Tính xác suất sai sau khi lặp lại 10 lần một thuật toán có xác suất đúng ban đầu = 0.6.
Ngày 485: Chứng minh Error Reduction - Chernoff Bound
Mục tiêu: Hiểu công cụ toán học đứng sau khẳng định ở Ngày 484.
Lý thuyết: Chernoff bound (giới thiệu sơ lược, không cần chứng minh đầy đủ) - xác suất sai giảm theo hàm mũ theo số lần lặp.
Thực hành: Đọc phát biểu Chernoff bound, ghi chú công thức và ý nghĩa trực giác.
Ngày 486: BQP chứa P
Mục tiêu: Tự chứng minh mọi thuật toán cổ điển đều mô phỏng được bằng mạch lượng tử.
Lý thuyết: Mọi mạch cổ điển khả nghịch (dùng Toffoli - Giai đoạn 3, Ngày 322–323) đều nhúng được vào mạch lượng tử.
Thực hành: Viết lại lập luận chứng minh P ⊆ BQP bằng lời của riêng bạn, dựa trên kiến thức reversible computing đã học.
Ngày 487: BQP vs BPP
Mục tiêu: So sánh với lớp phức tạp ngẫu nhiên hóa cổ điển gần nhất (Bounded-error Probabilistic Polynomial time).
Lý thuyết: BPP ⊆ BQP (đã biết); BQP ⊆ BPP hay không là câu hỏi tương đương "quantum advantage có thật hay không" theo nghĩa phức tạp tính toán.
Thực hành: Viết 1 đoạn giải thích tại sao câu hỏi BPP = BQP? quan trọng ngang câu hỏi P = NP?.
Ngày 488: Factoring ∈ BQP - Bằng chứng Cụ thể
Mục tiêu: Kết nối trực tiếp với Shor's algorithm đã cài đặt ở Giai đoạn 4.
Lý thuyết: Shor's algorithm là bằng chứng xây dựng (constructive proof) rằng integer factorization ∈ BQP.
Thực hành: Viết lại độ phức tạp Shor's algorithm (Giai đoạn 4, Ngày 468) dưới dạng chứng minh hình thức "factoring ∈ BQP".
Ngày 489: Giả thuyết BQP ⊄ P - Động lực
Mục tiêu: Hiểu vì sao cộng đồng tin quantum advantage tồn tại dù chưa chứng minh được tuyệt đối.
Lý thuyết: Không có bằng chứng toán học chặt (vì sẽ kéo theo P ≠ PSPACE, một bài toán mở); nhưng có bằng chứng gián tiếp mạnh (Shor phá RSA mà chưa ai tìm được thuật toán cổ điển tương đương).
Thực hành: Viết 1 trang lập luận về "tại sao chúng ta tin nhưng chưa chứng minh được BQP ⊄ P".
Ngày 490: BQP ⊆ PSPACE
Mục tiêu: Tự chứng minh (ở mức trực giác) một trong hai chiều bao hàm đã biết chắc chắn.
Lý thuyết: Mô phỏng mạch lượng tử bằng cách tính trực tiếp biên độ (dùng bộ nhớ polynomial dù thời gian mũ) - kỹ thuật path-integral-style simulation.
Thực hành: Đọc chứng minh sơ lược trong Nielsen & Chuang hoặc Watrous, ghi chú ý tưởng chính (không cần thuộc từng bước).
Ngày 491: Uniformity của Mạch Lượng tử
Mục tiêu: Hiểu điều kiện kỹ thuật cần thiết để định nghĩa BQP chặt chẽ (liên hệ Turing machine - Giai đoạn 0).
Lý thuyết: Polynomial-time uniform circuit family - cần tồn tại 1 Turing machine cổ điển sinh ra mạch cho từng kích thước input trong thời gian polynomial.
Thực hành: Viết 1 đoạn giải thích tại sao không có điều kiện uniformity, định nghĩa BQP sẽ trở nên "quá mạnh" (non-uniform).
Ngày 492: Promise Problems
Mục tiêu: Học khái niệm kỹ thuật cần thiết để phát biểu chính xác BQP-complete problems.
Lý thuyết: Bài toán hứa hẹn (promise problem) - chỉ cam kết đúng trên tập input thỏa điều kiện nhất định.
Thực hành: Nhận diện Deutsch-Jozsa (Giai đoạn 4, Module 4.1) là 1 promise problem - nêu rõ "lời hứa" ở đây là gì.
Ngày 493: BQP-complete Problems
Mục tiêu: Làm quen khái niệm bài toán khó nhất trong BQP.
Lý thuyết: Bài toán mô phỏng mạch lượng tử (quantum circuit simulation với ngưỡng xác suất cho trước) là BQP-complete.
Thực hành: Đọc tóm tắt về BQP-completeness, ghi chú ý nghĩa (tương tự vai trò SAT với NP-completeness, Giai đoạn 0 Ngày 82).
Ngày 494: Ôn tập BQP - Phần 1
Mục tiêu: Củng cố ngày 481–493.
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập.
Ngày 495: Amplitude Estimation và Mối liên hệ với BQP
Mục tiêu: Mở rộng hiểu biết về công cụ tổng quát hóa Grover (sẽ gặp lại ở Giai đoạn 10 - QML).
Lý thuyết: Amplitude estimation kết hợp Grover với Phase Estimation (Giai đoạn 4, Ngày 432–437) để ước lượng xác suất thành công mà không cần đo lặp lại nhiều lần.
Thực hành: Đọc tóm tắt ý tưởng amplitude estimation, ghi chú liên hệ với 2 kỹ thuật đã học.
Ngày 496: Search vs Decision Problems trong BQP
Mục tiêu: Phân biệt 2 dạng bài toán và cách chúng liên hệ với nhau.
Lý thuyết: BQP theo định nghĩa chuẩn là lớp bài toán quyết định (yes/no); các bài toán tìm kiếm (như factoring) được xử lý qua self-reducibility.
Thực hành: Viết 1 đoạn giải thích cách chuyển bài toán "tìm 1 thừa số của N" thành chuỗi bài toán quyết định "N có thừa số nhỏ hơn k hay không".
Ngày 497: Chuẩn hóa lại Thuật toán Giai đoạn 4 dưới Góc nhìn Complexity Class
Mục tiêu: Tổng hợp lại toàn bộ Giai đoạn 4 bằng ngôn ngữ lý thuyết độ phức tạp.
Lý thuyết: Không có thêm.
Thực hành: Lập bảng: từng thuật toán (Deutsch-Jozsa, Bernstein-Vazirani, Simon, Grover, Shor) - bài toán giải quyết, độ phức tạp cổ điển, độ phức tạp lượng tử, lớp phức tạp liên quan.
Ngày 498: Đọc bổ sung - Watrous, "Quantum Computational Complexity"
Mục tiêu: Tiếp cận tài liệu survey chuẩn của ngành.
Lý thuyết: Đọc phần về BQP trong survey của John Watrous (có sẵn công khai trên arXiv).
Thực hành: Ghi chú tổng hợp 2 trang.
Ngày 499: Ôn tập Tổng hợp BQP
Mục tiêu: Củng cố toàn bộ Phần A.
Lý thuyết: Vẽ sơ đồ tư duy tổng thể về BQP.
Thực hành: 10 bài tập tổng hợp.
Ngày 500: Kiểm tra kiến thức Phần A
Mục tiêu: Tự đánh giá trước khi sang QMA.
Lý thuyết: Không có.
Thực hành: Bài test 15 câu bao quát Phần A (BQP).
PHẦN B - QMA: QUANTUM MERLIN-ARTHUR (Ngày 501–515)
Ngày 501: Giới thiệu QMA
Mục tiêu: Học phiên bản lượng tử của NP - lớp phức tạp cho bài toán "verification dễ, tìm kiếm khó".
Lý thuyết: Trực giác: Merlin (không giới hạn quyền lực) gửi 1 "chứng cứ" (witness) lượng tử; Arthur (giới hạn polynomial) kiểm tra bằng mạch lượng tử.
Thực hành: Ôn lại định nghĩa NP (Giai đoạn 0, Ngày 81), viết song song định nghĩa trực giác QMA.
Ngày 502: Định nghĩa Hình thức QMA
Mục tiêu: Thành thạo phát biểu chính xác.
Lý thuyết: L ∈ QMA nếu tồn tại mạch verifier V polynomial-size sao cho: x∈L ⟹ tồn tại witness |ψ⟩ để V chấp nhận với xác suất ≥ 2/3; x∉L ⟹ với mọi witness, V chấp nhận với xác suất ≤ 1/3.
Thực hành: Viết lại định nghĩa bằng ký hiệu toán học của riêng bạn.
Ngày 503: So sánh QMA vs NP - Vai trò Witness
Mục tiêu: Hiểu điểm khác biệt cốt lõi: witness trong QMA là 1 trạng thái lượng tử (có thể là superposition), không phải chuỗi bit cổ điển.
Lý thuyết: Witness lượng tử có thể mang "nhiều thông tin hơn" bit cổ điển theo nghĩa Hilbert space, nhưng Holevo bound (Giai đoạn 2) vẫn giới hạn thông tin trích xuất được.
Thực hành: Viết 1 đoạn giải thích: witness lượng tử có mạnh hơn witness cổ điển hay không, và tại sao đây vẫn là câu hỏi mở một phần (liên hệ QCMA, Phần C).
Ngày 504: QMA vs MA
Mục tiêu: So sánh với lớp trung gian - Merlin-Arthur cổ điển (witness cổ điển, verifier ngẫu nhiên hóa cổ điển).
Lý thuyết: MA ⊆ QMA (đã biết); quan hệ ngược lại chưa rõ.
Thực hành: Vẽ sơ đồ bao hàm cập nhật: NP, MA, QMA, BQP.
Ngày 505: Completeness và Soundness trong QMA
Mục tiêu: Nắm chắc 2 điều kiện định nghĩa (tương tự completeness/soundness trong proof system cổ điển).
Lý thuyết: Completeness: instance đúng luôn có witness thuyết phục được verifier; Soundness: instance sai thì không witness nào thuyết phục được verifier (xác suất thấp).
Thực hành: Với 1 bài toán QMA cụ thể (Local Hamiltonian, xem trước Ngày 507), xác định rõ đâu là completeness case, đâu là soundness case.
Ngày 506: QMA-complete Problems - Giới thiệu
Mục tiêu: Làm quen khái niệm bài toán khó nhất trong QMA.
Lý thuyết: Local Hamiltonian Problem là bài toán QMA-complete kinh điển nhất (tương tự vai trò SAT với NP).
Thực hành: Đọc giới thiệu ngắn về Local Hamiltonian Problem, ghi chú lý do nó quan trọng (liên hệ trực tiếp vật lý - tìm trạng thái năng lượng thấp nhất của hệ lượng tử).
Ngày 507: Local Hamiltonian Problem - Phát biểu Chi tiết
Mục tiêu: Hiểu chính xác phát biểu bài toán.
Lý thuyết: Cho Hamiltonian H = ΣH_i (mỗi H_i tác động lên vài qubit "cục bộ"), quyết định xem giá trị riêng nhỏ nhất của H nhỏ hơn a hay lớn hơn b (với b-a ≥ 1/poly(n)).
Thực hành: Viết ví dụ 1 Hamiltonian đơn giản (tổng của vài toán tử Pauli cục bộ) trên hệ 3 qubit.
Ngày 508: Kitaev's Theorem - Giới thiệu Sơ lược
Mục tiêu: Biết đến kết quả nền tảng (không cần chứng minh đầy đủ).
Lý thuyết: Kitaev chứng minh Local Hamiltonian Problem là QMA-complete, dùng kỹ thuật "history state" mã hóa toàn bộ lịch sử tính toán của 1 mạch lượng tử vào 1 trạng thái duy nhất.
Thực hành: Đọc tóm tắt ý tưởng history state construction, ghi chú (không cần thuộc chi tiết kỹ thuật).
Ngày 509: Ứng dụng QMA - Liên hệ Quantum Chemistry
Mục tiêu: Thấy trước ứng dụng thực tế sẽ gặp lại ở Giai đoạn 10 (VQE - Variational Quantum Eigensolver).
Lý thuyết: Tìm trạng thái năng lượng thấp nhất (ground state energy) của phân tử chính là 1 dạng Local Hamiltonian Problem.
Thực hành: Viết 1 đoạn liên hệ giữa QMA-hardness của ground state energy problem và động lực phát triển thuật toán VQE.
Ngày 510: QMA(2) và Multiple Provers - Giới thiệu Sơ lược
Mục tiêu: Mở rộng hiểu biết sang biến thể với nhiều witness không entangled với nhau.
Lý thuyết: QMA(2) - 2 witness riêng biệt (không được phép entangled), câu hỏi QMA(2) = QMA? vẫn còn mở.
Thực hành: Đọc tóm tắt ngắn về QMA(2), ghi chú 5 dòng.
Ngày 511: Amplification cho QMA
Mục tiêu: Hiểu kỹ thuật giảm sai số cho QMA, có điểm tinh tế hơn BQP.
Lý thuyết: Không thể đơn giản lặp lại và lấy đa số như BQP vì witness có thể khác nhau mỗi lần; cần kỹ thuật "witness repetition" cẩn thận hơn.
Thực hành: Đọc tóm tắt kỹ thuật amplification cho QMA, ghi chú điểm khác biệt so với BQP (Ngày 484).
Ngày 512: Ôn tập QMA - Phần 1
Mục tiêu: Củng cố ngày 501–511.
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập.
Ngày 513: Đọc bổ sung về QMA
Mục tiêu: Lấp lỗ hổng lý thuyết trước khi kiểm tra.
Lý thuyết: Đọc phần QMA trong survey Watrous, hoặc chương tương ứng trong Kitaev-Shen-Vyalyi "Classical and Quantum Computation".
Thực hành: Ghi chú tổng hợp 2 trang.
Ngày 514: Ôn tập Tổng hợp QMA
Mục tiêu: Kết nối định nghĩa → completeness/soundness → Local Hamiltonian → ứng dụng.
Lý thuyết: Vẽ sơ đồ tổng thể.
Thực hành: 8 bài tập tổng hợp.
Ngày 515: Kiểm tra kiến thức Phần B
Mục tiêu: Tự đánh giá trước khi sang các lớp phức tạp khác.
Lý thuyết: Không có.
Thực hành: Bài test 15 câu bao quát Phần B (QMA).
PHẦN C - CÁC LỚP PHỨC TẠP LƯỢNG TỬ KHÁC (Ngày 516–525)
Ngày 516: QCMA - Quantum Classical Merlin-Arthur
Mục tiêu: Học biến thể trung gian giữa NP và QMA.
Lý thuyết: QCMA - witness là chuỗi bit cổ điển, nhưng verifier là mạch lượng tử.
Thực hành: Viết sơ đồ so sánh 4 lớp: NP (witness cổ điển, verify cổ điển), MA (witness cổ điển, verify ngẫu nhiên cổ điển), QCMA (witness cổ điển, verify lượng tử), QMA (witness lượng tử, verify lượng tử).
Ngày 517: So sánh QCMA vs QMA - Câu hỏi Mở
Mục tiêu: Hiểu đây là 1 trong các câu hỏi mở quan trọng của lĩnh vực.
Lý thuyết: QCMA ⊆ QMA hiển nhiên; QCMA = QMA? chưa được biết - tức chưa rõ witness lượng tử có thực sự mạnh hơn witness cổ điển hay không khi verifier đã là lượng tử.
Thực hành: Viết 1 đoạn tóm tắt tại sao câu hỏi này khó và quan trọng.
Ngày 518: QIP - Quantum Interactive Polynomial Time
Mục tiêu: Mở rộng sang mô hình có tương tác nhiều vòng (interactive proof), không chỉ 1 witness tĩnh.
Lý thuyết: QIP tổng quát hóa QMA bằng cách cho phép Arthur và Merlin trao đổi nhiều vòng thông tin lượng tử.
Thực hành: Đọc tóm tắt định nghĩa QIP, so sánh với QMA (chỉ 1 vòng witness → verify).
Ngày 519: QIP = PSPACE - Giới thiệu Kết quả Nổi tiếng
Mục tiêu: Biết đến 1 trong các kết quả đẹp nhất của lý thuyết độ phức tạp lượng tử.
Lý thuyết: Định lý (Jain-Ji-Upadhyay-Watrous, 2009): QIP = PSPACE - tương tác lượng tử không mạnh hơn tương tác cổ điển tổng quát (IP = PSPACE cũng đã biết trước đó).
Thực hành: Đọc tóm tắt kết quả, ghi chú ý nghĩa: dù có tương tác lượng tử, không "vượt" được PSPACE.
Ngày 520: BQP/qpoly và Advice Classes - Giới thiệu Sơ lược
Mục tiêu: Làm quen khái niệm lớp phức tạp với "advice" (thông tin phụ trợ không phụ thuộc input).
Lý thuyết: BQP/qpoly - BQP với advice lượng tử polynomial-size, không phụ thuộc vào input cụ thể.
Thực hành: Đọc tóm tắt ngắn, ghi chú 5 dòng liên hệ với khái niệm advice cổ điển P/poly.
Ngày 521: Quantum PCP Conjecture
Mục tiêu: Biết đến 1 trong các giả thuyết mở lớn nhất của lĩnh vực (tương tự PCP theorem cổ điển).
Lý thuyết: Giả thuyết Quantum PCP - mở rộng PCP theorem cổ điển sang QMA, vẫn chưa được chứng minh hay bác bỏ; liên hệ trực tiếp tới Local Hamiltonian Problem (Ngày 507) với "gap" cố định.
Thực hành: Đọc tóm tắt giả thuyết, ghi chú tại sao nó được coi là 1 trong những bài toán mở quan trọng nhất (liên hệ Giai đoạn 12 - Research Frontier).
Ngày 522: Sơ đồ Tổng thể các Lớp Phức tạp Lượng tử
Mục tiêu: Tổng hợp toàn bộ bức tranh đã học.
Lý thuyết: Không có thêm.
Thực hành: Tự vẽ 1 sơ đồ Venn hoàn chỉnh gồm: P, NP, BPP, MA, PSPACE, BQP, QCMA, QMA, QIP, không nhìn tài liệu.
Ngày 523: So sánh Lớp Phức tạp Cổ điển vs Lượng tử - Bảng Tổng hợp
Mục tiêu: Củng cố bằng cách hệ thống hóa dưới dạng bảng.
Lý thuyết: Không có thêm.
Thực hành: Lập bảng đối chiếu song song: P↔BQP, NP↔QMA, MA↔QCMA, IP↔QIP, nêu rõ quan hệ đã biết/chưa biết cho mỗi cặp.
Ngày 524: Ôn tập Tổng hợp Phần C
Mục tiêu: Củng cố ngày 516–523.
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập tổng hợp.
Ngày 525: Kiểm tra kiến thức Phần C
Mục tiêu: Tự đánh giá trước khi sang Oracle Separations.
Lý thuyết: Không có.
Thực hành: Bài test 12 câu bao quát Phần C.
PHẦN D - ORACLE SEPARATIONS (Ngày 526–540)
Ngày 526: Oracle Separations - Khái niệm
Mục tiêu: Học kỹ thuật chính dùng để so sánh sức mạnh tương đối giữa các lớp phức tạp khi không thể chứng minh trực tiếp.
Lý thuyết: Cho cả 2 mô hình tính toán quyền truy cập vào cùng 1 oracle (black box); nếu tồn tại oracle làm 2 lớp phức tạp khác nhau, đó là bằng chứng "tương đối" (relative) về sự khác biệt.
Thực hành: Đọc Nielsen & Chuang mục 6.5 (hoặc phần liên quan), ghi chú định nghĩa oracle separation.
Ngày 527: Relativized World - Ý nghĩa và Giới hạn
Mục tiêu: Hiểu rõ oracle separation KHÔNG chứng minh được sự khác biệt trong "thế giới thật" (unrelativized).
Lý thuyết: Kết quả trong thế giới có oracle không nhất thiết đúng khi bỏ oracle đi - đây là lý do P vs NP chưa giải quyết được bằng kỹ thuật này.
Thực hành: Viết 1 đoạn giải thích sự khác biệt giữa "chứng minh tuyệt đối" và "chứng minh tương đối qua oracle".
Ngày 528: Baker-Gill-Solovay Theorem
Mục tiêu: Biết đến kết quả kinh điển minh họa giới hạn của relativization.
Lý thuyết: Tồn tại oracle A sao cho P^A = NP^A, và tồn tại oracle B sao cho P^B ≠ NP^B - do đó kỹ thuật relativization một mình không thể giải quyết P vs NP.
Thực hành: Đọc tóm tắt định lý, ghi chú ý nghĩa đối với việc chọn phương pháp nghiên cứu trong lý thuyết độ phức tạp.
Ngày 529: Simon's Problem như Oracle Separation Đầu tiên
Mục tiêu: Kết nối trực tiếp với Giai đoạn 4 (Module 4.3) - nhìn lại Simon's algorithm dưới góc độ lý thuyết độ phức tạp.
Lý thuyết: Simon's problem cung cấp oracle separation đầu tiên giữa BQP và BPP (tách biệt exponential).
Thực hành: Viết lại lập luận: vì sao độ phức tạp Ω(2^(n/2)) cổ điển vs O(n) lượng tử (Giai đoạn 4, Ngày 382) chính là 1 oracle separation.
Ngày 530: Chi tiết - Simon's Oracle Separation
Mục tiêu: Đào sâu chứng minh lower bound cổ điển cho Simon's problem.
Lý thuyết: Chứng minh (sơ lược) bất kỳ thuật toán cổ điển ngẫu nhiên nào cũng cần Ω(2^(n/2)) truy vấn oracle để giải Simon's problem, dùng lập luận kiểu birthday paradox (Giai đoạn 4, Ngày 382).
Thực hành: Viết lại lập luận lower bound bằng ngôn ngữ xác suất của riêng bạn.
Ngày 531: Recursive Fourier Sampling
Mục tiêu: Làm quen 1 oracle separation khác trong lịch sử ngành (giới thiệu sơ lược).
Lý thuyết: Bài toán do Bernstein-Vazirani đề xuất, cho ưu thế lượng tử theo cấp số mũ trong mô hình query, là bước đệm lịch sử trước Simon.
Thực hành: Đọc tóm tắt ngắn về Recursive Fourier Sampling, ghi chú 5 dòng.
Ngày 532: Forrelation - Oracle Separation Mạnh nhất Được biết
Mục tiêu: Biết đến kết quả hiện đại hơn (Aaronson-Ambainis).
Lý thuyết: Forrelation cho oracle separation gần như tối đa có thể giữa độ phức tạp truy vấn lượng tử và cổ điển (gần polynomial vs exponential ở dạng mạnh nhất).
Thực hành: Đọc tóm tắt ý tưởng Forrelation, ghi chú (không cần chứng minh chi tiết).
Ngày 533: Quantum Query Complexity
Mục tiêu: Học mô hình chính xác dùng để đo lường các oracle separation đã gặp.
Lý thuyết: Đếm số lần gọi oracle (query) thay vì đếm tổng số gate - mô hình đơn giản hóa hữu ích để chứng minh lower bound.
Thực hành: Tính quantum query complexity của Deutsch-Jozsa, Grover, Simon (đã học ở Giai đoạn 4) theo mô hình này.
Ngày 534: Lower Bounds cho Quantum Query Complexity - Polynomial Method
Mục tiêu: Làm quen 1 kỹ thuật chứng minh lower bound quan trọng (giới thiệu sơ lược).
Lý thuyết: Biểu diễn xác suất output như 1 đa thức bậc thấp theo input, dùng giới hạn bậc đa thức để suy ra giới hạn số query.
Thực hành: Đọc tóm tắt ý tưởng polynomial method, ghi chú (không cần tự chứng minh 1 lower bound cụ thể).
Ngày 535: Adversary Method
Mục tiêu: Làm quen kỹ thuật chứng minh lower bound thứ hai (giới thiệu sơ lược).
Lý thuyết: Xây dựng 1 "đối thủ" (adversary) chọn input để làm khó thuật toán, suy ra giới hạn dưới cho số query cần thiết.
Thực hành: Đọc tóm tắt ý tưởng adversary method, so sánh sơ lược với polynomial method (Ngày 534).
Ngày 536: Ôn tập Oracle Separations
Mục tiêu: Củng cố ngày 526–535.
Lý thuyết: Tổng hợp.
Thực hành: 8 bài tập.
Ngày 537: Đọc bổ sung - Survey về Oracle Separations
Mục tiêu: Lấp lỗ hổng lý thuyết trước khi kiểm tra.
Lý thuyết: Đọc phần liên quan trong survey Watrous hoặc bài giảng Preskill về query complexity.
Thực hành: Ghi chú tổng hợp 2 trang.
Ngày 538: Ôn tập Tổng hợp Phần D
Mục tiêu: Kết nối Oracle Separation → Simon → Query Complexity → Lower Bound Techniques.
Lý thuyết: Vẽ sơ đồ tổng thể.
Thực hành: 10 bài tập tổng hợp.
Ngày 539: Kiểm tra kiến thức Phần D
Mục tiêu: Tự đánh giá tổng thể trước khi tổng kết Giai đoạn 5.
Lý thuyết: Không có.
Thực hành: Bài test 15 câu bao quát Phần D.
Ngày 540: Tổng kết Giai đoạn 5
Mục tiêu: Xác nhận sẵn sàng chuyển sang Giai đoạn 6 (Quantum Error Correction).
Lý thuyết: Ôn lại toàn bộ 4 phần: BQP, QMA, các lớp phức tạp khác, Oracle Separations - nhấn mạnh đây là nền tảng lý thuyết đứng sau mọi tuyên bố "quantum advantage" sẽ gặp lại xuyên suốt phần còn lại của syllabus (đặc biệt Giai đoạn 12 - Research Frontier, quantum supremacy/advantage).
Thực hành: Bài kiểm tra tổng hợp 25 câu bao quát cả Giai đoạn 5; liệt kê 3 điểm yếu nhất cần ôn thêm trước khi chuyển sang chủ đề thực hành nhiều hơn (Quantum Error Correction).