Thuật toán Lượng tử: Sức mạnh và Giới hạn

Một máy tính lượng tử chỉ hữu ích bằng đúng các thuật toán mà nó có thể chạy. Suốt ba thập kỷ, các nhà nghiên cứu đã tìm ra một số ít thuật toán nơi máy lượng tử mang lại lợi thế thực sự, cộng với một lớp các phương pháp “lai” (hybrid) được thiết kế cho phần cứng chưa hoàn hảo của ngày nay. Bài viết này giải thích những thuật toán quan trọng nhất cùng bộ máy error correction (sửa lỗi) mà cuối cùng sẽ cho phép chúng chạy ở quy mô lớn. Xuyên suốt, mục tiêu là chính xác về việc mỗi thuật toán thực sự mang lại bao nhiêu mức tăng tốc — bởi vì những khác biệt là rất lớn.

Thuật toán Shor: phân tích thừa số và mối đe dọa với mật mã

Bài toán. Tìm các thừa số nguyên tố của một số lớn. Máy tính cổ điển có thể nhân hai số nguyên tố lớn với nhau một cách dễ dàng, nhưng đảo ngược quá trình đó — phân tích tích trở lại thành các thừa số nguyên tố — được tin là cần thời gian theo hàm mũ. Toàn bộ tính bảo mật của mã hóa RSA, vốn bảo vệ HTTPS, chữ ký số và phần lớn tiền mã hóa, đều dựa trên độ khó này.

Lời giải lượng tử. Thuật toán Shor một cách khéo léo định nghĩa lại bài toán phân tích thừa số thành bài toán tìm chu kỳ (period) của một hàm toán học, một nhiệm vụ mà máy tính lượng tử rất giỏi nhờ phép biến đổi Fourier lượng tử (quantum Fourier transform).

Mức tăng tốc. Theo hàm mũ. Trong khi một phương pháp cổ điển cần xấp xỉ O(exp(∛n)) bước, thuật toán Shor cần khoảng O(n³). Đây chính là mức tăng tốc ngoạn mục đem lại cho điện toán lượng tử danh tiếng đáng gờm của nó.

Đối chiếu với thực tế. Chưa có máy tính lượng tử nào phân tích được một số lớn hơn 21 bằng thuật toán Shor. Một cuộc tấn công hữu hiệu vào RSA-2048 sẽ cần khoảng 1.400 logical qubit (qubit đã được sửa lỗi) — và hàng triệu qubit vật lý trong các thiết kế ban đầu, dù những tối ưu hóa gần đây đã cắt giảm yêu cầu qubit vật lý xuống quanh và dưới mức một triệu. Các khảo sát chuyên gia đặt khả năng xuất hiện một máy tính lượng tử có liên quan về mặt mật mã trong vòng mười năm ở mức xấp xỉ 28–49%. (Xem Quantum Threat Timeline Report 2025.)

Thuật toán Grover: tìm kiếm nhanh hơn

Bài toán. Tìm một mục cụ thể trong một cơ sở dữ liệu không sắp xếp gồm N mục.

Chi phí cổ điển. O(N) — trong trường hợp xấu nhất bạn phải kiểm tra mọi mục.

Chi phí lượng tử. O(√N), sử dụng một kỹ thuật gọi là khuếch đại biên độ (amplitude amplification).

Mức tăng tốc. Bậc hai (quadratic). Đối với một cơ sở dữ liệu gồm một nghìn tỷ mục, đó là khác biệt giữa một nghìn tỷ bước và một triệu bước — đáng kể, nhưng kém ngoạn mục hơn nhiều so với mức tăng tốc theo hàm mũ của Shor.

Thuật toán Grover tổng quát hơn thuật toán Shor: nó áp dụng cho hầu như bất kỳ bài toán tìm kiếm hay thỏa mãn ràng buộc nào và xuất hiện như một chương trình con bên trong nhiều thuật toán lượng tử khác. Cái bẫy của nó là bạn cần một “oracle” hiệu quả — một mạch lượng tử đặc thù cho bài toán có khả năng nhận ra đáp án đúng — vốn không phải lúc nào cũng dễ xây dựng. (Xem Quantum Algorithms for Beginners.)

VQE: hóa học lượng tử trên phần cứng cận-hạn

Variational Quantum Eigensolver (VQE) nhắm tới một mục tiêu khác: tìm trạng thái có năng lượng thấp nhất (trạng thái cơ bản) của một phân tử, vốn là nền tảng cho việc khám phá thuốc và khoa học vật liệu.

VQE là một thuật toán lai (hybrid). Máy tính lượng tử chuẩn bị một trạng thái thử (một “ansatz”) và đo năng lượng của nó; sau đó một bộ tối ưu hóa cổ điển điều chỉnh các tham số của trạng thái thử để đẩy năng lượng xuống thấp hơn, lặp lại cho đến khi hội tụ. Vì các mạch lượng tử giữ ở độ nông, VQE chịu đựng nhiễu của phần cứng hiện tại khá tốt, đó là lý do nó là một trong những thuật toán lượng tử được sử dụng tích cực nhất hiện nay.

Tuy nhiên, các điểm yếu của nó là có thật. Vòng lặp tối ưu hóa cổ điển thì chậm, và các mạch sâu hơn gặp phải bài toán “cao nguyên cằn cỗi” (barren plateau), nơi cảnh quan tối ưu hóa trở nên phẳng và việc huấn luyện bị đình trệ. Lợi thế lượng tử thực sự so với các phương pháp hóa học cổ điển tốt nhất vẫn chưa được chứng minh cho các phân tử quan trọng về mặt thực tiễn. Tuy nhiên, tiến bộ là cụ thể: vào năm 2026, IBM và Cleveland Clinic đã dùng một quy trình lai lượng tử-cổ điển để mô phỏng miniprotein Trp-cage 303 nguyên tử trên bộ xử lý Heron của IBM — một bước đầu tiên hướng tới hóa học lượng tử ở quy mô protein. (Xem Quantum Computing × Drug Discovery 2026.)

