Google giới thiệu thuật toán DQI, biến bài toán tối ưu thành bài toán giải mã có cấu trúc để tận dụng sức mạnh lượng tử và rút ngắn thời gian xử lý vượt trội so với máy tính cổ điển.
Hai nhà nghiên cứu Stephen Jordan và Noah Shutty thuộc Google Quantum AI và Google Research vừa giới thiệu một phương pháp tính toán lượng tử mới mang tên Decoded Quantum Interferometry (DQI). Công nghệ này được công bố trên tạp chí Nature, cho thấy tiềm năng giải quyết các bài toán tối ưu hóa vốn rất khó xử lý bằng máy tính cổ điển. DQI khai thác các mẫu giao thoa lượng tử để tiếp cận nghiệm tối ưu, kết hợp với những thuật toán giải mã đã quen thuộc trong lĩnh vực sửa lỗi và truyền dữ liệu. Điểm then chốt của phương pháp là xác định các dạng bài toán tối ưu có thể chuyển đổi thành những bài toán “giải mã” có cấu trúc phù hợp, từ đó hứa hẹn mang lại lợi thế lượng tử khi phần cứng ngày càng hoàn thiện.
Decoded Quantum Interferometry: Hướng tiếp cận mới cho bài toán tối ưu
Nhóm Google Quantum AI phát triển DQI như một thuật toán lượng tử nhằm xử lý những bài toán tối ưu hóa có không gian nghiệm rộng và phức tạp. Thay vì giải trực tiếp, DQI “biến đổi” bài toán tối ưu thành một bài toán giải mã – đi tìm điểm gần nhất trong một mạng lưới (lattice). Nhờ cơ chế giao thoa lượng tử, máy tính lượng tử có thể duyệt qua không gian nghiệm hiệu quả hơn.
Điểm đột phá của DQI nằm ở việc kết hợp giao thoa lượng tử với những thuật toán giải mã đã được phát triển hàng chục năm phục vụ lưu trữ dữ liệu. Với bài toán Optimal Polynomial Intersection (OPI) – tìm đa thức phù hợp nhất với một tập dữ liệu – nhóm nghiên cứu cho thấy OPI có thể được chuyển thành bài toán giải mã mã Reed–Solomon (loại mã dùng trong DVD hay QR code). Đánh giá lý thuyết cho thấy một máy tính lượng tử có thể giải một số trường hợp OPI với chỉ vài triệu thao tác, trong khi thuật toán tốt nhất của máy tính cổ điển cần đến khoảng 10^{23} bước – chênh lệch khổng lồ.
Điều quan trọng là DQI không đơn giản thay thế một bài toán khó bằng một bài toán khó khác. Thay vào đó, thuật toán tìm kiếm các trường hợp mà bài toán giải mã có cấu trúc đặc biệt – chẳng hạn như tính chất đại số hoặc sự thưa (sparsity) – giúp việc giải mã trở nên dễ dàng hơn trên máy tính lượng tử mà không làm bài toán gốc “dễ đi” đối với máy tính cổ điển.
Liên kết giữa tối ưu hóa và bài toán giải mã
Nhóm nghiên cứu đã chứng minh một cầu nối thú vị giữa bài toán tối ưu và bài toán giải mã – vốn là tìm điểm gần nhất trong một không gian lưới. Đây không chỉ là lý thuyết thuần túy, mà còn liên quan đến nhiều ứng dụng quan trọng như lập kế hoạch tuyến đường, thiết kế thử nghiệm lâm sàng hay phân tích dữ liệu.
DQI dựa vào việc chuyển đổi bài toán tối ưu sang dạng bài toán giải mã và tận dụng các thuật toán giải mã tối ưu đã được tối ưu hóa qua hàng thập kỷ. Trường hợp điển hình là OPI: một số mô hình cho thấy máy tính lượng tử chỉ cần vài triệu phép toán để giải, trong khi máy tính cổ điển phải mất nhiều bậc độ lớn hơn. Điều này mở ra khả năng đạt “lợi thế lượng tử” cho các bài toán tối ưu hóa cụ thể.
Lợi thế này không đến từ việc bài toán được làm đơn giản hơn, mà từ việc bài toán giải mã sau chuyển đổi mang những cấu trúc mà thuật toán lượng tử có thể khai thác, trong khi thuật toán cổ điển lại không tận dụng được.
Bài toán OPI: minh chứng tiêu biểu
Trong bài toán optimal polynomial intersection, DQI cho phép chuyển bài toán sang dạng giải mã mã Reed–Solomon. Điều này đặc biệt quan trọng vì các mã này có cấu trúc đại số rõ ràng. Nhờ đó, máy tính lượng tử có thể khai thác để rút ngắn đáng kể số bước cần thiết. Trong một số điều kiện, số phép toán lượng tử cần thiết chỉ gần vài triệu, thấp hơn hàng tỉ tỉ lần so với cách tiếp cận cổ điển.
Sức mạnh của DQI thể hiện ở việc chuyển bài toán sang một miền mà cấu trúc đại số giúp việc truy tìm nghiệm dễ dàng hơn, trong khi điều đó không làm giảm độ khó của bài toán gốc đối với máy tính cổ điển. Sự “lệch pha” này giữa hai thế giới chính là nền tảng của ưu thế lượng tử.
Nguồn gốc của ưu thế lượng tử
DQI cho thấy lợi thế lượng tử không phải đến từ việc xử lý bài toán “khó hơn”, mà từ việc chuyển đổi thông minh sang một bài toán giải mã có cấu trúc thích hợp. Dù cả tối ưu hóa lẫn giải mã đều NP-hard, một số dạng giải mã trên các lưới có cấu trúc tốt lại có thể được giải nhanh hơn trên máy tính lượng tử.
Ví dụ, bài toán max-k-XORSAT không có nhiều tính chất đại số, nhưng lại sinh ra các lưới rất thưa. Sự thưa này đôi khi tạo điều kiện cho các thuật toán lượng tử tận dụng đặc điểm cấu trúc, dù bài toán tối ưu ban đầu vẫn rất khó với máy tính cổ điển.
Mở rộng sang tối ưu hóa thưa (Sparse Optimization)
Tối ưu hóa thưa tiếp tục là thách thức lớn cho cả giới tính toán cổ điển và lượng tử. Tuy vậy, nhóm Google chỉ ra rằng DQI vẫn có thể mang lại lợi thế nếu cấu trúc của lưới giải mã – như độ thưa hoặc mối quan hệ đại số – phù hợp để khai thác.
Ngay cả với các dạng lưới ít cấu trúc như trong max-k-XORSAT, DQI vẫn có tiềm năng tạo lợi thế thông qua việc dựa vào sự thưa của ma trận cơ sở. Điều này giúp máy tính lượng tử xử lý hiệu quả hơn mà không làm suy yếu tính phức tạp của bài toán gốc đối với máy tính cổ điển.