계산 복잡도 이론 분야에서 저명한 컴퓨터 과학자인 스콧 애론슨은 수학과 컴퓨터 과학과 물리학에 걸친 양자 컴퓨팅의 다양한 주제에 대해 핵심 이론부터 논쟁거리까지 깊이 있게 다루고 있다. 뛰어난 통찰력과 날카로운 논리와 철학적 견해로 가득 찬 이 책은 고대 그리스 철학자인 데모크리토스부터 시작해서 논리학, 집합론, 계산 가능성 및 복잡도 이론, 양자 컴퓨팅, 암호학, 양자역학의 해석 등에 이르는 놀라울 정도로 광범위한 영역을 다루고 있다. 여기에 그치지 않고, 시간 여행, 뉴컴의 패러독스, 인류 원리, 로저 펜로즈의 주장에 대한 견해 등도 소개한다.
애론슨만의 친근한 문체와 유머로 물리학, 수학, 컴퓨터 과학, 철학을 비롯한 다양한 배경의 독자들이 양자 컴퓨팅에 쉽게 다가갈 수 있게 해준다.

이 책의 대상 독자
과학 분야의 배경 지식을 갖춘 독자나 물리학, 컴퓨터 과학, 수학, 철학을 전공하는 학생이라면 누구나 쉽게 접근할 수 있다.

[목 차]

01장. 원자와 빈 공간
02장. 집합
03장. 괴델, 튜링, 그 동지들
04장. 정신과 기계
05장. 고생대 복잡도 이론
06장. P와 NP, 그 동지들
07장. 무작위성
08장. 암호화
09장. 양자
10장. 양자 컴퓨팅
11장. 펜로즈
12장. 결잃음과 숨은 변수
13장. 증명
14장. 양자 상태는 얼마나 클까?.
15장. 양자 컴퓨팅에 대한 회의론
16장. 학습
17장. 대화형 증명, 회로 하한과 몇 가지 주제
18장. 인류 원리 갖고 놀기
19장. 자유 의지
20장. 시간 여행
21장. 우주론과 복잡도
22장. 무엇이든 물어보세요


[본 문]

[지은이의 말]
2013년만 해도 양자역학을 정보와 확률에 대한 이론이라고 보는 관점은 극소수에 불과했다. 대중서든 교과서든 아무 물리학 책을 하나 집어 보면 (1) 현대 물리학은 모순처럼 보이는 온갖 현상들, 가령 파장이 입자라던가 입자가 파장이라는 내용으로 가득 차 있고, (2) 깊이 들어가 보면 이런 말들을 제대로 이해하는 사람도 없으며, (3) 이를 수학적으로 표현하는 데만 수년간의 집중적인 연구가 필요하지만, (4) 결국 원자론의 관점이 옳을 뿐만 아니라 그것만이 중요하다는 결론을 내린다.
내가 알고 싶은 것은 오직 다음과 같은 것들이다. 내 직관과 맞지 않는 이유, 실험 결과에 맞게 내 생각을 바로잡을 방법, 실제 세상이 돌아가는 방식에 내가 당황하지 않게 추론하는 방법이다. 장담하건대 물리학자들은 아원자 입자의 움직임이 미친 것처럼 보이지 않도록 직관을 바로 잡을 방법은 아무도 모른다. 실제로 전혀 방법이 없을지도 모른다. 아원자의 움직임이 한결같이 무작위로 일어난다는 것은 불편한 진실로 남을 수도 있다. “이러이러한 공식을 통해 해답을 구할 수 있다.”는 표현 이외에는 할 말이 없는 상태로 말이다.
다행히 지난 수십 년 동안 진행된 양자 컴퓨팅과 양자 기초론에 대한 연구 결과에서 볼 수 있듯이 오늘날에는 양자역학을 단지 미지의 사실로 치부하는 것보다 더 잘 설명할 수 있다고 생각한다. 결론부터 밝히면 이 책의 관점은 다음과 같다.
양자역학은 확률 법칙을 우아하게 일반화한 것이다. 1 놈이 아닌 2 놈으로, 양의 실수가 아닌 복소수를 기반으로 한 일반화라고 볼 수 있다. 양자역학의 응용은 양자역학 자체에 대한 연구와 완전히 별개로 진행할 수 있다. 이러한 일반화한 확률 이론은 양자 컴퓨팅 모델이라는 새로운 계산 모델로 자연스레 발전하는 토대가 될 수 있다. 한때 사전에 알 수 있는 것으로 여겼던 계산(computation)에 대한 기존 관념에 도전하고, 이론 전산학자들 나름의 목적에 따라 개발하고자 노력했던 바로 그 모델 말이다. 이러한 방향은 실제로 물리학과는 아무런 관련이 없을 수도 있다. 정리하면 양자역학은 물리학의 구체적인 문제를 해결하고자 한 세기 전에 등장했지만, 현재는 완전히 다른 관점에서 충분히 설명할 수 있다. 즉, 관념에 대한 역사의 한 부분으로, 수학과 논리학과 전산학과 철학을 통한 인식의 한계를 말이다.
내가 양자 컴퓨터 분야에 뛰어든 이유는 양자 컴퓨터로 무엇을 할 수 있는가가 궁금해서가 아니라 양자 컴퓨터의 실현 가능성이 우리가 세상을 바라보는 관점에 어떤 영향을 미치는지가 궁금해서였다. 실용적인 양자 컴퓨터가 구현 가능하고 인식의 한계가 우리의 생각과 다르거나, 그런 컴퓨터를 만들 수 없고 양자역학 원칙을 수정해야 하거나, 미처 생각하지 못했던 고전 컴퓨터로 양자역학을 효과적으로 모사하는 방법을 발견하거나, 셋 중 하나일 것이다. 이런 세 가지 가능성은 좀 괴짜 같은 추측처럼 들리겠지만 최소한 그중 하나는 참이다. 따라서 어떤 결과가 나오든지 내 강의 노트를 표절한 광고를 표절하면 “그거 흥미로운데.”라고 말할 수 있을 것이다.