QAOA: tối ưu hóa xấp xỉ

Quantum Approximate Optimization Algorithm (QAOA) giải quyết bài toán tối ưu hóa tổ hợp — những bài toán như MaxCut, lập lịch và bài toán người bán hàng đi đường (traveling-salesman). Giống như VQE, nó là thuật toán lai: nó luân phiên giữa hai loại tiến hóa lượng tử và dùng một vòng lặp cổ điển để tinh chỉnh các tham số, rồi đo để trích ra một lời giải xấp xỉ.

Đánh giá trung thực thì thận trọng. Chất lượng lời giải của QAOA cải thiện theo độ sâu của mạch, nhưng độ sâu bị giới hạn bởi decoherence trên phần cứng thực. Quan trọng hơn, các bộ giải tối ưu hóa cổ điển — branch-and-bound, thuật toán di truyền, các heuristic hiện đại — cực kỳ giỏi, nên ngưỡng để chứng minh lợi thế lượng tử là rất cao, và bằng chứng cho đến nay còn hạn chế. QAOA là một hướng nghiên cứu đầy hứa hẹn, chứ không phải một chiến thắng đã ngã ngũ. (Xem bài viết nền tảng của Frontiers.)

Quantum error correction và fault tolerance

Mọi thuật toán ở trên đều chung một kẻ thù: lỗi. Các qubit decohere và các gate hoạt động sai, và những lỗi đó tích lũy cho đến khi quá trình tính toán trở nên vô nghĩa. Quantum error correction (QEC) là câu trả lời, và nó là công nghệ tạo tiền đề quan trọng nhất cho toàn bộ lĩnh vực.

Ý tưởng cốt lõi là trải thông tin của một logical qubit đáng tin cậy ra trên nhiều qubit vật lý nhiễu, sao cho các lỗi có thể được phát hiện và sửa trước khi chúng làm hỏng kết quả. Hai họ mã chiếm ưu thế:

Surface code. Một lưới hai chiều các qubit vật lý mã hóa mỗi logical qubit. Chúng được hiểu rõ và chỉ cần các kết nối tầm ngắn, giữa các qubit lân cận gần nhất — rất phù hợp với chip superconducting. Cái giá phải trả thì cao ngất: xấp xỉ 1.000 qubit vật lý cho mỗi logical qubit.

LDPC code (low-density parity-check — kiểm tra chẵn-lẻ mật độ thấp). Chúng đòi hỏi một số kết nối tầm xa giữa các qubit, khiến chúng phù hợp một cách tự nhiên với các nền tảng trapped-ion và neutral-atom. Đổi lại, chúng cắt giảm mạnh phí tổn (overhead), có thể chỉ cần 10–100 qubit vật lý cho mỗi logical qubit thay vì 1.000.

Cụm từ cần để ý là fault tolerance (chịu lỗi): chế độ mà việc thêm nhiều qubit vật lý thực sự làm giảm tổng tỷ lệ lỗi, thay vì đưa vào nhiều nhiễu hơn mức nó sửa được. Vượt qua được ngưỡng đó là ranh giới phân chia giữa những cỗ máy nhiễu của hôm nay với những cỗ máy hữu ích của ngày mai.

Một số kết quả năm 2026 cho thấy bước chuyển này đang diễn ra:

• Willow của Google đạt cột mốc “vượt điểm hòa vốn” (beyond breakeven) đầu tiên, nơi các logical qubit sống lâu hơn những qubit vật lý cấu thành chúng với hệ số 2,4, với lỗi thực sự được trấn áp khi mã lớn dần lên.
• Quantum Loon của IBM chứng minh khả năng giải mã lỗi theo thời gian thực trong chưa đầy 480 nano giây bằng các mã qLDPC — nhanh hơn gấp mười lần so với các phương pháp trước đó, đạt được sớm hơn một năm so với kế hoạch.
• QuEra xác minh 96 logical qubit trên 448 nguyên tử vật lý với cách mã hóa qLDPC tỷ lệ 2:1, cho thấy mức tiết kiệm phí tổn là có thật.
• Kiến trúc Pinnacle của Iceberg Quantum tuyên bố nó có thể cắt số qubit vật lý cần cho RSA-2048 từ 20 triệu xuống dưới 100.000.

(Xem Quantum Low-Density Parity-Check (qLDPC) Codes.)

Điểm mấu chốt rút ra

Các thuật toán lượng tử rơi vào hai phe. Phe thứ nhất — Shor và Grover — mang lại những mức tăng tốc có thể chứng minh được, đôi khi ngoạn mục, nhưng đòi hỏi những cỗ máy lớn, đã được sửa lỗi mà hiện chưa tồn tại. Phe thứ hai — VQE và QAOA — chạy được trên phần cứng nhiễu của hôm nay nhưng chưa đánh bại được các phương pháp cổ điển tốt nhất trên các bài toán thực. Bắc cầu giữa hai phe là nhiệm vụ của error correction. Các cột mốc năm 2026 cho thấy cây cầu đó cuối cùng đang được xây dựng, dù việc băng qua nó hoàn toàn vẫn còn cách nhiều năm nữa.

Tài liệu tham khảo

• PostQuantum: Quantum Threat Timeline Report 2025
• Blockchain Council: Quantum Algorithms for Beginners
• Morning Glory Sciences: Quantum Computing × Drug Discovery 2026
• Frontiers: Quantum computing — foundations, algorithms, and emerging applications
• PostQuantum: Quantum Low-Density Parity-Check (qLDPC) Codes