소개

Grover 알고리즘은 이른바 비구조적 탐색 문제를 위한 양자 알고리즘으로, 고전 알고리즘 대비 이차적 개선을 제공합니다. 이것이 의미하는 바는, Grover 알고리즘이 비구조적 탐색을 고전적으로 풀기 위해 필요한 연산 횟수의 제곱근 수준의 연산만을 필요로 한다는 것이며, 이는 비구조적 탐색에 대한 고전 알고리즘의 비용이 최소한 Grover 알고리즘 비용의 제곱 수준이 되어야 한다는 것과 동등합니다.

Grover 알고리즘은 그 확장 및 기반 방법론과 함께 폭넓은 적용 가능성을 가지며, 표면적으로는 비구조적 탐색 문제처럼 보이지 않을 수 있는 다양한 흥미로운 계산 작업에 대해 이차적 이점을 제공합니다.

Grover 탐색 기법의 폭넓은 적용성이 매력적이긴 하지만, 레슨을 시작하는 시점에서 이 기법이 제공하는 이차적 이점이 가까운 시일 내에 고전 컴퓨팅 대비 양자 컴퓨팅의 실용적 이점으로 이어질 가능성은 낮다는 점을 인정해야 합니다. 고전 컴퓨팅 하드웨어는 양자 컴퓨팅 하드웨어보다 훨씬 더 발전되어 있으며, Grover 알고리즘이 제공하는 고전 대비 양자의 이차적 이점은 가까운 시일 내에 실행 가능할 만한 어떤 비구조적 탐색 문제에서든 현대 고전 컴퓨터의 놀라운 클럭 속도에 의해 분명히 상쇄될 것입니다.

그러나 양자 컴퓨팅 기술이 발전함에 따라, Grover 알고리즘은 잠재력을 가질 수 있습니다. 실제로 고속 푸리에 변환과 빠른 정렬(예: 퀵 정렬과 병합 정렬) 등 지금까지 발견된 가장 중요하고 영향력 있는 고전 알고리즘 중 일부는 그들이 해결하는 문제에 대한 순진한 접근 방식과 비교하여 이차보다 약간 적은 이점을 제공합니다. 여기서 중요한 차이점은 물론 Grover 알고리즘을 실행하기 위해 완전히 새로운 기술(양자 컴퓨팅)이 필요하다는 점입니다. 이 기술이 고전 컴퓨팅에 비해 아직 초기 단계에 있지만, 언젠가 양자가 고전 컴퓨팅에 대해 이차적 이점을 제공하여 실질적인 실용적 혜택을 가져올 수 있는 기술 발전의 잠재력을 성급하게 과소평가해서는 안 됩니다.

레슨 영상

다음 영상에서 John Watrous가 Grover 알고리즘에 관한 이번 레슨의 내용을 단계별로 안내합니다. 또는 이 레슨의 YouTube 영상을 별도의 창에서 열 수도 있습니다. 이 레슨의 슬라이드를 다운로드할 수 있습니다.