맺음말

쿼리 모델 내에서 Grover 알고리즘은 점근적으로 최적입니다. 이것이 의미하는 바는, 최악의 경우에 Search 문제, 심지어 Unique search 문제만이라도 점근적으로 $O(\sqrt{N})$보다 적은 쿼리를 사용하여 푸는 쿼리 알고리즘을 고안하는 것이 불가능하다는 것입니다. 이는 여러 가지 방식으로 엄밀하게 증명되어 있습니다.

흥미롭게도, 이 사실은 Grover 알고리즘이 발견되기 전에도 알려져 있었습니다. Grover 알고리즘은 이미 알려져 있던 하한을 달성했습니다.

Grover 알고리즘은 또한 폭넓게 적용 가능하며, 그것이 제공하는 제곱근 속도 향상을 다양한 설정에서 얻을 수 있다는 의미에서 그러합니다. 예를 들어, Grover 알고리즘을 다른 알고리즘과 결합하여 개선을 얻을 수 있는 경우가 있습니다. 또한 Grover 알고리즘은 다른 양자 알고리즘 내부에서 속도 향상을 얻기 위한 서브루틴으로도 매우 흔히 사용됩니다.

마지막으로, 두 반사(reflection)를 합성하고 반복하여 양자 상태 벡터를 회전시키는 Grover 알고리즘에서 사용된 기법은 일반화될 수 있습니다. 그 예로 *진폭 증폭(amplitude amplification)*이라는 기법이 있는데, 이는 Grover 알고리즘과 유사한 과정을 다른 양자 알고리즘에 적용하여 성공 확률을 고전적으로 가능한 것보다 이차적으로 더 빠르게 증가시키는 것입니다. 진폭 증폭은 양자 알고리즘에서 폭넓게 응용됩니다.

따라서 Grover 알고리즘이 가까운 시일 내에 탐색에 대한 실용적인 양자 이점을 이끌어내지는 못할 수 있지만, 이는 근본적으로 중요한 양자 알고리즘이며, 양자 알고리즘에서 많은 응용을 발견하는 더 일반적인 기법의 대표적인 예입니다.