양자 컴퓨팅의 이해 : 기본 개념과 사례로 알려주는

엘레노어리에펠,볼프강폴락

저자:엘레노어리에펠(EleanorRieffel)
NASA에이미스연구소의연구원이다.

저자:볼프강폴락(WolfgangPolak)
컴퓨터과학컨설턴트다.

역자:남기환
중앙대학교에서물리학과수학을전공하고한국방송통신대학교에서컴퓨터과학,영어영문학을전공했다.중앙대학교에서입자물리학석사를취득하고,카이스트물리학과박사과정을중퇴했다.광주과학기술원고등광기술연구소를거쳐현재광통신관련업체에서연구원으로재직중이다.

1장.소개

1부.양자기초개념

2장.단일큐비트양자계
2.1편광된광자의양자역학
2.1.1간단한실험
2.1.2양자역학적설명
2.2단일양자비트
2.3단일큐비트측정
2.4양자키분배통신규약
2.5단일큐비트계의상태공간
2.5.1상대위상과전역위상
2.5.2단일큐비트의상태공간에대한기하학적관점
2.5.3일반적인양자상태공간에대한설명
2.6참고문헌
2.7연습문제

3장다중큐비트계
3.1양자상태공간
3.1.1벡터공간의직합
3.1.2벡터공간의텐서곱
3.1.3n큐비트계의상태공간
3.2얽힌상태
3.3다중큐비트측정의기초
3.4얽힌상태를사용하는양자키분배
3.5참고문헌
3.6연습문제
4장다중큐비트상태의측정
4.1선형변환에대한디랙의브라/켓표기법
4.2측정에대한투영연산자
4.3측정에대한에르미트연산자형식체계
4.3.1측정가설
4.4EPR역설과벨의정리
4.4.1벨의정리에대한실험장치
4.4.2양자역학이예측하는결과
4.4.3벨의정리의특수한경우:임의의국소적숨은변수이론이예측하는결과
4.4.4벨의부등식
4.5참고문헌
4.6연습문제

5장.양자상태변환
5.1유니타리변환
5.1.1불가능한변환:복제불가원리
5.2몇가지단순한양자게이트
5.2.1파울리변환
5.2.2아다마르변환
5.2.3단일큐비트변환에서다중큐비트변환
5.2.4제어형NOT게이트와다른단일제어형게이트
5.3단순한게이트의응용
5.3.1고밀도부호화
5.3.2양자상태원격전송
5.4유니타리변환을양자회로로구현하기
5.4.1단일큐비트변환의분해
5.4.2단일제어형단일큐비트변환
5.4.3다중제어단일큐비트변환
5.4.4일반적인유니타리변환
5.5만능근사게이트집합
5.6표준회로모형
5.7참고문헌
5.8연습문제

6장고전계산의양자화
6.1가역적인고전계산에서양자계산으로
6.1.1단순한고전게이트의가역적판본과양자적판본
6.2고전회로의가역적구현
6.2.1순진한가역적구현
6.2.2일반적구성
6.3양자구현을위한언어
6.3.1기본개념
6.3.2함수
6.4산술연산을위한몇가지예제프로그램
6.4.1AND연산의효율적인구현
6.4.2다중제어형단일큐비트변환의효율적구현
6.4.3제자리덧셈
6.4.4모듈러덧셈
6.4.5모듈러곱셈
6.4.6모듈러지수함수
6.5참고문헌
6.6연습문제

2부.양자알고리듬

