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 \rangle =-|\omega \rangle$

$U_{\omega }|x\rangle =|x\rangle \qquad {\mbox{for all}}\ x\neq \omega$

Mục tiêu của ta là tìm ra chỉ số của $|\omega \rangle$

Thuật toán

[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\rangle$ là chồng chập của các trạng thái:

$|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle$.

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:

1. Khởi tạo hệ thống ở trạng thái:

   $|s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=1}^{N}|x\rangle$

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.
   1. Thực hiện toán tử $U_{\omega }$.
   2. 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\left|s\right\rangle \left\langle s\right|-I$,

U_ω 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: $\langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}$.

$\langle s|s\rangle =N{\frac {1}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}=1$.

$U_{\omega }|s\rangle =(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle$.

$U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2|s\rangle \langle s|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=2|s\rangle \langle s|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}|s\rangle \langle s|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =$

$=2|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle =|s\rangle -{\frac {4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle ={\frac {N-4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle$.

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|\langle \omega |s\rangle \right|^{2}=1/N$ đến $\left|\langle \omega |U_{s}U_{\omega }s\rangle \right|^{2}\approx 9/N$.

Tham khảo

• Reinhold, Blumel (2009). “Foundations of Quantum Mechanics: From Photons to Quantum Computers”.