1747478
Biến đổi Fourier lượng tử
https://vi.wikipedia.org/wiki?curid=1747478
Title: Biến đổi Fourier lượng tử
Như vậy, biến đổi Fourier rời rạc trên trạng thái lượng tử của n qubit (để biểu diễn số formula_70) có thể thực hiện dễ dàng nhờ mạch lượng tử bên. Trên thực tế, mỗi qubit đơn có thể được thực hiện hiệu quả dựa vào cổng Hadamard và cổng điều khiển xoay pha. Tổng số lượng cổng sử dụng là formula_71 cổng.
Độ phức tạp.
Như các ví dụ trên và mạch lượng tử tổng quát, ta dễ thấy để triệt tiêu các thành phần, các phép biến đổi Fourier rời rạc được thực hiện qua formula_72 cổng Hadamard và các cổng điều khiển xoay pha formula_73, với formula_74 là số lượng qubit cần biến đổi, formula_75. Trong khi đó, phép biến đổi Fourier rời rạc "cổ điển" cần dùng formula_76 (với formula_74 là số lượng bit cần biến đổi). Đây là độ phức tạp thuật toán trong thời gian đa thức. Tuy nhiên, biến đổi Fourier lượng tử áp dụng trên một trạng thái lượng tử còn biến đổi Fourier rời rạc "cổ điển" lại áp dụng trên một vector, nên không phải tất cả công việc sử dụng biến đổi Fourier rời rạc "cổ điển" có thể tận dụng mức độ tăng độ phức tạp cấp số nhân này.
Ngày nay, trường hợp tốt nhất của thuật toán biến đổi Fourier lượng tử, chỉ sử dụng formula_78 cổng lượng tử, đã đạt được hiệu quả tốt.
Ứng dụng.
Biến đổi Fourier lượng tử là một thuật toán lượng tử quan trọng, nó thường là một phần của các thuật toán lượng tử khác, đặc biệt là thuật toán Shor để phân tích thừa số nguyên tố và tính toán các logarit rời rạc, thuật toán dự đoán pha lượng tử để ước tính giá trị riêng của các toán tử unita, và các thuật toán về vấn đề phân nhóm ẩn.