스콧 애론슨의 양자 컴퓨팅 강의 (데모크리토스부터시작된 양자 컴퓨팅 | 2022년도 대한민국학술원 선정 교육부 우수학술도서)

스콧애론슨

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

01장.원자와빈공간
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장에서는저자의전공분야이자양자역학과계산복잡도이론을합쳐탄생한양자계산이론(quantumtheoryofcomputation)의기초를소개한다.
11장에서는로저펜로즈경의사상을비평하는시간을갖는다.펜로즈경은사람의뇌는그냥양자컴퓨터가아니라양자중력컴퓨터(quantumgravitationalcomputer)라고주장하는것으로유명하다.그래서사람은튜링계산불가능한문제도풀수있으며,이에대한근거로괴델의불완전성정리를제시한다.이과정에서펜로즈의추측에서일말의진실을발견할수있는지살펴본다.
12장에서는양자역학개념에대한문제점중저자가핵심이라고생각하는것들을하나씩살펴본다.문제는미래가비결정론적이라는것이아니라(그래도상관없다)과거역시비결정론적이라는것이다.여기에대한두가지상반된반응을살펴본다.하나는물리학자들사이에서가장흔하게볼수있는것으로결잃음(decoherence)과열역학제2법칙에서말하는효과적인시간의화살(arrowoftime)을내세우는것이고,다른하나는봄역학과같은‘숨은변수이론(hidden-variabletheory)’에의존하는것이다.숨은변수이론을받아들이지않더라도이를통해나는아주흥미로운수학적질문몇가지를제시한다고생각한다.
13장에서는수학증명의새로운개념(확률론적증명과영지식증명등)을소개한다.그리고이를숨은변수이론의계산복잡도를이해하는데적용해본다.
14장에서는양자상태의크기를가늠해본다.즉,고전정보의지수적양을인코딩하는지여부를따져본다.이질문을양자해석논쟁과연관시켜보고,양자증명과양자조언에대한최신복잡도이론관점의연구결과와도연관시켜본다.
15장에서는양자컴퓨팅에대한회의론자들의주장을고찰해본다.회의론자들은(모두가동의하는사실인)실용적인양자컴퓨터를만드는것이힘들다고말하는것이아니라몇가지근본적인이유로인해근본적으로불가능하다고주장한다.
16장에서는흄의귀납문제를소개한다.이를매개로양자학습이론과양자상태의학습가능성에대한최신연구결과의논의로이어나간다.
17장에서는대화형증명시스템의고전버전과양자버전에관련된몇가지혁신적인결과(예,IP=PSPACE,QIP=PSPACE)를소개하되비상대화회로하한(non-relativizingcircuitlowerbound)으로이어지는것으로,P대NP문제에뭔가실마리를제공할지모르는것을중심으로살펴본다.
18장에서는그유명한인류원리(AnthropicPrinciple)와종말논법(DoomsdayArgument)을소개한다.(당연한얘기지만)굉장히철학적인주제에서출발해사후선택양자컴퓨팅과PostBQP=PP로이어지는식으로얘기를풀어나간다.
19장에서는뉴컴의패러독스와자유의지를살펴본다.이주제는콘웨이-코헨의‘자유의지정리’에대한설명과벨부등식을이용해‘아인슈타인인증무작위수’를생성하는방법으로이어진다.
20장에서는시간여행을다룬다.이제는익숙해진패턴에따라얘기하는데,다양한철학적논의에서시작해닫힌시간꼴곡선의고전컴퓨터나양자컴퓨터는PSPACE와완전히동등한계산능력을갖춘다는것을증명하는것으로마무리한다(이증명에대해흥미로운반론을제시할수있으며여기에대해서도충분히얘기할것이다).
21장에서는우주론,암흑에너지,베켄슈타인한계,홀로그래픽원칙등을소개한다.물론이모든주제는계산의한계와관련해어떤의미가있느냐의관점에서설명한다.예를들어블랙홀을생성할만한에너지를사용하지않고도얼마나많은비트를저장하거나검색할수있는지,이런비트에대해연산을얼마나많이수행할수있는지등을따져본다.
22장은일종의디저트역할을한다.여기나온내용은“QuantumComputingsinceDemocritus”강의의마지막수업에서학생들에게무엇이든지물어보라고하고나서저자가받은질문에답변했던내용을토대로정리한것이다.양자역학의실패,블랙홀과퍼즈볼,계산복잡도에서오라클결과의관련성,NP완전문제와창의성,‘슈퍼-양자’상관관계,무작위알고리즘의역무작위화,과학과종교와이성의본질,컴퓨터과학이물리학의한분야가아닌이유등을다룬다.