Thuật toán Lượng tử: Shor và Grover

Thuật toán Shor có thể phân tích một số nguyên lớn thành các thừa số nguyên tố một cách hiệu quả theo cấp số nhân so với thuật toán cổ điển tốt nhất. Vì sự an toàn của mã hóa RSA (được dùng trong hầu hết các giao dịch trực tuyến) dựa trên sự khó khăn của việc phân tích số nguyên tố, một máy tính lượng tử đủ lớn chạy thuật toán Shor có thể phá vỡ gần như toàn bộ an ninh mạng hiện tại.

Chưa cần hoảng sợ. Các máy tính lượng tử hiện tại còn quá nhỏ và quá nhiều lỗi để chạy thuật toán Shor với các số đủ lớn để phá vỡ mã hóa thực tế. Tuy nhiên, các nhà nghiên cứu đang tích cực phát triển "mật mã hậu lượng tử" (post-quantum cryptography) để chuẩn bị cho tương lai.

Thuật toán Grover được dùng để tìm kiếm một mục cụ thể trong một cơ sở dữ liệu lớn, không có cấu trúc. Hãy tưởng tượng bạn đang tìm một cái tên trong một danh bạ điện thoại khổng lồ không được sắp xếp theo thứ tự abc.

Một tìm kiếm cổ điển trong cơ sở dữ liệu N mục sẽ mất trung bình N/2 lần thử. Thuật toán Grover chỉ cần khoảng √N (căn bậc hai của N) lần thử. Đây là một sự tăng tốc đáng kể (tăng tốc bậc hai - quadratic speedup), nhưng không phải là tăng tốc theo cấp số nhân như thuật toán Shor.

Nó đến từ sự kết hợp của chồng chập và giao thoa lượng tử. Chồng chập cho phép máy tính lượng tử khám phá nhiều khả năng cùng một lúc. Giao thoa lượng tử sau đó được sử dụng để khuếch đại xác suất của câu trả lời đúng và triệt tiêu xác suất của các câu trả lời sai.

Có rất nhiều. Một số thuật toán quan trọng khác bao gồm thuật toán của Deutsch-Jozsa (một trong những ví dụ đầu tiên về tăng tốc lượng tử), các thuật toán mô phỏng lượng tử (để mô phỏng các hệ vật lý), và HHL (để giải các hệ phương trình tuyến tính), có ứng dụng trong học máy.

Bản chất của bài toán tìm kiếm không có cấu trúc là có giới hạn về mặt lý thuyết. Đã được chứng minh rằng thuật toán Grover là tối ưu, và không có thuật toán lượng tử nào có thể giải quyết bài toán này nhanh hơn đáng kể so với mức tăng tốc bậc hai.

Về cơ bản, thuật toán Shor giải quyết "bài toán tìm chu kỳ" (period-finding problem). Bài toán này có nhiều ứng dụng trong toán học và vật lý, không chỉ riêng việc phân tích thừa số nguyên tố.

Sau khi thực hiện các phép toán lượng tử, thuật toán kết thúc bằng một phép đo. Phép đo này làm sụp đổ trạng thái chồng chập thành một chuỗi bit cổ điển. Nhờ vào giao thoa lượng tử, chuỗi bit này có xác suất cao chính là câu trả lời cho bài toán.

Chắc chắn. Lĩnh vực thuật toán lượng tử vẫn còn rất mới và đang phát triển nhanh chóng. Các nhà nghiên cứu trên khắp thế giới đang liên tục tìm kiếm các vấn đề mới mà máy tính lượng tử có thể giải quyết hiệu quả hơn máy tính cổ điển.