7장양자알고리듬소개
7.1중첩상태에서계산하기
7.1.1월시-아다마르변환
7.1.2양자병렬성
7.2복잡도개념
7.2.1질의복잡도
7.2.2통신복잡도
7.3간단한양자알고리듬
7.3.1도이치문제
7.4양자서브루틴
7.4.1양자서브루틴에서얽히지않은임시큐비트의중요성
7.4.2기저벡터의부분집합에대한위상변화
7.4.3상태에따른위상이동
7.4.4상태의존단일큐비트진폭이동
7.5몇가지간단한양자알고리듬
7.5.1도이치-조사문제
7.5.2베른슈타인-바지라니문제
7.5.3사이먼문제
7.5.4분산계산
7.6양자병렬성에대한설명
7.7기계모형과복잡도분류
7.7.1복잡도분류
7.7.2복잡도:알려진결과
7.8양자푸리에변환
7.8.1고전푸리에변환
7.8.2양자푸리에변환
7.8.3빠른푸리에변환의양자회로
7.9참고문헌
7.10연습문제

8장쇼어알고리듬
8.1주기찾기의고전적인축약법
8.2쇼어의인수분해알고리듬
8.2.1양자적핵심
8.2.2측정된값에서주기를고전적으로추출하기
8.3쇼어알고리듬을설명하는예제
8.4쇼어알고리듬의효율
8.5내부측정의생략
8.6일반화
8.6.1이산로그문제
8.6.2숨은부분군문제
8.7참고문헌
8.8연습문제
9장그로버알고리듬과일반화
9.1그로버알고리듬
9.1.1개괄
9.1.2준비
9.1.3반복단계
9.1.4반복횟수는?
9.2진폭증폭
9.2.1진폭증폭의기하학적해석
9.3그로버알고리듬의최적성
9.3.13개의부등식으로축약
9.3.2세부등식의증명
9.4그로버알고리듬과진폭증폭의비무작위화
9.4.1접근법1:각단계고치기
9.4.2접근법2:마지막단계만고치기
9.5답의개수를모를때
9.5.1반복횟수가변하는경우
9.5.2양자계수
9.6그로버알고리듬과진폭증폭의현실적의미
9.7참고문헌
9.8연습문제

3부.얽힌부분계와강건한양자계산

10장양자부분계와얽힌상태의성질
10.1양자부분계와섞인상태
10.1.1밀도연산자
10.1.2밀도연산자의성질
10.1.3섞인단일큐비트상태의기하학
10.1.4폰노이만엔트로피
10.2얽힌상태의분류
10.2.1이분할양자계
10.2.2LOCC등가성으로이분할순수상태분류하기
10.2.3이분할섞인상태의얽힘정량화하기
10.2.4다분할얽힘
10.3측정에대한밀도연산자형식체계
10.3.1밀도연산자의측정
10.4양자부분계의변환과결어긋남
10.4.1초연산자
10.4.2연산자합분해
10.4.3양자상태변환과측정사이의관계
10.4.4결어긋남
10.5참고문헌
10.6연습문제
11장양자오류보정
11.1양자오류보정부호의세가지간단한사례
11.1.1단일비트뒤집힘오류를바로잡는양자부호
11.1.2단일큐비트위상뒤집힘오류에대한부호
11.1.3모든단일큐비트오류에대한부호
11.2양자오류보정부호에대한작업틀
11.2.1고전오류보정부호
11.2.2양자오류보정부호
11.2.3고전부호에대해바로잡을수있는오류집합
11.2.4양자부호에대해바로잡을수있는오류집합
11.2.5고전부호를사용한오류바로잡기
11.2.6양자부호를사용해오류진단하고바로잡기
11.2.7다중블록을통한양자오류보정
11.2.8부호화된양자상태로계산하기
11.2.9바로잡을수있는오류의중첩과섞임상태는바로잡을수있다
11.2.10고전적인독립오류모형
11.2.11양자독립오류모형
11.3CSS부호
11.3.1쌍대고전부호
11.3.2쌍대조건을만족하는고전부호에서CSS부호의구성
11.3.3스테인부호
11.4안정자부호
11.4.1양자오류보정에대한이진관측가능량
11.4.2양자오류보정에대한파울리관측가능량
11.4.3오류의진단과바로잡기
11.4.4부호화된안정자상태에대한계산
11.5안정자부호로서의CSS부호
11.6참고문헌
11.7연습문제

