소개

Grover의 알고리즘은 소위 비정형 검색 문제를 위한 양자 알고리즘으로, 기존 알고리즘보다 4배 이상 향상된 성능을 제공합니다. 즉, 그로버 알고리즘은 고전적으로 비정형 검색을 해결하는 데 필요한 연산 수의 제곱근에 해당하는 수의 연산을 필요로 하며, 이는 비정형 검색을 위한 고전적인 알고리즘은 적어도 그로버 알고리즘의 비용의 제곱근에 해당하는 비용이 있어야 한다는 말과 같습니다.

Grover의 알고리즘은 그 확장 및 기본 방법론과 함께 광범위하게 적용할 수 있는 것으로 밝혀졌으며, 표면적으로는 비정형 검색 문제처럼 보이지 않을 수 있는 많은 흥미로운 계산 작업에 4차원적인 이점을 가져다줍니다.

그로버의 검색 기법의 광범위한 적용 가능성은 매력적이지만, 이 강의를 시작하면서 이 기법이 제공하는 4차원적 이점이 클래식 컴퓨팅에 비해 퀀텀의 실질적인 이점으로 곧바로 이어지지는 않을 것 같다는 점을 인정해야 합니다. 클래식 컴퓨팅 하드웨어는 양자 컴퓨팅 하드웨어보다 훨씬 더 발전되어 있으며, 그로버 알고리즘이 제공하는 클래식 대비 양자적 이점은 조만간 실행 가능한 모든 비정형 검색 문제에 대해 현대 클래식 컴퓨터의 엄청난 클럭 속도에 의해 사라질 것입니다.

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

강의 동영상

다음 동영상에서는 John Watrous가 Grover의 알고리즘에 대한 이 단원의 내용을 단계별로 설명합니다. 또는 이 강의의 YouTube 비디오를 별도의 창에서 열 수 있습니다. 이 강의의 슬라이드를 다운로드하세요.