1장에서는 최대한 ‘태초’에 해당하는 시점으로 거슬러 가서 고대 그리스 철학자인 데모크리토스에 대한 얘기부터 시작한다. 현재까지 전해지는 기록을 통해 추측되는 데모크리토스의 견해를 요약하면 모든 자연 현상은 주로 빈 공간을 빙빙 돌고 있는 몇 종류의 조그만 ‘원자’들 사이에서 일어나는 복잡한 상호작용을 통해 발생한다는 것이다.
2장과 3장에서는 논의의 방향을 잠시 바꿔 물리 세계에 대한 ‘미지의 사실’에 기대지 않는, 우리가 확보한 가장 심오한 지식인 수학을 설명한다. 지금까지 나온 수학 중에서도 가장 ‘물리학에 영향을 받지 않은’ 영역인 집합론, 논리학, 계산 가능성 이론부터 살펴본다. 이 과정에서 칸토어, 프레게, 괴델, 튜링, 처치, 코헨의 위대한 발견을 소개하는데, 이는 수학적 추론에 대한 분야를 파악하는 데 도움이 된다. 그뿐만 아니라 수학의 모든 분야를 ‘일정한 기계적인 절차’로 환원할 수 없는 이유를 보여주는 과정에서 어디까지 환원 가능한지, ‘기계적인 절차’라고 부르는 것의 정확한 의미가 무엇인지를 설명한다.
4장에서는 사람의 정신 역시 ‘일정한 기계적인 절차’를 따르는지에 대한 고리타분한 논쟁을 살펴본다.
5장에서는 계산 가능성 이론의 현대 사촌인 계산복잡도 이론을 소개한다. 이 이론은 이후의 장에서 중요한 역할을 한다. 특히 계산복잡도를 이용해 인식의 한계와 같은 ‘심오한 철학적 신비’를 인식의 한계라고 여기는 것들의 상당수를 반영하는 굉장히 풀기 어려운 수학적 난제로 탈바꿈하는 방법을 보여줄 것이다. 이런 수학적 난제는 우리가 알고 싶어 하는 것을 대부분 담을 수 있다. 이러한 변환의 예로 P 대 NP 문제가 대표적이다. 여기에 대해서는 6장에서 설명한다.
7장에서는 양자 컴퓨팅에 대한 준비 운동으로 계산 복잡도뿐만 아니라 다른 영역에서 고전적인 무작위성의 다양한 용도를 소개한다.
8장에서는 계산 복잡도란 개념이 1970년대 초에 암호학 이론과 응용에 접목돼 혁신적인 성과를 거두게 된 스토리를 소개한다.
9장에서는 양자역학이 ‘일반화된 확률 이론’이라는 저자의 관점을 소개한다.
10장에서는 저자의 전공 분야이자 양자역학과 계산복잡도 이론을 합쳐 탄생한 양자 계산 이론(quantum theory of computation)의 기초를 소개한다.
11장에서는 로저 펜로즈 경의 사상을 비평하는 시간을 갖는다. 펜로즈 경은 사람의 뇌는 그냥 양자 컴퓨터가 아니라 양자 중력 컴퓨터(quantum gravitational computer)라고 주장하는 것으로 유명하다. 그래서 사람은 튜링 계산 불가능한 문제도 풀 수 있으며, 이에 대한 근거로 괴델의 불완전성 정리를 제시한다. 이 과정에서 펜로즈의 추측에서 일말의 진실을 발견할 수 있는지 살펴본다.
12장에서는 양자역학 개념에 대한 문제점 중 저자가 핵심이라고 생각하는 것들을 하나씩 살펴본다. 문제는 미래가 비결정론적이라는 것이 아니라(그래도 상관없다) 과거 역시 비결정론적이라는 것이다. 여기에 대한 두 가지 상반된 반응을 살펴본다. 하나는 물리학자들 사이에서 가장 흔하게 볼 수 있는 것으로 결잃음(decoherence)과 열역학 제2법칙에서 말하는 효과적인 시간의 화살(arrow of time)을 내세우는 것이고, 다른 하나는 봄 역학과 같은 ‘숨은 변수 이론(hidden-variable theory)’에 의존하는 것이다. 숨은 변수 이론을 받아들이지 않더라도 이를 통해 나는 아주 흥미로운 수학적 질문 몇 가지를 제시한다고 생각한다.
13장에서는 수학 증명의 새로운 개념(확률론적 증명과 영지식 증명 등)을 소개한다. 그리고 이를 숨은 변수 이론의 계산 복잡도를 이해하는 데 적용해본다.
14장에서는 양자 상태의 크기를 가늠해본다. 즉, 고전 정보의 지수적 양을 인코딩하는지 여부를 따져본다. 이 질문을 양자 해석 논쟁과 연관시켜 보고, 양자 증명과 양자 조언에 대한 최신 복잡도 이론 관점의 연구 결과와도 연관시켜 본다.
15장에서는 양자 컴퓨팅에 대한 회의론자들의 주장을 고찰해본다. 회의론자들은 (모두가 동의하는 사실인) 실용적인 양자 컴퓨터를 만드는 것이 힘들다고 말하는 것이 아니라 몇 가지 근본적인 이유로 인해 근본적으로 불가능하다고 주장한다.
16장에서는 흄의 귀납 문제를 소개한다. 이를 매개로 양자 학습 이론과 양자 상태의 학습 가능성에 대한 최신 연구 결과의 논의로 이어 나간다.
17장에서는 대화형 증명 시스템의 고전 버전과 양자 버전에 관련된 몇 가지 혁신적인 결과(예, IP = PSPACE, QIP = PSPACE)를 소개하되 비상대화 회로 하한(non-relativizing circuit lower bound)으로 이어지는 것으로, P 대 NP 문제에 뭔가 실마리를 제공할지 모르는 것을 중심으로 살펴본다.
18장에서는 그 유명한 인류 원리(Anthropic Principle)와 종말 논법(Doomsday Argument)을 소개한다. (당연한 얘기지만) 굉장히 철학적인 주제에서 출발해 사후선택 양자 컴퓨팅과 PostBQP = PP로 이어지는 식으로 얘기를 풀어나간다.
19장에서는 뉴컴의 패러독스와 자유 의지를 살펴본다. 이 주제는 콘웨이-코헨의 ‘자유 의지 정리’에 대한 설명과 벨 부등식을 이용해 ‘아인슈타인 인증 무작위수’를 생성하는 방법으로 이어진다.
20장에서는 시간 여행을 다룬다. 이제는 익숙해진 패턴에 따라 얘기하는데, 다양한 철학적 논의에서 시작해 닫힌 시간꼴 곡선의 고전 컴퓨터나 양자 컴퓨터는 PSPACE와 완전히 동등한 계산 능력을 갖춘다는 것을 증명하는 것으로 마무리한다(이 증명에 대해 흥미로운 반론을 제시할 수 있으며 여기에 대해서도 충분히 얘기할 것이다).
21장에서는 우주론, 암흑 에너지, 베켄슈타인 한계, 홀로그래픽 원칙 등을 소개한다. 물론 이 모든 주제는 계산의 한계와 관련해 어떤 의미가 있느냐의 관점에서 설명한다. 예를 들어 블랙홀을 생성할 만한 에너지를 사용하지 않고도 얼마나 많은 비트를 저장하거나 검색할 수 있는지, 이런 비트에 대해 연산을 얼마나 많이 수행할 수 있는지 등을 따져본다.
22장은 일종의 디저트 역할을 한다. 여기 나온 내용은 “Quantum Computing since Democritus” 강의의 마지막 수업에서 학생들에게 무엇이든지 물어보라고 하고 나서 저자가 받은 질문에 답변했던 내용을 토대로 정리한 것이다. 양자역학의 실패, 블랙홀과 퍼즈볼, 계산복잡도에서 오라클 결과의 관련성, NP 완전 문제와 창의성, ‘슈퍼-양자’ 상관관계, 무작위 알고리즘의 역무작위화, 과학과 종교와 이성의 본질, 컴퓨터 과학이 물리학의 한 분야가 아닌 이유 등을 다룬다.

