✨Thuật toán Grover

Thuật toán tìm kiếm Grover là một thuật toán lượng tử dùng trong việc tìm kiếm trên một cơ sở dữ liệu chưa sắp xếp gồm N phần tử trong độ phức tạp về thời gian là O(N^1/2) và sử dụng O(log N) không gian lưu trữ. Thuật toán được trình bày bởi Lov Grover vào năm 1996.

Giống như nhiều thuật toán lượng tử khác, thuật toán lượng tử cho kết quả có xác suất chính xác cao. Xác suất thất bại có thể được giảm đi bằng cách thực hiện nhiều lần thuật toán.

Ứng dụng

Thuật toán Grover có thể được dùng để giải ngược phương trình. Nói cách khác, nếu có 1 phương trình y=f(x) có thể tính toán được trên 1 máy tính lượng tử, ta có thể dùng thuật toán Grover để tính được x với y cho trước. "Giải ngược phương trình" có thể được liên hệ với việc tìm kiếm trong 1 cơ sở dữ liệu vì ta có thể tạo ra 1 phương trình sao cho phương trình đó tạo ra một số y duy nhất nếu x trùng với 1 giá trị ở trong cơ sở dữ liệu.

Thuật toán Grover cũng có thể dùng để tính toán số trung bình và số trung vị trong 1 tập số. Thuật toán cũng có thể được tối ưu hóa nếu như có nhiều hơn 1 kết quả tìm kiếm hoặc số kết quả tìm kiếm đã được biết trước.

Khởi tạo

Giả sử ta có 1 cơ sở dữ liệu gồm N phần tử. Thuật toán cần có 1 không gian N chiều, dùng n=log₂N qubits. Ta cần xác định chỉ số của phần tử thỏa mãn những điều kiện tìm kiếm. Cho f là phương trình sao cho f cho giá trị 0 hoặc 1, f(ω)=1 khi và chỉ khi ω thỏa mãn những điều kiện tìm kiếm. Ta sử dụng toán tử U_ω: :$U$\omega |\omega\rang = - |\omega\rang :$U$\omega |x\rang = |x\rang \qquad \mbox {for all}\ x \ne \omega Mục tiêu của ta là tìm ra chỉ số của $|\backslash omega\backslash rang$

Thuật toán

nhỏ|phải|[Mạch lượng tử thể hiện Thuật Toán Grover Các bước của thuật toán được thực hiện như sau. Cho $|s\backslash rangle$ là chồng chập của các trạng thái:

:$|s\backslash rang\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\; \backslash sum\_\{x=1\}^\{N\}\; |x\backslash rang$.

Toán tử

:$U\_s\; =\; 2\; \backslash left|s\backslash right\backslash rangle\; \backslash left\backslash langle\; s\backslash right|\; -\; I$

là toán tử truyền thông tin (diffusion operator).

Thuật toán gồm các bước:

1. Khởi tạo hệ thống ở trạng thái: ::$|s\backslash rang\; =\; \backslash frac\{1\}\{\backslash sqrt\{N\; \backslash sum\_\{x=1\}^\{N\}\; |x\backslash rang$
2. Thực hiện "Vòng lặp Grover" _r(N)_ lần. Hàm _r(N),_ có độ phức tạp _O(N^½)_, được miêu tả như sau. #Thực hiện toán tử $U\_\backslash omega$. #Thực hiện toán tử $U\_s$.
3. Thực hiện phép đo Ω. Kết quả của phép đo sẽ là λ_ω với xác suất tiến tới 1 khi N≫1. Từ λ_ω, ta có thể tìm thấy ω.

Vòng lặp đầu tiên

Từ định nghĩa, ta có bước khởi tạo :$U\_s\; =\; 2\; \backslash left|s\backslash right\backslash rangle\; \backslash left\backslash langle\; s\backslash right|\; -\; I$, U_ω có thể được biểu diễn theo cách: :$U\_\backslash omega\; =\; I\; -\; 2\; \backslash left|\backslash omega\backslash right\backslash rangle\; \backslash left\backslash langle\; \backslash omega\backslash right|$.

Các bước sau cho thấy những gì xảy ra trong vòng lặp đầu tiên: