소개

양자 알고리즘은 질의 모델(query model) 계산에서 고전 알고리즘에 비해 입증 가능한 이점을 제공합니다. 그러나 문제 입력이 오라클이나 블랙박스 형태가 아니라 명시적으로 주어지는 보다 표준적인 계산 모델의 경우에는 어떨까요? 이는 답하기가 훨씬 더 어려운 질문임이 밝혀졌으며, 이를 다루기 위해서는 먼저 탐구의 기반이 될 견고한 토대를 마련해야 합니다. 이것이 바로 이 레슨의 주된 목적입니다.

먼저 고전 및 양자 계산 모두에 대한 계산 비용(computational cost) 과 이를 측정하는 방법을 논의하는 것으로 시작하겠습니다. 이는 광범위한 계산 문제에 적용할 수 있는 일반적인 개념입니다. 그러나 내용을 단순하게 유지하기 위해 주로 계산적 정수론(computational number theory) 의 관점에서 살펴보겠습니다. 이 분야는 기본 산술, 최대공약수 계산, 정수 인수분해와 같이 대부분의 독자에게 친숙할 만한 계산 작업을 다룹니다. 계산적 정수론은 응용 분야가 좁지만, 이러한 문제들은 기본적인 쟁점을 설명하는 데 적합합니다(그리고 공교롭게도 이후 레슨과도 매우 밀접한 관련이 있습니다).

우리는 끊임없이 발전하는 하드웨어가 아니라 알고리즘에 초점을 맞춥니다. 이에 따라 어떤 특정 계산이 몇 초, 몇 분, 혹은 몇 시간 걸리는지보다는, 알고리즘이 실행되는 구체적인 문제 사례의 크기가 커질 때 실행 비용이 어떻게 확장되는지에 더 관심을 두겠습니다. 우리가 계산 비용의 이러한 측면에 집중하는 이유는, 알고리즘이 근본적인 중요성을 가지며 기술이 발전함에 따라 더 빠르고 더 신뢰할 수 있는 하드웨어를 사용하여 자연스럽게 점점 더 큰 문제 사례에 적용될 것이라는 점을 인식하기 때문입니다.

마지막으로, 매우 중요한 과제인 양자 컴퓨터에서 고전 계산을 실행하는 문제를 다루겠습니다. 이 과제가 중요한 이유는 고전 컴퓨터를 양자 컴퓨터로 대체하고자 해서가 아니라(가까운 시일 내에, 혹은 영영 그렇게 될 가능성은 극히 낮아 보입니다), 양자 알고리즘에 흥미로운 가능성을 많이 열어주기 때문입니다. 구체적으로, 양자 컴퓨터에서 실행되는 고전 계산은 *서브루틴(subroutine)*으로 사용할 수 있게 되며, 이는 수십 년에 걸친 고전 알고리즘 연구 개발의 성과를 양자 계산적 이점을 추구하는 데 효과적으로 활용할 수 있게 해줍니다.

강의 영상

다음 영상에서 존 와트러스(John Watrous)가 이 양자 알고리즘적 기초 레슨의 내용을 단계별로 설명합니다. 또는 이 레슨의 YouTube 영상을 별도의 창에서 열어 볼 수도 있습니다. 이 레슨의 슬라이드를 다운로드하세요.