Thuật toán cổ điển tái tạo bài toán từng được coi là chỉ máy tính lượng tử mới giải được

Các công ty máy tính lượng tử thường công bố bước đột phá khi phần cứng của họ giải được những bài toán được cho là ngoài tầm với của máy tính cổ điển. Nhưng một nghiên cứu mới từ các nhà vật lý tại Flatiron Institute và Đại học Boston cho thấy ranh giới đó có thể thay đổi rất nhanh.

Nhóm nghiên cứu đã phát triển một phương pháp mô phỏng cổ điển hiệu quả hơn dựa trên tensor networks kết hợp với belief propagation (thuật toán truyền thông tin trên mạng). Bằng cách này, họ tái tạo được chính bài toán động lực học lượng tử từng được dùng trong tuyên bố “quantum supremacy” nổi tiếng của D‑Wave năm 2025. Trong một số trường hợp, mô phỏng này đủ nhẹ để chạy trên phần cứng khiêm tốn — thậm chí trên laptop cá nhân.

Tuyên bố ban đầu của D‑Wave

Tháng 3/2025, D‑Wave công bố kết quả từ Advantage2, một máy tính lượng tử kiểu quantum annealer với khoảng 5.000 qubit. Công ty cho biết hệ thống này mô phỏng được động lực học của các vật liệu từ tính phức tạp chỉ trong dưới khoảng 20 phút.

Theo ước tính của họ, nếu thực hiện phép tính tương tự trên một siêu máy tính cổ điển hàng đầu — chẳng hạn như Frontier tại Oak Ridge National Laboratory (Mỹ) — thì quá trình này có thể mất gần một triệu năm tính toán liên tục.

Bài toán mà họ giải liên quan đến mô phỏng các hệ từ tính rối loạn, cụ thể là mô hình spin‑glass Ising trên các mạng tinh thể. Những hệ vật lý như vậy thường được dùng để nghiên cứu vật liệu từ, cảm biến và nhiều ứng dụng vật liệu mới. Theo nhóm nghiên cứu của D‑Wave, các phương pháp cổ điển khi đó gặp khó khăn khi mở rộng lên hệ lượng tử lớn, nên họ mô tả kết quả là một ví dụ về tính toán “vượt ngoài khả năng cổ điển”.

Khái niệm này thường được gọi là quantum supremacy hoặc quantum advantage — thời điểm một thiết bị lượng tử có thể hoàn thành nhiệm vụ mà máy tính cổ điển không thể làm trong thời gian thực tế.

Thuật toán cổ điển mới hoạt động thế nào

Nhóm Flatiron–Boston University quay lại chính bài toán mô phỏng đó nhưng tiếp cận theo cách khác.

Thay vì theo dõi toàn bộ trạng thái lượng tử — một đại lượng tăng theo cấp số mũ với số qubit — họ khai thác cấu trúc toán học của hệ thống.

Phương pháp của họ kết hợp nhiều ý tưởng:

• Tensor networks hai và ba chiều được sắp xếp theo đúng hình học của mạng spin
• Belief propagation, một thuật toán truyền thông điệp giúp cập nhật mạng hiệu quả
• Các kỹ thuật nén tensor network để giữ kích thước mô hình ở mức kiểm soát được khi mức độ vướng víu lượng tử tăng

Nhờ mô hình hóa mạng tensor theo cấu trúc lattice của hệ spin và dùng belief propagation trong quá trình tiến hóa thời gian, thuật toán có thể theo dõi động lực học của hệ mà không cần biểu diễn toàn bộ hàm sóng 5.000 qubit. Điều này giảm mạnh chi phí tính toán mà vẫn giữ độ chính xác cao.

Theo nhóm nghiên cứu, phương pháp này có thể mô phỏng chính xác và hiệu quả động lực học annealing lượng tử từng được cho là vượt ngoài khả năng của máy tính cổ điển.

Vì sao có thể chạy trên laptop

Tensor network hoạt động bằng cách nén trạng thái lượng tử. Thay vì lưu mọi biên độ của hàm sóng khổng lồ, nó chỉ giữ lại các tương quan quan trọng trong hệ.

Trong nhiều hệ vật lý có cấu trúc mạng rõ ràng, mức độ vướng víu lượng tử tăng theo cách vẫn có thể xấp xỉ gọn gàng. Khi điều đó xảy ra, tensor network chỉ cần ít tham số hơn rất nhiều so với mô phỏng brute‑force.

Trong nghiên cứu của Flatiron, việc kết hợp tensor network với belief propagation giúp giảm độ phức tạp đến mức một số trường hợp mô phỏng có thể chạy trên máy tính cá nhân thay vì siêu máy tính.

Điều này nói gì về “ưu thế lượng tử”?

Kết quả này không có nghĩa máy tính lượng tử không có lợi thế. Thay vào đó, nó nhấn mạnh một thực tế quan trọng trong lĩnh vực này: chuẩn so sánh luôn thay đổi.

Các tuyên bố về quantum advantage thường so sánh phần cứng lượng tử với thuật toán cổ điển tốt nhất được biết tại thời điểm đó. Nhưng các phương pháp cổ điển — từ tensor networks đến Monte Carlo và các kỹ thuật xấp xỉ khác — vẫn đang tiến bộ rất nhanh.

Vì vậy, một nhiệm vụ có vẻ “bất khả thi” đối với máy tính cổ điển hôm nay có thể trở nên khả thi ngày mai nếu có thuật toán tốt hơn. Nghiên cứu của Flatiron là minh họa rõ ràng: giới hạn trước đây chủ yếu nằm ở thuật toán cổ điển dùng để so sánh, không phải ở rào cản tính toán tuyệt đối.

Cuộc chạy đua vẫn tiếp diễn

Do đó, tiêu chuẩn để chứng minh quantum advantage ngày càng khắt khe hơn. Các nhà nghiên cứu hiện tìm kiếm những bài toán mà:

• thuật toán cổ điển khó có thể cải tiến đáng kể
• phần cứng lượng tử mang lại lợi thế rõ ràng khi mở rộng quy mô
• kết quả có thể được kiểm chứng độc lập

Câu chuyện này phản ánh một quy luật quen thuộc trong khoa học tính toán: tiến bộ thường đến từ cả phần cứng lẫn thuật toán. Trong khi bộ xử lý lượng tử ngày càng mạnh hơn, các thuật toán cổ điển cũng đang phát triển nhanh không kém.

Vì thế, cuộc cạnh tranh giữa hai hướng vẫn là một “cuộc chạy đua vũ trang” về tính toán — và mỗi tuyên bố về ưu thế lượng tử đều có thể bị thách thức bởi đột phá thuật toán tiếp theo.