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 Ứ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_hoá 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 logN qubits Ta cần xác_định chỉ_số của phần_tử thoả_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 ω thoả_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 Thuật_toán 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 Vòng lặp đầu_tiên 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
Thuật_toán Grover