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(N1/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=log2N 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 |\omega\rang

Thuật toán

Các bước của thuật toán được thực hiện như sau. Cho |s\rangle là chồng chập của các trạng thái:

:|s\rang = \frac{1}{\sqrt{N}} \sum_{x=1}^{N} |x\rang.

Toán tử

:U_s = 2 \left|s\right\rangle \left\langle s\right| - I

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

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

Khởi tạo hệ thống ở trạng thái:
::|s\rang = \frac{1}{\sqrt{N}} \sum_{x=1}^{N} |x\rang
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_\omega.
Thực hiện toán tử U_s.
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 \left|s\right\rangle \left\langle s\right| - I,
U&omega; có thể được biểu diễn theo cách:
: U_\omega = I - 2 \left|\omega\right\rangle \left\langle \omega\right|.

Các bước sau cho thấy những gì xảy ra trong vòng lặp đầu tiên:
\lang\omega|s\rang =\lang s|\omega\rang = \frac{1}{\sqrt{N}} .
: \langle s| s\rang =N\frac{1}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}=1.
: U_\omega |s\rang = (I-2| \omega\rangle \langle \omega|)|s\rang=|s\rang-2| \omega\rangle \langle \omega|s\rang=|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle .
:U_s(|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle) = (2 |s\rang \lang s| - I)(|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle)=2 |s\rang \lang s|s\rang-|s\rang-\frac{4}{\sqrt{N}}|s\rang \langle s|\omega\rang+\frac{2}{\sqrt{N}}|\omega\rang=
:=2|s\rang-|s\rang-\frac{4}{\sqrt{N}}\cdot\frac{1}{\sqrt{N}}|s\rang+\frac{2}{\sqrt{N}}|\omega\rang=|s\rang-\frac{4}{N}|s\rang+\frac{2}{\sqrt{N}}|\omega\rang=\frac{N-4}{N}|s\rang+\frac{2}{\sqrt{N}}|\omega\rang.
Sau khi 2 toán tử (U_\omega and U_s) được sử dụng, giá trị cần tìm đã tăng từ \left| \lang \omega | s \rang \right|^2 = 1/N đến \left| \lang \omega | U_s U_\omega s \rang \right|^2 \approx 9/N.

Tham khảo