사례로 설명한 양자 컴퓨팅
일반 컴퓨터와의 비교
*출처(클릭)
YK Sugi
2018.10.22
(전략)
양자 컴퓨터란 무엇인가?
(중략)
‘양자 컴퓨터는 일반 컴퓨터보다 효율적으로 특정 유형의 산출(computation) 작업을 수행할 수 있도록 양자 역학(quantum mechanics)을 활용하는 일종의 컴퓨터를 말한다.’
이 문장 만으로는 알 수 있는 것이 적으므로, 간단한 사례를 들어 영자 컴퓨터가 진짜 무엇인지 알려 주겠다.
양자 컴퓨터의 작동 원리를 설명하기 위해 먼저 일반 컴퓨터에 대해 간략히 설명할 것이다.
1. 일반 컴퓨터는 어떻게 정보를 저장하나?
일반 컴퓨터는 ‘0’과 ‘1’을 연이어 사용해 정보를 저장한다.
숫자, 문자, 그리고 이미지 등 서로 다른 유형의 정보가 이러한 방식으로 표현된다.
연이은 ‘0’과 ‘1’을 사용하는 각 단위를 비트(bit)라 부른다. 따라서 1 비트는 ‘0’ 또는 ‘1’로 설정된다.
1. 양자 컴퓨터는 어떠한가?
영자 컴퓨터는 정보 저장에 비트(bit)를 사용하지 않는다. 그 대신 큐빗(qubit)이라 불리는 단위를 사용한다.
각 큐빗은 1이나 0으로 설정되지 않을 뿐만 아니라 1과 0으로 설정된다. 이건 무슨 의미일까?
간단한 사례를 들어 설명하겠다. 이 사례는 인위적으로 구성된 사례이지만, 양자 컴퓨터 작동 방식을 이해하는데 효과적일 것이다.
1. 양자 컴퓨터 작동 방식을 이해하기 위한 간략한 사례
당신이 여행사를 운영하고 있다고 가정하자. 그리고 한 그룹의 관광객을 한 장소에서 다른 장소로 이동시키려 한다.
사례의 간략함을 유지하기 위해 대상 인원은 3명 - 앨리스, 벡키, 그리고 크리스 - 으로 한다.
이동을 위해 2 대의 택시를 예약했고, 각 택시에 누구를 태울지 정하고자 한다.
그리고 당신은 누가 누구와 친구이고 누구와 적인지에 관한 정보를 가지고 있다고 가정한다.
그 정보는 다음과 같다:
. 앨리스와 벡키는 친구 사이이다.
. 앨리스와 크리스는 적 관계이다.
. 벡키와 크리스는 적 관계이다.
그리고 당신의 목표는 이들 3명의 그룹을 2 대의 택시에 나누어 태워 다음 2 가지 목적을 달성하는 데 있다고 가정한다:
. 동일 택시를 공유하는 친구 관계의 수를 극대화한다.
. 동일 택시를 공유하는 적 관계의 수를 최소화한다.
이것이 이 문제의 기본 전제이다. 자, 일반 컴퓨터를 활용하여 이 문제를 어떻게 풀지에 대해 생각해 보자.
1. 일반 컴퓨터를 사용한 문제 풀이
일반 컴퓨터로 이 문제를 풀기 위해 먼저 비트를 사용하여 관련 정보를 저장하는 방식을 알아내야 할 것이다.
각 택시에 Taxi#1, Taxi#0으로 레이블을 붙인다.
그런 다음 각 택시는 3비트의 자리가 있고, 이를 이용해 누가 어떤 차에 탈지를 표현하자.
예를 들면, 3 비트를 0,0, 그리고 1로 설정하여 다음과 같이 표현해 보자:
앨리스가 택시#0에 탄다.
벡커가 택시#0에 탄다.
크리스가 택시#1에 탄다.
각 인원별로 2 번의 선택지가 있으므로, 이 그룹의 인원을 2대의 택시에 나누어 태우는 데는 2*2*2 = 8 가지 방식이 있다.
모든 예상 구성을 목록으로 만들면 아래와 같다:
A | B | C
0 | 0 | 0
0 | 0 | 1
0 | 1 | 0
0 | 1 | 1
1 | 0 | 0
1 | 0 | 1
1 | 1 | 0
1 | 1 | 1
*A=Alice, B=Becky, C=Chris
3 비트를 사용하면 이렇게 탑승자를 표현할 수 있다.
1. 각 인원 구성에 대한 점수(score) 산출
일반 컴퓨터를 이용해 최적의 구성을 결정해 보자.
그리고 점수를 계산할 방법을 정의해 보자. 이 점수는 이전에 언급한 2 가지 목표를 달성할 해결책이 무엇인지를 표현할 것이다.
. 동일 택시를 공유하는 친구 관계의 수를 극대화한다.
. 동일 택시를 공유하는 적 관계의 수를 최소화한다.
다음과 같이 공식을 구성하자:
#
각 구성 방식에 관한 점수 = (동일 차량을 공유한 친구 간 결합의 수) - (동일 차향을 공유한 적간 결합의 수)
#
예를 들면, 앨리스, 벡키, 크리스가 한 차에 탄 경우를 가정해 보자. 비트를 이용하면 ‘111’이 된다.
이 경우, 이 차에는 1쌍의 친구(앨리스와 벡키)가 동일한 차량을 공유하고 있다.
하지만, 이 차에는 1쌍의 적(앨리스-크리스, 벡키-크리스)이 타고 있다.
따라서 이 구성의 총 점수는 1-2=-1이다.
1. 문제 해결
이러한 방식으로 이 문제를 해결할 수 있다.
일반 컴퓨터를 사용하여 최상의 구성을 찾아내기 위해 필수적으로 어떤 구성이 가장 높은 점수를 달성하는지 모든 구성을 일일이 살펴보아야 할 것이다.
따라서 다음과 같이 하나의 테이블을 구성하는 것을 생각할 수 있다:
A | B | C | 점수
0 | 0 | 0 | -1
0 | 0 | 1 | 1 <= 가장 점수가 높은 해결책 중 하나
0 | 1 | 0 | -1
0 | 1 | 1 | -1
1 | 0 | 0 | -1
1 | 0 | 1 | -1
1 | 1 | 0 | 1 <= 가장 점수가 높은 해결책 중 하나
1 | 1 | 1 | -1
*A=Alice, B=Becky, C=Chris
이와 같이 2 가지 해결책을 찾았다 - 001과 110. 모두 점수 1을 얻었다.
이 사례는 간략한 예이다. 이 문제의 인원수를 늘리는 만큼 일반 컴퓨터로 문제를 해결하기 더 어려워진다.
우리는 3인의 승차 편성을 위해 8가지 예상 구성을 검토해야 했다.
만일 인원수가 4명이 되면? 2*2*2*2 = 16가지 구성을 산출해야 한다.
만일 인원수가 n명이 되면 2의 n 승만큼의 구성을 계산해서 최상의 솔루션을 찾아야 한다.
인원수가 100명일 경우:
2의 100승 ~= 10의 30승 = 1백만 + 백만 + 백만 + 백만 + 백만 개의 구성이 나온다. 이것은 일반 컴퓨터로 해결하기가 거의 불가능하다.
1. 양자 컴퓨터로 문제 해결하기
(중략)
위 사례를 그대로 사용하면 8가지 예상 구성이 있을 수 있다:
A | B | C
0 | 0 | 0
0 | 0 | 1
0 | 1 | 0
0 | 1 | 1
1 | 0 | 0
1 | 0 | 1
1 | 1 | 0
1 | 1 | 1
*A=Alice, B=Becky, C=Chris
일반 컴퓨터는 3 비트를 사용하여 한 번에 하나의 구성만 산출할 수 있다.
하지만 양자 컴퓨터의 경우, 3 큐빗을 사용하여 동시에 8가지 구성 모두를 산출할 수 있다.
이것이 무슨 의미인지에 대해서는 논쟁의 여지가 있지만 내가 생각하는 바는 이렇다.
먼저, 이 3 큐빗 중 첫 번째 큐빗을 시험하자. ‘0’과 ‘1’로 설정할 경우, 2 가지 평행 세계를 창조하는 것과 같다. (이상하게 들릴지 모르지만 여기서는 그렇게 표현하겠다.)
이 평행 세계 중 하나는 ‘0’으로 설정하고, 다른 하나는 ‘1’로 설정한다.
두 번째 큐빗을 ‘0’과 ‘1’로 설정하면 어떻게 될까? ㄱ럼 4 개의 평행 세계를 창출하는 것과 같다.
첫 번째 세계에서 2개 큐빗은 00으로 설정된다. 두 번째 세계에서는 01로 설정된다. 세 번째 세계는 10으로, 네 번째 세계는 11로 설정된다.
이와 마찬가지로, 3 큐빗 모두를 ‘0’과 ‘1’로 설정할 경우, 8개의 평생 세계가 만들어진다 - 000, 001, 010, 011, 100, 101, 110, 그리고 111.
이것은 생각하기에 이상해 보이지만, 실제 세계에서 큐빗이 어떻게 움직이는지를 해석하는 올바른 방법 중 하나이다.
이 3 큐빗을 산출할 때, 동시에 8개 평행 세계 모두를 한꺼번에 적용한다.
따라서 예상 구성을 순차적으로 하나씩 산출하는 대신, 동시에 모든 구성의 점수를 산출할 수 있다.
이 사례에 대해, 이론적으로 말하면, 양자 컴퓨터는 몇 밀리 초만에 최고의 해결책을 찾아낼 것이다.
(중략)
사실, 이 문제를 해결하기 위해서는 양자 컴퓨터에 2 가지 작업을 부여해야 할 것이다:
. 모든 예상 해결책을 큐빗으로 표현한다.
. 각 예상 구성을 하나의 점수로 전환하는 기능. 이 경우, 이 기능은 동일한 차량을 공유하는 친구 결합 쌍과 적 결합 쌍의 수를 산출하는 기능이다.
이 2 가지 작업을 부여하면, 양자 컴퓨터는 몇 밀리 초만에 최상의 해결책 중 하나를 산출해 낼 것이다.
(중략)
하지만 실제로 양자 컴퓨터를 운용할 때 몇 가지 에러가 있다. 따라서, 최상의 해결책을 찾기 보다, 두 번째, 세 번째 최상의 해결책을 찾아낼 것이다.
이러한 에러들은 문제가 복잡해질수록 더욱 두드러진다.
따라서 실제로는, 아마도 수십 회 혹은 수백 회로 양자 컴퓨터에서 동일한 작업을 진행하길 원할 것이다. 그런 다음 산출된 결과 중에서 최상의 결과를 골라낼 것이다.
1. 양자 컴퓨터는 어떻게 규모 조정을 할까?
언급한 에러는 있지만, 양자 컴퓨터는 일반 컴퓨터가 겪는 것과 같은 규모 조정 문제(scaling issue)는 가지고 있지 않다.
2 대의 차량에 나누어 타야 할 3명의 인원이 있는 경우, 양자 컴퓨터에서 수행해야 할 작업 횟수는 1이다. 양자 컴퓨터는 동시에 모든 예상 구성의 점수를 산출하기 때문이다.
인원이 4명이어도 작업 횟수는 여전히 1이다.
인원이 100명이어도 작업 횟수는 여전히 1이다. 단 한 번의 작업으로, 양자 컴퓨터는 2의 100승 = 10의 30승 = 일 백만 백만 백만 백만 백만 개의 구성을 한 번에 산출한다.
상기와 같이, 아마도 양자 컴퓨터를 수십에서 수백 회 가동하고 산출된 결과에서 최상의 결과를 뽑아내는 것이 최상일 수 있다.
하지만, 일반 컴퓨터에서 동일한 문제를 적용하여 일 백만 백만 백만 백만 백만 회의 동일한 산출 작업을 반복하는 것보다는 나은 방법이다.
(후략)
