노벨 물리학 수상자인 리차드 파인만(Richard Feynman)이 양자역학에 대해 “If you think you understand quantum mechanics, you don’t understand quantum mechanics.”라고 한 것은 그만큼 양자역학의 이해가 힘들다는 뜻이다. 시작부터 매우 실망스러운 말이다. 하지만 파인만은 1981년 “Simulating Physics with Computers”라는 제목의 소규모 MIT 강연에서 양자 시스템을 사용하여 고전(일반) 컴퓨터에서 매우 어렵거나 불가능한 계산을 수행하는 아이디어를 제안했다. 양자의 세계에서 일어나는 현상을 전반적으로 이해할 수는 없어도 양자를 이용한 계산은 당연히 가능하다. 양자 컴퓨터는 일반 컴퓨터와 본질적으로 다른 하드웨어이다. 양자 컴퓨터에는 CPU도 없고 하드디스크 같은 메모리도 없으며, 정보를 가지고 있는 큐비트의 상태를 다른 큐비트에 복사할 수도 없다. 그러나 양자 컴퓨터의 매우 큰 장점은 n개의 큐비트를 중첩하여 2의 n승개의 연산을 동시에 할 수 있는 것이다. 이는 일반 컴퓨터가 흉내 낼 수 없는 중요한 장점이다. 하지만 양자 컴퓨터가 2의 n승개의 연산을 동시에 수행하더라도 중간에 결과를 알고 싶다면 n 큐비트를 측정해야 하는데, 실제로 n 큐비트를 측정하면 2의 n승개의 연산 결과 중 오직 1개의 결과만 알 수 있고, 다른 모든 2의 n승-1개의 중간 결과는 모두 사라진다. 일반 컴퓨터에서는 이러한 불상사는 안 일어난다. 즉, 일반 컴퓨터에서는 중간 결과 일부분을 읽고 처리하여도 중간 결과는 사라지지 않는다. 이는 양자 컴퓨터의 큰 제약점이며, 양자 컴퓨터가 일반 컴퓨터가 해결할 수 있는 모든 문제를 해결할 수 없는 근본적인 이유 중 하나이다. 그러나 양자 컴퓨터는 데이터의 패턴 추측이나 주기(period)를 찾는 문제, 최대 또는 최솟값을 찾는 최적화 문제, 최소 고윳값을 찾는 문제 등을 2의 n승개의 병렬 연산을 이용하여 기하급수적으로 빠르게 해결한다. 아무리 빠른 슈퍼컴퓨터를 수백 수천 대를 가지고 동시에 위에 말한 문제를 해결하려해도 앞으로 만들어질 오류 보정 기능을 갖춘 양자 컴퓨터 1대를 따라갈 수 없다. 30년 넘게 알고리즘을 강의하고 피터 쇼어의 소인수분해 양자 알고리즘도 수년간 강의해보았다. 매년 쇼어의 소인수분해 알고리즘을 컴퓨터과학과 학부생들에게 강의할 때마다 양자역학의 기본 지식 이해는커녕 양자역학의 용어부터 학부생들에게 매우 높은 장벽이 되는 것을 느꼈다. 기말시험에 쇼어 알고리즘에 대해 문제가 나온다고 하고, 실제 출제하면 답을 비슷하게 쓰는 학생은 8∼90명 중 두셋 정도였다. 이 책을 접하는 독자 대부분은 일반 컴퓨터의 알고리즘에 익숙하다고 본다. 그런데 양자 알고리즘을 처음 보면 일반 컴퓨터의 알고리즘과 비교하여 그 형태도 다르고, 알고리즘의 입력이 어디에 있는지조차 불분명하며, 큐비트 상태를 나타내는 생소한 양자 식으로 알고리즘의 단계를 설명하는 등 ‘알고리즘’이라는 용어만이 일반 컴퓨터 알고리즘과 같다는 것을 느낄 것이다. 이러한 장벽은 양자역학의 용어뿐 아니라, 앞서 설명한 양자 컴퓨터 자체의 특수한 하드웨어에 기인한다. 양자역학 용어 중, 중첩이나 얽힘은 누구나 들어본 용어라 별문제 없지만, 위상이나 간섭 효과만 해도 생소해지기 시작한다. 눈으로 볼 수 있는 것도 아니고, 체감할 수 있는 것도 아니기 때문이다.

