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) 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.

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.

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=logN 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:
Mục tiêu của ta là tìm ra chỉ số của formula_3

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

Toán tử

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

Thuật toán gồm các bước:
Từ định nghĩa, ta có bước khởi tạo
"U" có thể được biểu diễn theo cách:

Các bước sau cho thấy những gì xảy ra trong vòng lặp đầu tiên:
formula_9.
Sau khi 2 toán tử (formula_14 and formula_15) được sử dụng, giá trị cần tìm đã tăng từ formula_16 đến formula_17.
