Quantum algorithm (thuật toán lượng tử) là thuật toán được thiết kế để chạy trên máy tính lượng tử, khai thác các hiện tượng của cơ học lượng tử để giải quyết một số bài toán nhanh hơn đáng kể so với thuật toán cổ điển.
Quantum algorithm sử dụng các hiện tượng:
-
Chồng chập (superposition): qubit có thể ở nhiều trạng thái cùng lúc
-
Vướng víu lượng tử (entanglement): các qubit liên hệ chặt chẽ với nhau
-
Giao thoa (interference): khuếch đại xác suất kết quả đúng, triệt tiêu kết quả sai
Quantum algorithm ra đời không phải để thay thế hoàn toàn thuật toán cổ điển, mà để giải quyết hiệu quả hơn một số bài toán đặc thù, nhờ khai thác các nguyên lý của cơ học lượng tử.
Cấu trúc chung của một Quantum Algorithm
Hầu hết các thuật toán lượng tử đều tuân theo một “kịch bản” quen thuộc:
-
Chuẩn bị chồng chập
Đưa hệ qubit vào trạng thái biểu diễn nhiều khả năng cùng lúc. -
Đánh dấu nghiệm đúng (Oracle)
Một phép biến đổi lượng tử “gắn nhãn” nghiệm cần tìm. -
Khuếch đại bằng giao thoa
Làm tăng xác suất của nghiệm đúng, giảm xác suất nghiệm sai. -
Đo (Measurement)
Khi đo, ta thu được nghiệm đúng với xác suất rất cao.
Một số quantum algorithm tiêu biểu
-
Thuật toán Grover
Dùng cho bài toán tìm kiếm không cấu trúc.
Thay vì cần bước như cổ điển, Grover chỉ cần khoảng bước. -
Thuật toán Shor
Dùng để phân tích số nguyên lớn thành thừa số.
Có ý nghĩa lớn trong mật mã học, vì nhiều hệ mã hiện nay dựa vào độ khó của bài toán này. -
Thuật toán mô phỏng hệ lượng tử
Máy tính lượng tử đặc biệt phù hợp để mô phỏng chính… thế giới lượng tử, điều mà máy tính cổ điển làm rất tốn kém.
Nguồn tham khảo và đọc thêm
- https://www.quantumgrad.com/article/744
- https://quantum.microsoft.com/en-us/insights/education/concepts/quantum-algorithms
- https://quantumalgorithmzoo.org/
- https://www.bluequbit.io/blog/quantum-algorithms
- https://www.cs.umd.edu/~amchilds/qa/qa.pdf
Không có nhận xét nào:
Đăng nhận xét