출처 검증됨레벨 3
그로버 알고리즘
그로버 알고리즘은 비구조적 검색에 이차적 속도향상을 제공하여, N개 항목의 비정렬 데이터베이스에서 O(N) 대신 O(√N) 쿼리만으로 표시된 항목을 찾습니다.
무슨 뜻인가요
그로버 알고리즘(1996)은 대략 π/4 * √N 오라클 쿼리를 사용합니다.두 연산을 반복 적용합니다: (1) 대상 상태의 위상을 뒤집는 오라클, (2) 평균에 대한 반전을 통해 표시된 상태의 진폭을 증폭하는 확산 연산자.일상 비유
그로버 알고리즘은 공명 효과와 같습니다: 각 반복이 올바른 답의 확률을 증폭시킵니다.
양자 반향 정위로 생각하세요.
흔한 오해
- 이차적 속도향상이지 지수적이 아닙니다.
- 너무 많은 반복은 성공 확률을 감소시킵니다.
핵심 정리
- O(√N) 쿼리로 비정렬 데이터베이스 검색 -- 이차적 속도향상.
- 위상 오라클 + 진폭 증폭 사용.
- 비구조적 검색에 최적임이 증명됨.
이해했는지 확인해 보세요
N개 항목에 대한 그로버 검색의 시간 복잡도는?
- A.O(N)
- B.O(log N)
- C.O(√N)
- D.O(N²)
정답 보기
정답: C. O(√N)
이유: O(√N) 오라클 쿼리가 필요합니다.
먼저 알아야 할 개념
원 출처: Grover, Quantum mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325 (1997), doi:10.1103/PhysRevLett.79.325