추천사
"스콧 애론슨은 영지식 증명, 양자 컴퓨팅, 블랙홀 엔트로피를 비롯한 과학 분야의 최신 개념을 깔끔하면서도 저자 고유의 시각으로 설명하고 있다. 강력히 추천한다."
― 마이클 닐슨(Michael Nielsen)/ 『Reinventing Discovery』(Princeton University Press, 2011) 저자

"웃다가 울다가 의자에서 떨어졌다. 그것도 계산 복잡도에 대한 장을 읽다가 그랬다. 양자 컴퓨팅과 컴퓨터 과학의 교재만큼이나 심각한 주제를 다루는 책이 어떻게 이처럼 어처구니없을 정도로 재미있을 수 있는가? 이 책은 물리적 우주가 어떻게 구성됐으며 왜 그런 식으로 형성됐는지 심오한 질문을 제기한다. 저자의 명료한 설명을 읽는 동안(최소한 이 책을 손에 쥐고 있는 동안 만큼은) 그 답을 우리가 이해한다고 믿을 수 있다."
― 세스 로이드(Seth Lloyd)/ MIT 교수, 『Programming the Universe(프로그래밍 유니버스)』(Vintage, 2007) 저자

"리처드 파인만 교수의 물리학 강의 이후로 이 책만큼 훌륭하면서 즐거운 강의 노트는 처음이다. 이 책은 강의 노트를 가장한 시집이다. 증명 및 농담과 이야기와 폭로로 구성돼 컴퓨터 과학과 물리학이라는 두 분야를 합성해 순전히 지적인 놀라움으로 일관되게 짜여 있다."
― 데이브 베이컨(Dave Bacon)/ 구글

