이 책의 특징과 내용
이 책은 비 양자역학 전공자가 대표적인 양자 알고리즘들을 가능한 한 쉽게 이해할 수 있도록 집필하였으며, 양자 알고리즘을 이해하기 위한 최소한의 기본 지식과 용어 설명으로 이러한 장벽을 낮추려고 노력하였다. 본서의 가장 큰 장점은 양자 알고리즘이 수행될 때 단계적으로 큐비트들이 어떤 상태가 되는지를 보여주는 알고리즘의 단계적 흐름도를 제공하는 것이다. 단계적 흐름도는 그림으로 주어지며 아울러 설명도 곁들여 있어 독자가 양자 알고리즘을 이해하는 데 매우 큰 도움이 되리라 믿는다. 그리고 추가적인 필수 용어 및 기본 지식, 그리고 알고리즘 일부에 대한 상세한 이해를 위한 설명은 알고리즘을 이해해가는 흐름에 방해가 되지 않도록 부록에 수록하였다.
제1장 알고리즘을 배우기 위한 준비: 양자 알고리즘을 위한 양자역학의 기본적인 용어를 설명한다. 특히 큐비트, 양자 게이트, 중첩, 간섭 효과, 얽힘, 측정 및 양자 알고리즘의 시간복잡도를 살펴본다.
제2장 도이치 알고리즘: 도이치 알고리즘은 함수가 항상 일정한 값을 반환하는지 아니면 0과 1을 고루 반환하는지를 판별하는 아주 간단한 양자 알고리즘이다. 이 알고리즘은 초창기의 양자 알고리즘으로 “Hello_World 양자 알고리즘”이라 불리기도 한다. 또한 양자 연산 중 매우 중요한 개념으로 다른 양자 알고리즘들에서 자주 사용되는 위상 되차기(phase kickback)를 설명한다.
제3장 도이치-조자 알고리즘: 도이치-조자 알고리즘은 도이치 알고리즘을 n 비트로 일반화시킨 양자 알고리즘이다. 이 알고리즘은 n 비트의 입력임에도 단 1회의 오라클 사용만으로 해를 확인함으로써 기하급수적 시간 향상을 보여주는 양자 알고리즘이다.
제4장 번스타인-바지라니 알고리즘: 번스타인-바지라니(BV) 알고리즘은 도이치-조자 알고리즘과 유사하여 오라클 내의 함수만 다를 뿐 양자 회로가 같다. BV 알고리즘은 비밀 코드를 인자로 가진 특정 함수의 함숫값으로 위상 되차기를 수행하여 비밀 코드를 100%의 확률로 찾는다. 도이치-조자 알고리즘에서는 입력 함수가 오라클에 주어지고 주어진 입력 함수가 상수 함수인지 균형 함수인지를 판단하지만, BV 알고리즘은 오라클 속의 비밀 코드를 출력한다.
제5장 사이먼 알고리즘: 사이먼 알고리즘은 함수에 숨겨진 주기를 이용하여 비밀 코드 s를 O(n) 시간에 높은 확률로 찾는 양자 알고리즘이다. 사이먼 알고리즘은 알고리즘 전체를 여러 차례 수행하여 선형 독립 방정식을 추출함으로써 비밀 이진 코드 s를 계산한다. 사이먼 알고리즘은 일반 컴퓨터 알고리즘에 비해 기하급수적인 속도 향상을 보여준다.
제6장 그로버의 탐색 알고리즘: 그로버 양자 탐색 알고리즘은 지수 시간의 향상이 아니라 이차 시간 향상만을 보이는 양자 알고리즘이다.
제7장 쇼어의 소인수분해 알고리즘: 쇼어 알고리즘은 합성수를 소인수로 분해하는 양자 알고리즘이다. 즉, 두 개의 소수 p와 q의 곱으로 만들어진 홀수 N이 주어지면 쇼어 소인수분해 알고리즘은 p와 q를 다항식 시간에 찾는다. 현재까지 알려진 가장 빠른 알고리즘은 지수 시간에 근접한 수행 시간을 가진다.
제8장 QAOA: QAOA는 양자 알고리즘과 일반 컴퓨터의 최적화 알고리즘을 사용하는 혼합형 알고리즘이다. QAOA는 최근 일반적인 최적화 문제를 해결하는 데 사용되고 있으며, 특히 NP-완전 문제를 포함하여 많은 실세계 문제의 근사해를 찾는 알고리즘으로 많이 사용된다. 8장에서는 Max-Cut을 위한 QAOA를 소개한다.
제9장 VQE: VQE는 다항식 크기(polynomial size)의 매개변수만을 사용하여 고윳값 문제를 효율적으로 해결하여 원자나 분자의 특성을 찾는 데 도움을 주는 근사 알고리즘이다. VQE는 물리학의 변분 원리(variational principles)를 이용하여 행렬의 최저 고윳값에 근접한 고윳값을 찾는다. 8장의 QAOA와 같이 양자 알고리즘과 일반 컴퓨터의 최적화 알고리즘을 활용하는 복합형 알고리즘으로 일종의 해 탐색 알고리즘이다. 9장에서는 헬륨 수소 결합 분자를 위한 VQE를 살펴본다.
부록: 각 장을 보조하는 양자 용어로부터 알고리즘 분석에 필요한 과정, 양자 회로, 확률 계산, 복잡한 예제의 알고리즘 수행 결과 등을 포함하고 있다.
