1. 소개와 개요

1.1 전체적 관점

양자계산 및 양자정보란 양자역학계 quantum mechanical system 을 사용해 수행할 수 있는 정보 처리 작업에 대한 연구다. 양자역학계를 사용해 정보 처리를 수행하기까지는 오랜 시간이 걸렸다. 그 이유를 알려면 양자계산 및 양자정보에 근본적인 아이디어를 제공한 각 분야를 차례로 돌아봐야 한다. 

1.1.1 양자계산 및 양자정보의 역사

20세기 말 물리학 이론(고전물리학)으로는 에너지가무한대로 되는 자외선 파탄, 또는 전자가 회전하면서 점점 원자핵 쪽으로 떨어지는 등의 이상한 예측이 나오고 있었다. 이는 원자와 방사선을 잘 알게 되면서 이러한 설명은 점차 설 자리를 잃게 되었다.

1920 년대 초반에 이 위기는 정점에 이르렀고 양자역학이라는 현대 이론이 탄생하게 되었다. 그 이후 양자역학은 과학의 필수 불가결한 부분이 되었으며 원자 구조, 별의 핵융합, 초전도체, DNA 구조, 자연의 소립자를 포함해 모든 것에 성공적으로 적용됐다.

양자역학은 물리이론을 세우기 위한 하나의 수학적 틀 또는 규칙 집합이다. 예를 들변 원자와 빛의 상호작용을 아주 정확하게 묘사하는 양자전기역학 quantum electrodynamics 라는 물리 이론이 있다. 양자전기역학은 영자역학의 틀 안에서 만들어지지만 양자역학에 의해 결정되지 않는 특정 규칙도 포함한다. 

양자역학과 특정 물리 이론의 관계는 컴퓨터의 운영체제와 특정 애플리케이션 소프트웨어의 관계와 비슷하다. 운영체제는 기본 매개변수와 작동 모드를 설정할 뿐, 애플리케이션이 특정 작업을 수행하는 방식에는 간여하지 않는다. 

1980 년대 초, 양자효과 quantum effect 를 사용하면 빛보다 빨리 신호를 보내는 것이 가능할지에 관심이 일어났다(아인슈타인의 상대성 이론에 따르면 불가능하다). 이 문제의 해법은 알려지지 않은 양자상태를 복제할 수 있는지, 즉 양자상태의 복사본을 만들 수 있는지에 달려 있었다. 복제가 가능하다면 양자효과를 사용해 빛보다 빨리 신호를 보내는 것이 가능한 것이다.

그러나 양자역학에서는 일반적으로 복제가 불가능하다. 1980년대 초에 나온 이 복제불가 정리 no-cloning theorem 은 양자계산 및 양자정보의 초기 결과 중 하나다. 이후 복제불가 정리가 많이 개선돼 이제는 양자복제 장치가 얼마나 잘 작동할 수 있는지 알 수 있는 개념적 도구들을 갖게 됐다. 이러한 도구들은 차례로 양자역학의 다른 측면을 이해하는 데 적용됐다.

양자계산과 양자정보의 발전에 기여했던 관련 연구는 역사적으로 1970년대 단일 양자계를 완벽히 제어하는 능력을 확보하는 데에 대한 관심이었다. 1970년대 이전의 양자역학 응용물에 대해서는 대개 엄청난 수의 양자역학계가 들어간 벌크 샘플을 전체적인 수준에서 제어해야 했고, 그중 어느 계도 직접 접근할 수 없었다. 예를 들어 초전도는 양자역학으로 잘 설명된다. 그러나 초전도체에서는 거대한 전도성 금속 샘플이 들어가기 때문에 우리는 양자역학적 성질의 몇 가지 측면만을 조사할 수 있을 뿐, 초전도체를 구성하는 각각의 양자계에는 접근이 불가능하다. 

입자 가속기와 같은 계는 개별 양자계에 제한적으로 접근할 수 있지만 앞서와 마찬가지로 그 하위계에 대해서는 거의 제어할 수 없다.

1970 년대 이후 단일 양자계를 제어하기 위한 기술이 많이 개발됐다. 예를 들어 하나의 원자를 원자트랩에 가두고 나머지 세계로부터 고립시켜 그 거동의 여러 측면을 아주 정밀하게 조사할 수 있는 방법이 개발된 것이다. 주사 터널 현미경은 원자를 한 개씩 이동시키며 원자 배열을 자유롭게 만들어내는 데 사용됐다. (전자를 하나씩 이동시키는 전자 기기가 나온 것)