스콧 애론슨(Scott Aaronson)
텍사스대학교 데이비드 제이 브루톤 센테니얼 컴퓨터 과학과 교수이자 양자정보센터 디렉터로, MIT 전기공학 및 컴퓨터 과학과 부교수일 때 이 책을 출간했다. 양자 복잡도 이론 전문가로서 세계 최고로 손꼽히며 양자 컴퓨팅과 계산 복잡도 이론 분야의 연구 성과뿐만 아니라 인기 있는 블로그인 ‘Shtetl-Optimized’로도 유명하다. 계산 복잡도 이론에 대한 온라인 백과사전인 복잡도 동물원(Complexity Zoo)을 만들었으며, <사이언티픽 아메리칸(Scientific American)>과 <뉴욕 타임즈(New York Times)>에 컬럼도 쓰고 있다. 연구 성과와 인기 있는 글에 대해 젊은 과학자와 공학자에게 주는 미국 대통령상(United States Presidential Early Career Award for Scientists and Engineers)과 앨런 T. 워터맨상을 비롯한 다양한 상을 받았다.


옮긴이 남기혁
고려대 컴퓨터학과에서 학부와 석사 과정을 마친 후 한국전자통신연구원에서 선임 연구원으로 재직하고 있다. 한빛미디어에서 출간한 『Make: 센서』(2015), 『메이커 매뉴얼』(2016), 『이펙티브 디버깅』(2017), 『전문가를 위한 C++』(2019), 『리팩토링 2판』(2020), 에이콘출판사에서 출간한 『현대 네트워크 기초 이론』(2016), 『도커 컨테이너』(2017), 『파이썬으로 배우는 인공지능』(2017), 『스마트 IoT 프로젝트』(2017), 『메이커를 위한 실전 모터 가이드』(2018), 『Go 마스터하기』(2018), 『자율 주행 자동차 만들기』(2018), 『The Hundred-Page Machine Learning Book』(2019) 등을 번역했다.

옮긴이 이태휘
산업체와 학교, 연구기관을 거치며 여러 시스템 소프트웨어 개발 프로젝트를 수행했다. 2007년부터 2010년까지 티맥스소프트에서 근무하며 티베로 관계형 데이터베이스 개발에 참여했다. 2014년에 서울대학교 컴퓨터공학부에서 박사 학위를 받았으며, 현재 한국전자통신연구원에서 선임연구원으로 재직 중이다. 번역서로는 에이콘출판사에서 펴낸 『퀄리티 코드』(2017), 『블록체인 완전정복 2/e』(2019), 『양자 컴퓨팅 입문』(2020), 『양자 컴퓨팅』(2020)이 있다.