그로버 알고리즘
그로버 알고리즘은 양자 비구조적 탐색 분야에서 사용되는 대표적인 알고리즘이다. 오라클 위상 표시와 평균에 대한 진폭 반전 반복을 중심으로 동작하며, 처리 대상은 N개의 후보와 참·거짓 오라클이다. 주요 활용에는 양자 검색과 진폭 증폭이 포함된다.
| 분류 | 양자 비구조적 탐색 |
|---|---|
| 설계 | Lov Grover |
| 공개 | 1996년 발표 |
| 입력 | N개의 후보와 참·거짓 오라클 |
| 핵심 구조 | 오라클 위상 표시와 평균에 대한 진폭 반전 반복 |
| 성질·전제 | 유일한 해에서 O(√N) 오라클 질의; 다수 해라면 O(√(N/M)) |
| 활용 | 양자 검색과 진폭 증폭 |
| 참고 자료 | 논문·공식 문서 |
그로버 알고리즘은 양자 비구조적 탐색 분야에서 사용되는 대표적인 알고리즘이다. 오라클 위상 표시와 평균에 대한 진폭 반전 반복을 중심으로 동작하며, 처리 대상은 N개의 후보와 참·거짓 오라클이다. 주요 활용에는 양자 검색과 진폭 증폭이 포함된다.[1]
그로버 알고리즘은 해를 찾기 위한 특별한 구조가 없는 N개의 후보를 탐색할 때 양자 중첩과 진폭 증폭을 활용해 오라클 질의 횟수를 줄이는 양자 알고리즘이다. 1996년 Lov Grover가 발표했으며, 일반적인 고전적 비구조적 탐색에 필요한 O(N) 질의보다 적은 O(√N) 질의로 해를 높은 확률로 찾을 수 있다. 후보 중 해가 M개인 경우 적절한 가정 아래 O(√(N/M)) 횟수로 일반화된다.
동일한 진폭의 균등 중첩 상태를 준비한 뒤, 정답을 표시하는 오라클이 해당 상태의 위상을 반전시키도록 한다. 이어 확산(diffusion) 연산으로 진폭을 평균에 대해 반전해 정답 상태의 진폭을 키운다. 두 연산을 적절한 횟수만큼 반복하고 측정하여 정답 후보를 얻는다. 반복 횟수가 지나치게 크면 정답 확률이 다시 감소하므로 후보 개수와 해의 수를 고려한 반복 횟수 선택이 중요하다.
그로버 알고리즘은 주어진 입력에 대한 정답 여부를 오라클로 검사할 수 있을 때의 질의 복잡도를 설명한다. 오라클 회로 자체를 구현하는 비용과 오류 수정·메모리 접근 등 실제 양자 하드웨어의 비용을 포함하면 이론적인 제곱근 질의 이득이 실제 실행 시간 이득으로 바로 이어지지는 않는다. 양자 암호분석과 검색·최적화의 이론적 한계를 연구할 때 중요한 기초 알고리즘이다.[2]