이렇게 단일 양자계를 완벽히 제어해야 하는 이유는 무엇일까? 단일 양자계를 완전히 제어함으로써 우리는 새로운 현상을 발견하리라는 희망을 안고 자연의 미지 영역을 탐구하고 있다. 단일 양자계를 완전히 제어하고 더 복잡한 계로 넓혀 나간다면 또 무엇을 발견하게 될까?

양자계산 및 양자정보는 이러한 진행에 자연스레 맞아 들어간다. 양자계산 및 양자정보를 이용하면 단일 양자계를 더 잘 조작하기 위한 방법을 고안하는 사람들은 다양한 난이도로 유용한 도전을 할 수 있고, 새로운 실험 기법 개발에 힘을 얻으며 가장 흥미로운 실험 방향을 알 수 있다. 

역으로 말하면 양자계산 및 양자정보의 응용에 있어 양자역학의 힘을 활용하려면 단일 양자계를 제어하는 능력이 필수다.

몇 개의 양자비트(또는 큐비트) 로 수십 개의 연산을 할 수 있는 소형 양자 컴퓨터 정도가 양자계산에서 최첨단 기술을 보여준다. 양자 암호학에 대한 실험용 원형이 시연됐으며 현실적인 애플리케이션에 이용할 수 있는 수준에 이르렀다. 하지만 대규모 양자정보 처리를 현실화하기 위한 기술을 개발하기에는 큰 도전이 되고 있다.

컴퓨터 과학에서 무어의 법칙(컴퓨터의 성능이 2년마다 2배씩 증가)은 컴퓨터 제작 기술에 대한 기존의 접근법으로는 크기 면에서 근본적인 어려움에 부딪히기 시작했다. 전자기기가 작아지면서 양자효과로 인해 그 기능이 방해받기 시작한 것이다.

무어의 법칙이 궁극적으로 실패했을 때 취할 수 있는 한 가지 해결책은 다른 컴퓨팅 패러다임으로 이동하는 것이다. 그러한 패러다임은 양자계산 이론을 따르며 고전물리학 대신 양자역학을 이용해 계산을 한다는 발상에 바탕을 둔다. 

일반 컴퓨터는 양자 컴퓨터를 시뮬레이션하는 데 사용할 수 있지만 효율적인 방법으로 시뮬레이션하는 것은 불가능한 것으로 나타났다. 그런 까닭에 양자 컴퓨턴는 속도 이점을 갖고 있다. 

양자 컴퓨터의 효율적 시뮬레이션과 비효율적 시뮬레이션이란 무슨 뜻일까? 이에 대한 아이디어는 계산 복잡도 computational complexity 분야에 의해 수학적으로 정확해졌다. 문제의 크기를 시간에 대한 다항식으로 풀어내는 것이다. 이러한 주목을 통해 다음과 같이 처치-튜링 논제의 강화 버전이 나왔다.

어떠한 알고리즘 프로세스라도 튜링머신을 사용해 효율적으로 시뮬레이션할 수 있다.

핵심은 효율적이라는 단어다. 이 논제가 옳다면 알고리즘을 수행하는 데 있어 어떤 기계 타입을 사용하는지 간에 그 기계를 효율적으로 시뮬레이션할 수 있다는 뜻이다. 

강한 처치-튜링 논제에 대한 도전 과제 중 하나는 아날로그 계산 분야다. 튜링 이후 여러 연구 팀은 튜링머신에서 효율적인 솔류션이 없다고 생각되는 문제를 특정 유형의 아날로그 컴퓨터가 효율적으로 해결할 수 있다는 것을 알아냈다. 

안타깝게도 아날로그 계산의 경우, 아날로그 컴퓨터에 현실적으로 노이즈가 존재하는 것으로 가정하면 모든 경우에 있어서 그 강력함이 사라지는 것으로 판명됐다. 

즉, 튜링머신에서 효율적으로 해결할 수 없는 문제는 아날로그 컴퓨터에서도 효율적으로 해결할 수 없다.

이(계산모델의 효율성을 평가할 때 현실적인 노이즈의 영향을 고려해야 한다) 는 양자계산 및 양자정보의 초기 과제 중 하나였으며, 양자 오류정정 코드 및 결함허용 양자계산의 이론 개발로 이어졌다. 이런 까닭에 아날로그 계산과 달리 양자계산은 원칙적으로 한정된 양의 노이즈를 자동으로 해결하며 계산사의 장점을 여전히 지닐 수 있었다.