12장결함내성및강건한양자계산
12.1강건한양자계산을위한무대준비
12.2스테인부호를사용한결함내성계산
12.2.1징훗값계산문제
12.2.2결함내성징훗값추출과오류보정
12.2.3스테인부호에대한결함내성게이트
12.2.4결함내성측정
12.2.5|?π/4>의결함내성적상태준비
12.3강건한양자계산
12.3.1이어붙이기부호화
12.3.2문턱값정리
12.4참고문헌
12.5연습문제

13장양자정보처리더알아보기
13.1양자알고리듬더보기
13.2양자계산의한계
13.3강건한양자계산을위한더많은기법들
13.4양자계산의회로모형의대안
13.4.1측정기반클러스터상태양자계산
13.4.2단열적양자계산
13.4.3홀로노미양자계산
13.4.4위상학적양자계산
13.5고전계산에대한시사점
13.6양자컴퓨터만들기
13.7양자계시뮬레이션
13.8양자계산능력은어디서오는가?
13.9양자역학이그렇게정확하지않다면어떻게되는가?

부록A양자역학과확률론사이의몇가지관계
부록B숨은가환부분군문제의풀이법

부록A양자역학과확률론사이의몇가지관계
부록B숨은가환부분군문제의풀이법

이책의대상독자

이책의의도는컴퓨터과학자,공학자,수학자그리고충분한수학지식을갖고서이주제에관심을가진누구에게나양자컴퓨터를다뤄볼수있도록만드는것이다.전체적으로벡터공간,선형변환,고윳값,고유벡터와같은학부생수준의기본적인선형대수학개념이사용된다.몇몇절은더어려운수학을요구할것이다.8.6.1절,8.6.2절,부록B,11장의대부분에서는군론에익숙해야할것이다.군론은상자안에서설명할것이다.다만군론에대해배운적이없는독자라면군론을다룬교재의도움을받거나이절들을건너뛰어야할것이다.

지은이의말

양자컴퓨터는양자물리학,컴퓨터과학,정보이론의아름다운결합이다.이책의목적은여러분야의독자가이놀라운연구분야에접근할수있도록하는것이다.특히양자컴퓨터와통상적인컴퓨터사이를구분짓는개념과표기법의장벽을넘어갈수있도록독자에게다리를놓아주려고한다.

이책은이론에관한책이다.통상적인컴퓨터를뒷받침하는고전적모형을양자적모형으로바꿨을때무엇이변할까?전문가조차어떤접근법이가장성공적일지예측하는것이여전히불가능할만큼,이제갓만들어진활발한분야인양자컴퓨터를만들기위해현재진행중인노력에대해서는간략히설명한다.그대신원동력이된물리학에서양자계산을논의하는데중요한이론적기초를다룬다.이런이유로,이책은이론이왜그렇게정의됐는지설명하기위해서양자물리와실험을논의한다.
양자계산에서사용되는개념을정확히정의하고,미묘한차이를강조한다.이러한엄격함은FXPAL/PARC의합동독서모임에서활동하며이분야를잘알지못하는여러저자와논문을읽었던경험에일부자극을받은것이다.예를들어양자상태와그상태를표현하는벡터를구분하는것에주의해야한다.이책에서는어떤개념이기저에의존하고(예를들어중첩)어떤것이그렇지않은지(예를들어얽힘)그리고특정한개념(예를들어얽힘)의특정한텐서분해에대한의존성을강조한다.텐서분해와직합분해는둘다양자역학에서널리사용되는데,양자역학과고전확률적인상황에서그둘의차이를명시적으로따져본다.정의는주의깊게제시된다.예를들어밀도연산자나섞인상태에대한공리에서시작하는대신,하부체계에대한단독측정으로부터그하부체계에관해어떤것들을연역해낼수있는지논의하는것으로이개념들의정의를제시한다.

