Vật lý nghiên cứu chuyên sâu

Thuật toán lượng tử (Shor, Grover)

Thuật toán lượng tử khai thác giao thoa và rối để tăng tốc một số bài toán, không làm mọi phép tính nhanh hơn.

Thuật toán lượng tử là chuỗi cổng đơn nhất, đo lường và xử lý cổ điển. Mục tiêu là tạo phân bố kết quả hữu ích với ít tài nguyên hơn một thuật toán cổ điển tốt nhất đã biết hoặc trong mô hình độ phức tạp phù hợp.

T_{\mathrm{Grover}}=O(\sqrt{N}),\qquad T_{\mathrm{classique}}=O(N);\quad T_{\mathrm{Shor}}=\operatorname{poly}(n)\ (\text{portes quantiques})

Định nghĩa: Tăng tốc lượng tử

Cải thiện tài nguyên tính toán so với mô hình cổ điển được chỉ rõ. Tuyên bố tăng tốc phải tính cả truy cập dữ liệu, lấy mẫu đầu ra, lỗi và chi phí tiền-hậu xử lý.

Vector trạng thái xoay trong mặt phẳng hai chiều; minh họa Grover lý tưởng, không mô phỏng phần cứng nhiễu.

Grover và Shor

Grover khuếch đại biên độ trạng thái đánh dấu bằng lặp phép oracle và phép phản xạ trung bình; cần bậc $\sqrt N$ truy vấn cho tìm kiếm không cấu trúc. Shor dùng biến đổi Fourier lượng tử và tìm chu kỳ để phân tích thừa số trong thời gian đa thức theo số bit, với mô hình truy vấn cổng lượng tử và sửa lỗi.

Ví dụ: Số truy vấn Grover

Với $N=10^4$ mục, ước lượng số truy vấn oracle cổ điển và bậc truy vấn Grover.

Lời giải

Tìm cổ điển cần bậc $N=10^4$ truy vấn; Grover cần bậc $\sqrt N=10^2$ . Hệ số chính xác tùy xác suất thành công và cách đếm oracle.

Thuật toán không làm song song mọi câu trả lời có thể đọc được: đo chỉ cho một mẫu, nên phải thiết kế giao thoa để khuếch đại biên độ đúng. Trong Grover, phép oracle đánh dấu trạng thái mục tiêu, còn phép khuếch đại biên độ quay trạng thái khoảng $\pi/4$ mỗi vòng về phía mục tiêu; số truy vấn tỉ lệ $\sqrt N$ . Shor khai thác chu kỳ của phép nhân modulo để phân tích thừa số với thời gian đa thức lượng tử, nhưng lợi thế thực tế còn phụ thuộc sửa lỗi và phần cứng.

Độ phức tạp truy vấn không giống thời gian chạy đầy đủ: chi phí chuẩn bị trạng thái, sửa lỗi và đọc kết quả đều phải tính vào ứng dụng thực tế. Phân tích thuật toán cần nêu rõ mô hình oracle và phân bố đầu vào; lợi thế tiệm cận có thể biến mất với dữ liệu nhỏ hoặc chi phí tiền xử lý lớn. Câu hỏi nghiên cứu quan trọng là lớp bài toán nào giữ được lợi ích khi chuyển từ mạch lý tưởng sang máy chịu lỗi.

Grover tìm kiếm không cấu trúc trong N mục cần bậc số truy vấn nào?

Ưu thế của thuật toán Shor được phát biểu chính xác nhất thế nào?

Tài liệu tham khảo

Michael A. Nielsen, Isaac L. Chuang (2010). Quantum Computation and Quantum Information