무작위 알고리즘은 강한 처치-튜링 논제에 도전을 제기하며, 결정론적 튜링머신에서 효율적으로 해결할 수 없어도 효율적으로 해결할 수 있는 문제가 존재한다고 제안한다. 

어떠한 알고리즘 프로세스라도 확률론적 튜링머신을 사용해 효율적으로 시뮬레이션 할 수 있다.

어떤 다른 문제를 양자 컴퓨터가 고전 컴퓨터보다 더 빠르게 해결할 수 있을까? 우리는 모른다. 좋은 양자 알고리즘을 내놓는 것은 어려울 것이다. 그 이유는 설계자가 고전 컴퓨터에서 알고리즘 제작 때는 마주치지 않았던 두 가지 어려운 문제에 직면하기 때문이다. 

1. 인간의 직감은 고전적인 세계에 뿌리를 두고 있다. 알고리즘 제작에 도움이 되는 직관을 사용한다면, 그 알고리즘 아이디어는 고전적인 아이디어가 될 것이다. 
2. 양자역학적 알고리즘을 설계하는 것 뿐만 아니라 그 알고리즘은 기존의 고전 알고리즘보다 우수해야 한다. 

양자 컴퓨터를 고전 컴퓨터보다 더 강력하게 만드는 것은 무엇알까? 이러한 질문에 대한 답변은 거의 나오지 않았다. 

양자계산 및 양자정보에 기여한 또 다른 사고의 역사를 본다. 1948년 클로드 섀넌은 현대 정보통신 이론에 대한 기초를 마련한 논문을 발표했다.

섀넌의 업적의 핵심은 정보의 개념을 수학적으로 정의했다는 점일 것이다. 많은 수리과학에서는 기본적인 정의를 선택할 때 상당한 유연성을 발휘한다. 

정보 소스 개념을 수학적으로 정의하는 방법에 대해 어떻게 생각하는가? 섀넌이 제시한 정의 덕택에 이해의 폭이 넓어졌고 많은 실제 통신 문제를 정확히 반영하고 풍부한 구조를 갖춘 이론과 다양한 심층 결과가 나왔다.

섀넌은 통신채널을 통한 정보통신과 관련된 두 가지 주요 의문에 관심이 있었다. 첫째, 통신채널을 통해 정보를 보내는 데 필요한 자원은 무엇일까? 예를 들어 전화 회사는 주어진 전화선을 통해 안정적으로 전송할 수 있는 정보의 양을 알아야 한다. 둘째, 통신 채널의 노이즈로부터 보호된 상태로 정보를 전송할 수 있을까?

섀넌은 정보이론의 두 가지 기본 원리를 증명함으로써 이 두가지 의문에 답했다.

1. 섀넌의 무노이즈 채널 코딩 정리는 정보 소스의 출력을 저장하는 데 필요한 물리적 자원을 양으로 전한다. 
2. 노이즈 채널 코딩 정리는 노이즈가 있는 통신채널을 통해 안정적으로 전송할 수 있는 정보의양을 정한다. 섀넌은 노이즈가 있는 상태에서 안정적인 전송을 수행하려면 오류정정 코드를 사용해 전송되는 정보를 보호하면 된다는 것을 보였다.

섀넌은 노이즈 채널 코딩 정리는 오류정정 코드로 감당할 수 있는 보호의 상한선을 제공한다. 연구자들은 섀넌의 정리가 설정한 상한선에 근접하기 위해 시도하며 더 좋고 많은 클래스의 오류정정 코드들을 만들어 냈다. 

양자정보이론은 비슷한 발전으로 이어졌다. 1995년 벤 슈마허는 섀넌의 무노이즈 코딩 이론과 비슷한 이론을 내놓았는데, 그 과정에서 양자비트, 큐비트를 현실의 물리적 자원으로 정의했다. 하지만 섀넌의 노이즈 채널 코딩 정리와 비슷한 정리가 양자정보 분야에 확립되지는 않았다. 그럼에도 고전적인 이론과 유사하게 양자 오류; 정정 이론이 개발돼 이미 언급했듯이 양자 컴퓨터가 노이즈 환경에서 효율적으로 계산할 수 있으며 노이즈 양자채널을 통한 통신도 안정적으로 이루어질 수 있다.