- 현재 위치
- home > 컴퓨터·ICT·어학 > 컴퓨터·IT 도서 > 컴퓨터공학 > 스콧 애론슨의 양자 컴퓨팅 강의[에이콘출판]
;)
계산 복잡도 이론 분야에서 저명한 컴퓨터 과학자인 스콧 애론슨은 수학과 컴퓨터 과학과 물리학에 걸친 양자 컴퓨팅의 다양한 주제에 대해 핵심 이론부터 논쟁거리까지 깊이 있게 다루고 있다. 뛰어난 통찰력과 날카로운 논리와 철학적 견해로 가득 찬 이 책은 고대 그리스 철학자인 데모크리토스부터 시작해서 논리학, 집합론, 계산 가능성 및 복잡도 이론, 양자 컴퓨팅, 암호학, 양자역학의 해석 등에 이르는 놀라울 정도로 광범위한 영역을 다루고 있다.
여기에 그치지 않고, 시간 여행, 뉴컴의 패러독스, 인류 원리, 로저 펜로즈의 주장에 대한 견해 등도 소개한다. 애론슨만의 친근한 문체와 유머로 물리학, 수학, 컴퓨터 과학, 철학을 비롯한 다양한 배경의 독자들이 양자 컴퓨팅에 쉽게 다가갈 수 있게 해준다.
여기에 그치지 않고, 시간 여행, 뉴컴의 패러독스, 인류 원리, 로저 펜로즈의 주장에 대한 견해 등도 소개한다. 애론슨만의 친근한 문체와 유머로 물리학, 수학, 컴퓨터 과학, 철학을 비롯한 다양한 배경의 독자들이 양자 컴퓨팅에 쉽게 다가갈 수 있게 해준다.
저자: 스콧 애론슨
01장. 원자와 빈 공간
02장. 집합
03장. 괴델, 튜링, 그 동지들
04장. 정신과 기계
05장. 고생대 복잡도 이론
06장. P와 NP, 그 동지들
07장. 무작위성
08장. 암호화
09장. 양자
10장. 양자 컴퓨팅
11장. 펜로즈
12장. 결잃음과 숨은 변수
13장. 증명
14장. 양자 상태는 얼마나 클까?.
15장. 양자 컴퓨팅에 대한 회의론
16장. 학습
17장. 대화형 증명, 회로 하한과 몇 가지 주제
18장. 인류 원리 갖고 놀기
19장. 자유 의지
20장. 시간 여행
21장. 우주론과 복잡도
22장. 무엇이든 물어보세요
02장. 집합
03장. 괴델, 튜링, 그 동지들
04장. 정신과 기계
05장. 고생대 복잡도 이론
06장. P와 NP, 그 동지들
07장. 무작위성
08장. 암호화
09장. 양자
10장. 양자 컴퓨팅
11장. 펜로즈
12장. 결잃음과 숨은 변수
13장. 증명
14장. 양자 상태는 얼마나 클까?.
15장. 양자 컴퓨팅에 대한 회의론
16장. 학습
17장. 대화형 증명, 회로 하한과 몇 가지 주제
18장. 인류 원리 갖고 놀기
19장. 자유 의지
20장. 시간 여행
21장. 우주론과 복잡도
22장. 무엇이든 물어보세요
★ 이 책의 대상 독자 ★
과학 분야의 배경 지식을 갖춘 독자나 물리학, 컴퓨터 과학, 수학, 철학을 전공하는 학생이라면 누구나 쉽게 접근할 수 있다.
★ 이 책의 구성 ★
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 완전 문제와 창의성, 슈퍼-양자 상관관계, 무작위 알고리즘의 역무작위화, 과학과 종교와 이성의 본질, 컴퓨터 과학이 물리학의 한 분야가 아닌 이유 등을 다룬다.
과학 분야의 배경 지식을 갖춘 독자나 물리학, 컴퓨터 과학, 수학, 철학을 전공하는 학생이라면 누구나 쉽게 접근할 수 있다.
★ 이 책의 구성 ★
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 완전 문제와 창의성, 슈퍼-양자 상관관계, 무작위 알고리즘의 역무작위화, 과학과 종교와 이성의 본질, 컴퓨터 과학이 물리학의 한 분야가 아닌 이유 등을 다룬다.