이론만다루는것그리고양자컴퓨터를만드는방법을다루지않는것의한가지장점은여기에필요한양자물리학과이를뒷받침하는수학의양이줄어든다는점이다.이책은이책자체로필요한양자역학의모든것을전개할수있다.양자물리학을미리알아야할필요가없다.여기서는표준적인양자알고리듬과양자키분배와양자원격작용과같은다른양자정보처리작업에대해다루기전에양자상태공간,양자측정,얽힘과같은기본개념에대해주의깊고정확한설명을제시한다.

옮긴이의말

최근과학계뉴스에따르면전세계적으로양자컴퓨터에대한관심이높아지고있다.심지어과학계뿐만아니라산업계전반을비롯한국가적인관심까지도받는중이다.이는아마도예전에는단지이론적가능성에불과했고,공상과학소설에서만등장하는환상의존재였던양자컴퓨터가이제는가까운미래에실용적인수준에서사용가능하다는판단이서기때문이리라.이에따라구글,IBM,마이크로소프트,아마존등세계적인컴퓨터기업에서양자컴퓨터에대한연구와투자를하고있다.

양자컴퓨터가관심을받는이유는고전컴퓨터에서는현실적으로빠르게풀수없을것으로보이는문제를유의미한시간내에빠르게풀수있을것으로보이기때문이다.물론양자컴퓨터에대한연구가양자역학자체를더깊이이해하고기초과학을더발전시키는등전반적인물리학연구에주는함의가충분히있겠으나,기초과학을벗어나컴퓨터공학,암호학,경제학등다양한응용분야에서도관심을보이는것은고전컴퓨터를초월할것이라는기대감때문일것이다.

그런데이처럼많은사람이양자컴퓨터에대해관심은갖고있지만실제로양자컴퓨터의작동원리를이해하는이는많지않다.양자컴퓨터의작동원리의바탕이되는양자역학을이해하는것부터쉽지않기때문이다.양자컴퓨터를이해하려면양자상태로이뤄진큐비트,그큐비트의얽힘,얽힌큐비트에작용하는양자연산자와같은개념을이해해야하는데,이와같은양자개념을고전적인컴퓨터이론에서배워온비트와논리게이트개념으로설명하려고들면혼란에빠질뿐제대로이해하기가어려워서이다.아마20세기초에양자역학이고전역학을대체하는것으로소개됐을때물리학자들이받은충격을고전적인컴퓨터이론을공부한현재의컴퓨터엔지니어들이양자컴퓨터를배워야할때고스란히받을것이다.

문제는그작동원리를몰라도수많은애플리케이션이등장해실생활에현실적도움을주고있는고전컴퓨터와는달리,이제갓태어나그쓸모를찾기시작하는양자컴퓨터는작동원리를알지못하면고전컴퓨터보다나을것이없다는점이다.먼미래에양자컴퓨터가대중화되고일상적으로사용하게되면그원리를모르고도사용할수있겠지만,현시대를살아가는컴퓨터엔지니어들이양자컴퓨터를사용하고싶다면어쩔수없이고전컴퓨터와다른양자적인컴퓨터이론을공부해야만한다.이는진공관을이용해서만들어졌던초창기컴퓨터를사용하기위해서는진공관의작동원리를대충이나마이해하고있어야했던것과마찬가지일것이다.

그렇다고양자컴퓨터를사용하기위해서물리학전체를다시공부한다는것은배보다배꼽이더커지는격이다.바로이지점에서이책을추천할수있다.큐비트,양자게이트,양자얽힘과같은기본개념에서시작해쇼어알고리듬,그로버알고리듬과같은중요한양자알고리듬을다루고,양자엔트로피,양자오류보정,강건한양자계산과같은전문적인주제까지훑어본다.이번역서가부디한국어판독자들에게저자의매력적인설명을훼손하지않고전달하기를바라며,아울러양자컴퓨터에관심있는독자들이이책을읽고보다깊이있는주제들을연구할수있는기초를다지게되길바란다.