CHAPTER 01 알고리즘을 배우기 위한 준비 1.1 큐비트 1.2 기본적인 양자 게이트 및 회로 1.3 양자 상태 측정과 알고리즘의 시간복잡도 요약 연습문제 CHAPTER 02 도이치 알고리즘 2.1 1-비트 상수 함수와 균형 함수 2.2 도이치 알고리즘 2.3 알고리즘의 단계별 이해 2.4 양자 회로 및 시간복잡도 요약 연습문제 CHAPTER 03 도이치-조자 알고리즘 3.1 n-비트 상수 함수와 균형 함수 3.2 도이치-조자 알고리즘 3.3 알고리즘의 단계별 이해 3.4 양자 회로 및 시간복잡도 요약 연습문제 CHAPTER 04 번스타인-바지라니 알고리즘 4.1 비밀 코드와 특정 함수 4.2 BV 알고리즘 4.3 알고리즘의 단계별 이해 4.4 양자 회로 및 시간복잡도 요약 연습문제 CHAPTER 05 사이먼 알고리즘 5.1 사이먼 문제 5.2 사이먼 알고리즘 5.3 알고리즘의 단계별 이해 5.4 양자 회로 및 시간복잡도 요약 연습문제 CHAPTER 06 그로버의 탐색 알고리즘 6.1 탐색 문제 6.2 그로버 알고리즘 6.3 알고리즘의 단계별 이해 6.4 양자 회로 및 시간복잡도 요약 연습문제 CHAPTER 07 쇼어의 소인수분해 알고리즘 7.1 소인수분해를 위한 정리 7.2 쇼어 알고리즘 7.3 알고리즘의 단계별 이해 7.4 양자 회로 및 시간복잡도 요약 연습문제 CHAPTER 08 QAOA 8.1 Max-Cut 문제 8.2 Max-Cut을 위한 QAOA 8.3 Max-Cut을 위한 QAOA의 양자 회로 8.4 알고리즘의 단계별 이해 8.5 Max-Cut을 위한 QAOA의 알고리즘 분석 요약 연습문제 CHAPTER 09 VQE 9.1 VQE는 어떤 문제를 해결하나? 9.2 VQE 알고리즘 9.3 HeH+를 위한 VQE 요약 연습문제 부록 A. 유니터리 연산자 B. 위상, Bloch Sphere, 위상 되차기 C. 양자 게이트 D. 도이치-조자 알고리즘 Step [4]의 식 유도과정 E. 그로버 알고리즘의 Step [4]에 대한 상세 설명 F. QFT의 결과가 왜 M/k의 배수인가? G. QFT 양자 회로 H. 내적, Operators, 기댓값 I. QAOA 확률 계산 J. HeH+를 위한 VQE 참고문헌

이 책의 특징과 내용 이 책은 비 양자역학 전공자가 대표적인 양자 알고리즘들을 가능한 한 쉽게 이해할 수 있도록 집필하였으며, 양자 알고리즘을 이해하기 위한 최소한의 기본 지식과 용어 설명으로 이러한 장벽을 낮추려고 노력하였다. 본서의 가장 큰 장점은 양자 알고리즘이 수행될 때 단계적으로 큐비트들이 어떤 상태가 되는지를 보여주는 알고리즘의 단계적 흐름도를 제공하는 것이다. 단계적 흐름도는 그림으로 주어지며 아울러 설명도 곁들여 있어 독자가 양자 알고리즘을 이해하는 데 매우 큰 도움이 되리라 믿는다. 그리고 추가적인 필수 용어 및 기본 지식, 그리고 알고리즘 일부에 대한 상세한 이해를 위한 설명은 알고리즘을 이해해가는 흐름에 방해가 되지 않도록 부록에 수록하였다. 제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를 살펴본다. 부록: 각 장을 보조하는 양자 용어로부터 알고리즘 분석에 필요한 과정, 양자 회로, 확률 계산, 복잡한 예제의 알고리즘 수행 결과 등을 포함하고 있다.