Bạn sẽ học được gì
- Phân tích Deutsch–Jozsa, Bernstein–Vazirani và Simon trong mô hình truy vấn, nêu rõ tách biệt so với thuật toán cổ điển tất định và ngẫu nhiên
- Dựng mạch biến đổi Fourier lượng tử, phân tích số cổng và dùng nó trong ước lượng pha
- Trình bày thuật toán Shor từ tìm chu kỳ tới phân số liên tục, cài đặt cho N nhỏ và nêu các giả thiết của ước lượng tài nguyên
- Chứng minh thuật toán Grover cần cỡ (π/4)√N lần lặp, áp dụng khuếch đại biên độ và giải thích vì sao tăng tốc căn bậc hai là tối ưu
- Mô tả bước ngẫu nhiên lượng tử liên tục và rời rạc và thuật toán tìm kiếm dựa trên bước ngẫu nhiên
- Mô phỏng Hamiltonian bằng công thức tích Trotter, ước lượng sai số theo số bước và so với phương pháp mới
- Đánh giá có phê phán một tuyên bố tăng tốc lượng tử: mô hình chi phí, thuật toán cổ điển đối chiếu, chi phí nạp dữ liệu và sửa lỗi
Nên học trước
Giới thiệu
Thuật toán lượng tử trả lời câu hỏi cốt lõi của ngành: máy tính lượng tử nhanh hơn ở đâu, nhanh hơn bao nhiêu, và với giả thiết nào? Chủ đề đi qua các họ thuật toán chính theo ghi chép thuật toán lượng tử của Andrew Childs và MIT 8.371 (Quantum Information Science II).
Ý tưởng chung: giao thoa có chủ đích
Một thuật toán lượng tử tốt không "thử mọi đáp án cùng lúc". Nó chuẩn bị chồng chập, để một hộp đen (oracle) ghi thông tin vào pha, rồi dùng giao thoa để các đường dẫn tới đáp án sai triệt tiêu nhau. Vì vậy tăng tốc thường được đo trong mô hình truy vấn (đếm số lần gọi oracle) hoặc bằng số cổng; khi so với thuật toán cổ điển, phải nói rõ so với thuật toán cổ điển tốt nhất đã biết hay với cận dưới đã chứng minh.
Họ Fourier: từ Simon tới Shor
- Deutsch–Jozsa, Bernstein–Vazirani, Simon: các bài toán "đồ chơi" nhưng cho thấy tách biệt rõ ràng trong mô hình truy vấn; bài toán Simon cần số truy vấn tăng theo hàm mũ với mọi thuật toán cổ điển ngẫu nhiên nhưng chỉ tuyến tính với thuật toán lượng tử.
- Biến đổi Fourier lượng tử (QFT) trên n qubit chỉ cần cỡ n² cổng, nhưng không cho ta đọc được toàn bộ phổ Fourier; nó là bộ phận của ước lượng pha: ước lượng trị riêng exp(2πiφ) của một unita với độ chính xác t bit dùng cỡ t qubit phụ.
- Thuật toán Shor quy phân tích thừa số về tìm chu kỳ của hàm aˣ mod N, giải bằng ước lượng pha rồi phân số liên tục. Số cổng tăng theo đa thức của số bit n (cỡ n³ với phép nhân thông thường), trong khi thuật toán cổ điển tốt nhất đã biết (sàng trường số) chạy trong thời gian dưới hàm mũ nhưng trên đa thức. Không ai chứng minh được phân tích thừa số là khó với máy cổ điển; tăng tốc so với thuật toán đã biết. Cùng khung đó giải logarit rời rạc (cả trên đường cong elliptic) và bài toán nhóm con ẩn giao hoán; với nhóm không giao hoán, phần lớn vẫn là câu hỏi mở.
Về tài nguyên thực tế: một ước lượng năm 2025 của Craig Gidney cho rằng phá RSA-2048 cần dưới một triệu qubit vật lý chạy dưới một tuần, với giả thiết lỗi cổng khoảng 0,1 %, chu kỳ sửa lỗi 1 µs và kết nối lân cận trên mặt phẳng — xa hơn nhiều so với máy hiện có, nhưng đủ gần để ngành mật mã chuyển sang mật mã hậu lượng tử.
Grover và khuếch đại biên độ
Tìm một phần tử đánh dấu trong N phần tử không có cấu trúc cần khoảng (π/4)√N lần gọi oracle thay vì cỡ N; với N = 2²⁰ là khoảng 804 lần. Tăng tốc chỉ là căn bậc hai, và đã được chứng minh là tối ưu (không thuật toán lượng tử nào dùng ít hơn cỡ √N truy vấn). Khuếch đại biên độ tổng quát hóa Grover cho mọi thuật toán có xác suất thành công p, giảm số lần lặp từ cỡ 1/p xuống cỡ 1/√p. Khi tính cả chi phí sửa lỗi, tăng tốc này khó thành lợi thế thực tế.
Bước ngẫu nhiên và mô phỏng Hamiltonian
Bước ngẫu nhiên lượng tử (liên tục và rời rạc) lan nhanh hơn bước ngẫu nhiên cổ điển trên một số đồ thị và cho thuật toán tìm kiếm trên đồ thị. Mô phỏng Hamiltonian — ý tưởng ban đầu của Feynman — có lẽ là ứng dụng hữu ích sớm nhất: công thức tích Trotter chia exp(−iHt) thành nhiều bước ngắn, các phương pháp mới như xử lý tín hiệu lượng tử đạt chi phí gần tối ưu. Thuật toán HHL cho hệ phương trình tuyến tính chỉ tăng tốc hàm mũ khi thỏa nhiều điều kiện chặt (xem phần khái niệm).
Nên học thế nào
- Sách chính là ghi chép của Childs (miễn phí), đọc Preliminaries, Phần II (Fourier, ước lượng pha, logarit rời rạc, nhóm con ẩn), Phần III (bước ngẫu nhiên) và Phần V (mô phỏng). Giáo trình của Kaye, Laflamme và Mosca viết chứng minh cẩn thận hơn cho người mới; khóa Fundamentals of quantum algorithms trên IBM Quantum Learning có video và bài Qiskit.
- Cài đặt từng thuật toán trên trình mô phỏng với số qubit nhỏ, rồi đếm số cổng khi tăng kích thước để thấy tỉ lệ tăng.
- Luôn ghi giả thiết: mô hình truy vấn hay số cổng, so với thuật toán tốt nhất đã biết hay cận dưới, dữ liệu nạp vào thế nào.
Chủ đề cần Cơ sở tính toán lượng tử, phân tích thuật toán và số học đồng dư (lý thuyết số); sau đó là Độ phức tạp tính toán lượng tử và Thuật toán lượng tử biến phân.
Giáo trình & sách tham khảo
Xem tất cả trong tab SáchGiáo trình chính
Lecture Notes on Quantum Algorithms
Andrew M. Childs
Vì sao chọn: Ghi chép thuật toán lượng tử của Andrew Childs (University of Maryland), miễn phí, không ghi giấy phép mở: mạch lượng tử, Fourier lượng tử và ước lượng pha, nhóm con ẩn, bước ngẫu nhiên, độ phức tạp truy vấn, mô phỏng Hamiltonian và tính toán đoạn nhiệt. Chọn làm sách chính vì bao quát, cập nhật và chính xác.
Nên đọc: Preliminaries; Chương 4–7, 17–20, 27–29
Quantum Computing: Lecture Notes
Ronald de Wolf · 2026
Ghi chép của Ronald de Wolf, ngắn gọn và có bài tập cho Simon, Fourier lượng tử, Shor, Grover và bước ngẫu nhiên; hợp để ôn nhanh trước khi đọc Childs. Miễn phí trên arXiv (giấy phép phân phối không độc quyền); số chương thay đổi theo phiên bản nên không ghi.
An Introduction to Quantum Computing
Phillip Kaye, Raymond Laflamme, Michele Mosca · 2006
Giáo trình của Kaye, Laflamme và Mosca (Oxford University Press) tập trung vào thuật toán với chứng minh viết cẩn thận: thuật toán nhập môn, thuật toán tăng tốc trên đa thức (Shor) và thuật toán dựa trên khuếch đại biên độ. Sách trả phí, hợp với người mới hơn Childs.
Nên đọc: Chương 6–8
Quantum Computation and Quantum Information
Michael A. Nielsen, Isaac L. Chuang · 2010 · Bản kỷ niệm 10 năm
Giáo trình chuẩn của Nielsen và Chuang; chương về biến đổi Fourier lượng tử và ứng dụng (ước lượng pha, tìm cấp, phân tích thừa số) vẫn là tài liệu tham khảo kinh điển. Sách trả phí.
Nên đọc: Chương 5
Các bước học
Đăng nhập để đánh dấu các bước đã hoàn thành.
Bước 1: Mô hình truy vấn và các thuật toán đầu tiên
khoảng 11 giờHọc mô hình truy vấn, pha kickback, Deutsch–Jozsa, Bernstein–Vazirani và Simon. Ôn nhanh bằng bài Giới thiệu thuật toán lượng tử của khóa Nhập môn Khoa học Thông tin Lượng tử trên trang. Bài tập: cài đặt Bernstein–Vazirani cho chuỗi ẩn 8 bit trong Qiskit và kiểm tra chỉ cần một truy vấn; cài đặt Simon với n = 3 và giải hệ phương trình tuyến tính trên GF(2) từ các kết quả đo; so số truy vấn với lời giải cổ điển.
- Đọc: Preliminaries — Lecture Notes on Quantum Algorithms
- Đọc: Chương 6 Introductory Quantum Algorithms — An Introduction to Quantum Computing
Bước 2: Biến đổi Fourier lượng tử và ước lượng pha
khoảng 11 giờHọc QFT trên nhóm cyclic, mạch QFT, QFT xấp xỉ và ước lượng pha. Bài tập: dựng mạch QFT 4 qubit, kiểm tra với ma trận Fourier rời rạc của NumPy; chạy ước lượng pha với U = Rz(θ) và 3, 5, 7 qubit phụ, vẽ phân bố kết quả khi φ không biểu diễn đúng được bằng số bit hữu hạn; đếm số cổng khi bỏ các phép quay nhỏ hơn π/2⁴.
- Đọc: Chương 4 The abelian quantum Fourier transform and phase estimation — Lecture Notes on Quantum Algorithms
- Đọc: Chương 5 The quantum Fourier transform and its applications — Quantum Computation and Quantum Information
Bước 3: Thuật toán Shor, logarit rời rạc và nhóm con ẩn
khoảng 13 giờHọc tìm cấp bằng ước lượng pha, phân số liên tục, quy phân tích thừa số về tìm cấp, logarit rời rạc và bài toán nhóm con ẩn giao hoán; đọc lướt chương về tấn công mật mã đường cong elliptic. Bài tập: với N = 15 và N = 21, chạy toàn bộ phần xử lý cổ điển (chọn a, tìm cấp bằng mô phỏng, phân số liên tục, ước chung lớn nhất); mô phỏng phần lượng tử cho N = 15; đọc ước lượng tài nguyên RSA-2048 năm 2025 của Craig Gidney và liệt kê mọi giả thiết phần cứng của nó.
- Đọc: Chương 5 Discrete log and the hidden subgroup problem; Chương 6 The abelian HSP and decomposing abelian groups; Chương 7 Quantum attacks on elliptic curve cryptography (đọc lướt) — Lecture Notes on Quantum Algorithms
- Đọc: Chương 7 Algorithms With Superpolynomial Speed-Up — An Introduction to Quantum Computing
Bước 4: Grover và khuếch đại biên độ
khoảng 10 giờHọc thuật toán Grover dưới góc nhìn hình học (phép quay trong mặt phẳng hai chiều), số lần lặp tối ưu, trường hợp nhiều phần tử đánh dấu, khuếch đại biên độ và đếm lượng tử. Bài tập: cài đặt Grover 3 và 4 qubit, vẽ xác suất thành công theo số lần lặp để thấy nó giảm khi lặp quá; tính số lần lặp cho N = 2²⁰ (khoảng 804); ước lượng xem với thời gian mỗi lần lặp 1 ms trên máy chịu lỗi, Grover cần N lớn cỡ nào mới thắng một máy cổ điển kiểm tra 10⁹ phần tử mỗi giây.
- Đọc: Chương 8 Algorithms Based on Amplitude Amplification — An Introduction to Quantum Computing
- Đọc: Chương 19 Unstructured search — Lecture Notes on Quantum Algorithms
Bước 5: Bước ngẫu nhiên lượng tử
khoảng 7 giờHọc bước ngẫu nhiên lượng tử liên tục và rời rạc và thuật toán tìm kiếm dựa trên bước ngẫu nhiên. Bài tập NumPy: mô phỏng bước ngẫu nhiên lượng tử liên tục trên đường thẳng và so độ lan (tỉ lệ với t) với bước ngẫu nhiên cổ điển (tỉ lệ với √t); mô phỏng tìm kiếm bằng bước ngẫu nhiên trên đồ thị đầy đủ.
- Đọc: Chương 17 Continuous-time quantum walk; Chương 18 Discrete-time quantum walk; Chương 20 Quantum walk search — Lecture Notes on Quantum Algorithms
Bước 6: Mô phỏng Hamiltonian
khoảng 10 giờHọc mô phỏng động học Hamiltonian bằng công thức tích Trotter bậc một và bậc hai, các phương pháp mới và xử lý tín hiệu lượng tử ở mức ý tưởng. Bài tập: với chuỗi Ising ngang 6 spin, so exp(−iHt) chính xác (NumPy) với công thức Trotter bậc một và bậc hai theo số bước r; vẽ sai số theo r trên thang logarit để thấy độ dốc −1 và −2; dựng mạch một bước Trotter trong Qiskit và đếm số CNOT.
- Đọc: Chương 27 Simulating Hamiltonian dynamics; Chương 28 Fast quantum simulation algorithms; Chương 29 Quantum signal processing (đọc lướt) — Lecture Notes on Quantum Algorithms
Bước 7: Dự án: đánh giá một tuyên bố tăng tốc
khoảng 8 giờChọn một ứng dụng được quảng bá (ví dụ hệ phương trình tuyến tính bằng HHL, tối ưu hóa danh mục đầu tư, tìm kiếm cơ sở dữ liệu). Viết báo cáo ba trang: mô hình chi phí, thuật toán cổ điển tốt nhất để so, chi phí nạp dữ liệu vào trạng thái lượng tử, cách đọc kết quả ra, và ước lượng thô số qubit logic, số cổng khi tính cả sửa lỗi. Kèm một bản cài đặt thu nhỏ trên trình mô phỏng; có thể dùng các bài của khóa Fundamentals of quantum algorithms trên IBM Quantum Learning làm mẫu.
Khái niệm chính
- Mô hình truy vấn
- Mô hình chi phí đếm số lần gọi hộp đen (oracle) cài đặt hàm cần khảo sát; cho phép chứng minh cận dưới và tách biệt chặt chẽ giữa thuật toán lượng tử và cổ điển, nhưng không nói gì về chi phí cài đặt oracle.
- Phase kickback
- Kỹ thuật đặt qubit đích ở trạng thái riêng của oracle để giá trị hàm được ghi vào pha của thanh ghi điều khiển, (−1)ᶠ⁽ˣ⁾|x⟩; là cơ chế chung của Deutsch–Jozsa, Grover và ước lượng pha.
- Bài toán Simon
- Tìm chuỗi bit ẩn s khi biết f(x) = f(y) đúng khi y = x hoặc y = x ⊕ s; thuật toán lượng tử cần cỡ n truy vấn còn mọi thuật toán cổ điển ngẫu nhiên cần cỡ √(2ⁿ), và đã gợi ý cho Shor.
- Biến đổi Fourier lượng tử
- Biến đổi unita ánh xạ |x⟩ thành tổng các |y⟩ với pha exp(2πixy/N); với N = 2ⁿ cài đặt được bằng cỡ n² cổng (ít hơn nếu bỏ các phép quay rất nhỏ), nhưng biên độ Fourier không đọc trực tiếp ra được.
- Ước lượng pha
- Thuật toán ước lượng φ trong trị riêng exp(2πiφ) của unita U khi có trạng thái riêng tương ứng, dùng các lũy thừa U, U², U⁴, … có điều khiển và QFT nghịch; là lõi của Shor, của mô phỏng hóa học và nhiều thuật toán khác.
- Tìm chu kỳ và thuật toán Shor
- Phân tích N quy về tìm cấp r của a mod N; ước lượng pha trên phép nhân modulo cho một xấp xỉ của s/r, phân số liên tục khôi phục r, rồi ước chung lớn nhất của a lũy thừa r/2 cộng hoặc trừ 1 với N cho thừa số với xác suất cao.
- Bài toán nhóm con ẩn (HSP)
- Khung tổng quát chứa tìm chu kỳ, logarit rời rạc và Simon: tìm nhóm con H khi biết hàm hằng trên mỗi lớp kề của H; giải hiệu quả với nhóm giao hoán, còn với nhiều nhóm không giao hoán (nhóm đối xứng, nhóm nhị diện) vẫn là bài toán mở.
- Thuật toán Grover
- Tìm phần tử đánh dấu trong N phần tử bằng cỡ (π/4)√N lần lặp phép phản xạ qua trạng thái đánh dấu và qua trạng thái đều; lặp quá số lần tối ưu làm xác suất thành công giảm trở lại.
- Khuếch đại biên độ
- Tổng quát hóa Grover: với một thuật toán thành công với xác suất p, lặp cỡ 1/√p lần phép phản xạ thích hợp nâng xác suất thành công lên gần 1, thay vì lặp lại cỡ 1/p lần như cổ điển.
- Cận dưới √N của tìm kiếm
- Kết quả của Bennett, Bernstein, Brassard và Vazirani (1997): mọi thuật toán lượng tử tìm kiếm không cấu trúc cần cỡ √N truy vấn, nên Grover là tối ưu và máy tính lượng tử không giải được bài toán NP bằng vét cạn trong thời gian đa thức theo cách này.
- Bước ngẫu nhiên lượng tử
- Tương tự lượng tử của bước ngẫu nhiên trên đồ thị, dạng liên tục (tiến hóa theo exp(−iAt) với A là ma trận kề) hoặc rời rạc (có đồng xu); lan truyền nhanh hơn trên một số đồ thị và cho thuật toán tìm kiếm, bài toán phân biệt phần tử.
- Công thức tích Trotter
- Xấp xỉ exp(−i(A+B)t) bằng (exp(−iAt/r)·exp(−iBt/r))ʳ; với công thức bậc một, sai số tỉ lệ cỡ t²/r nên số bước cần tăng theo t²/ε; công thức bậc cao và phương pháp xử lý tín hiệu lượng tử giảm chi phí đáng kể.
- Thuật toán HHL
- Thuật toán lượng tử cho hệ phương trình tuyến tính Ax = b trả về trạng thái tỉ lệ với nghiệm; tăng tốc hàm mũ chỉ đạt được khi A thưa, có số điều kiện nhỏ, b nạp được hiệu quả và chỉ cần một đại lượng thống kê của nghiệm chứ không cần đọc hết nghiệm.
Học xong để làm gì
- Đánh giá rủi ro với mật mã khóa công khai (RSA, đường cong elliptic) và lập kế hoạch chuyển sang mật mã hậu lượng tử
- Mô phỏng phân tử, vật liệu và hệ spin — ứng dụng hữu ích được kỳ vọng sớm nhất của máy tính lượng tử chịu lỗi
- Ước lượng tài nguyên (số qubit logic, số cổng T, thời gian chạy) cho một bài toán ứng dụng cụ thể
- Thẩm định các tuyên bố tăng tốc lượng tử trong tối ưu hóa, tài chính và học máy
- Nền cho độ phức tạp tính toán lượng tử và thuật toán biến phân
Câu hỏi thường gặp
Máy tính lượng tử có giải được bài toán NP-đầy đủ trong thời gian đa thức không?
Không ai biết chắc, nhưng giới nghiên cứu tin là không. Grover chỉ cho tăng tốc căn bậc hai với tìm kiếm vét cạn và cận dưới √N cho thấy không thể làm tốt hơn theo cách đó; chưa có thuật toán lượng tử nào giải một bài toán NP-đầy đủ nhanh hơn hàm mũ.
Shor có phá được RSA ngay bây giờ không?
Không. Các thí nghiệm hiện nay chỉ phân tích những số rất nhỏ, thường với nhiều giản lược. Ước lượng năm 2025 cho RSA-2048 cần dưới một triệu qubit vật lý chạy khoảng một tuần với giả thiết lỗi cổng 0,1 % và sửa lỗi bằng mã bề mặt — lớn hơn nhiều so với máy hiện có. Tuy vậy, dữ liệu mã hóa hôm nay có thể bị lưu lại để giải mã sau, nên việc chuyển sang mật mã hậu lượng tử là cần thiết.
Tôi cần lý thuyết số đến mức nào?
Số học đồng dư, thuật toán Euclid, định lý Euler, cấp của một phần tử và phân số liên tục. Chủ đề Lý thuyết số của lộ trình Toán học có đủ các phần này.
Có cần mua sách không?
Không bắt buộc. Sách chính của Childs và ghi chép của de Wolf miễn phí. Giáo trình của Kaye, Laflamme và Mosca và của Nielsen – Chuang là sách trả phí, thư viện các trường thường có.
70 giờ có đủ không?
Đủ để hiểu và cài đặt các thuật toán chính ở quy mô nhỏ. Một học phần thuật toán lượng tử ở bậc cao học cần khoảng 120–150 giờ với nhiều bài tập chứng minh; phần bài toán nhóm con ẩn không giao hoán, độ phức tạp truy vấn và tính toán đoạn nhiệt trong ghi chép của Childs dành cho người muốn đi sâu.

