2001년 크리스마스 무렵, 캘리포니아의 알마덴(Almaden)의 IBM 실험실에서 처음으로 양자물리 법칙에 따라 계산한 양자 컴퓨터가 공개되었다. 뉴욕타임즈는 "컴퓨터를 변화시키려는 노력이 드디어 새로운 이정표를 만들어내다"라고 대서특필하였고, 1월 초에 르 몽드는 "양자 컴퓨터가 처음 계산을 하다"라는 기사를 실었다. 스위스 신문에 나온 표제는 "15 = 3 x 5"로 역사상 보기 드문 수학방정식 형태의 신문 표제어였다.
7.1. 논리게이트
양자 컴퓨터의 소개에 앞서, 일반적인 컴퓨터에 대해 간단히 알아보자. 컴퓨터는 몇 개의 논리게이트로 이루어져 있고, 사용자로부터 입력을 받아 처리하고 출력한다. 입력과 출력은 이진법으로 "0"과 "1"만 다룬다.
이진법으로 표기된 메시지를 1회용 암호로 암호화하면 메시지와 키의 각 자리에 덧셈 모듈러 2를 수행한다는 것을 앞서 다루었다. 이는 XOR의 논리 함수와 같으며, XOR 외에도 NOT, OR, AND, NAND와 같은 다른 함수들이 진리표(truth table)를 따라 동작한다. 논리게이드들을 더 복잡하게 연속적으로 만드는 것을 논리회로(logic circuit)라고 부른다.
논리회로에서 "0"과 "1"을 다루는 대신에 중첩 상태를 입력하는 것을 생각해보자. "0"과 "1"을 입력할 때 |1> 과 |0> 을 사용하며, 중첩 상태인 (|0> + |1>)√2 는 |1> 과 |0> 을 동시에 함께 처리해야 한다. 기존의 AND, OR, XOR 등의 게이트들은 비가역적(irreversible)이기 때문에 양자 상태와 공존하기 어렵다. 다시 말해, 논리 게이트들은 일방 통행되는 거리와 같다. 비가역적인 이유는 게이트의 입력은 2개이고, 출력은 1개라서, "0"과 "1"로 이루어진 가능한 4가지 조합의 입력들은 결국 2가지 출력으로 나온다. AND 게이트의 결과가 "0"이라면, 가능한 입력 조합은 "0"+"0", "0"+"1", "1"+"0" 이다. 따라서 출력 값을 통해 입력 값을 구할 수 없다. 그러나 양자 역학은 값을 측정하지 않는 한 정보를 잃지 않으므로, 양자 상태를 갖는 논리회로의 게이트는 반드시 가역적(reversible)이어야 한다.
이제, 중첩 상태를 제어 입력으로 사용하고 표적 상태가 |0> 이면 다음과 같다.
위 식을 다시 아래와 같이 쓸 수 있다.
즉 입력 상태는 |00> / √2 와 |10> / √2 의 중첩이라는 의미이다. 이 중첩 상태를 CNOT 에 입력해보자. 양자 상태들은 중첩이 가능하므로 CNOT 게이트의 출력도 두 개의 입력 상태의 중첩이 될 것이다. 그러므로 CNOT 진리표의 복합 입력 상태를 따라 |00 / √2 는 |00> / √2 으로, |10 / √2 은 |11 / √2 로 출력된다. 따라서 위 복합 상태의 CNOT 출력은 다음과 같다.
위 식을 보면 2개의 단일 입자 양자 상태들의 곱으로 나타낼 수 없다는 것을 알 수 있다. 복합 입력 상태 (|00> + |10>) / √2 는 두 개의 단일 입자 상태의 곱 상태인 (|0> + |1>)|0>) / √2 와 같았지만, CNOT 의 출력 상태는 분리되지 않는다. 다시 말해, CNOT 의 입력이 충접 상태과 |0>의 상태에서 출력 상태는 얽힘 상태로 바뀌었다. 얽힘 상태의 양자들은 특이한 성질을 갖는다. 두 양자 비트 중의 하나를 측정하면 동시에 다른 입자의 양자 상태가 결정된다. 하지만 측정 전에는 어떤 양자 비트에 대해서도 정확한 상태를 알 수 없다.
CNOT 게이트의 출력 상태를 보면 복제 불가능의 원리가 깨어지는 것 같이 보일 수 있다. 그러나 CNOT 은 '미지(0과 1이 아닌 그 사이의 어떤 값)'인 중첩 상태를 제어 입력으로 하면 단순하게 출력이 얽힘 상태로 유도된 것 뿐이다.
그리고 양자 논리회로에서 자주 사용되는 토폴리 게이트(Toffoli gate)[2]의 진리표는 다음과 같다.
다시 돌아가서, 제어 입력과 표적 입력이 모두 중첩 상태일 때, 두 상태를 곱하여 전개하면,
상기 식이 되고, 정리하면 아래의 식이 된다.
위 식에 CNOT 게이트를 적용하면 아래와 같다. 밑줄은 CNOT 게이트를 통해 상태가 변한 비트이다.
위 상태는 얽힘 상태가 아니므로 두 상태의 곱으로 쓸 수 있다.
제어 입력을 중첩 상태로, 표적 입력을 단순 기저 상태로 입력하면 얽힘 상태가 나오는데, 표적 입력에도 중첩 상태를 사용하면 간단한 출력 상태를 얻게 된다. 이 경우 두 개의 출력은 중첩 상태들의 곱으로 분리된다. 기저 상태 |0> 과 |1>을 사용하여 중첩 상태를 측정하면 마구잡이의 결과를 얻지만, ±45도의 기저로 측정하면 출력에 얽힘 상태가 없으므로 정확한 결과를 얻을 수 있다. 따라서 Alice 와 Bob 이 통신할 때 Bob 이 Alice 와 같은 기저상태로 측정하면 정확한 결과를 얻게 된다.
또, 제어 비트와 무관하게 표적 비트가 무조건 바뀌는 게이트의 진리표는 다음과 같다.
둘 중 표적 비트가 무조건 바뀌는 게이트에 앞서 사용한, 제어와 표적이 모두 중첩 상태인 두 비트를 입력하자. 두 입력의 초기 상태는 다음과 같을 때,
이 상태를 표적 비트가 무조건 바뀌는 게이트에 통과시키면 아래와 같은 결과를 얻는다.
위 상태도 얽힘 상태가 아니므로 두 상태의 곱으로 정리할 수 있다.
표적 비트가 무조건 바뀌는 게이트는 정상적인 CNOT 게이트와 유사하지만 제어 출력의 중첩 상태는 |1> 앞에 다른 부호를 갖는다. 따라서 만일 이 출력을 위의 CNOT 게이트에 사용한 것과 같은 기저 상태로 측정한다면 "1" 보다는 "0"의 결과로 나올 것이다. 제어 비트가 전혀 작동하지 않는 게이트도 잘못된 부호를 가지는 유사한 결과를 나타낸다. 그러므로 각 게이트들을 중첩 상태로 입력하여 한 번씩만 테스트한다면 45도 기저 상태로 출력을 측정하여 정상적인 CNOT 게이트를 가려낼 수 있다.
도이치 알고리즘(Duetsch Algorithm)[3]은 상수 함수와 균형 함수를 단 한번의 시도로 구별하는 알고리즘이다. 이 알고리즘을 병렬로 동시에 처리할 수 있다고 하더라도 가능한 함수 값이 동시에 나오는 것은 아니다. 그럼에도 고전전인 논리와 달리 양자 논리를 사용하면 무언가 얻을 수 있는 희망이 보인다.
[1] Carry 출력을 포함해야 두 개의 출력이 된다.
[2] xyz → xy(XOR(z,AND(x,y))) 이며, 관찰해보면 앞의 두 비트가 1일때 마지막 비트가 바뀐다. 수식의 출처는 https://horizon.kias.re.kr/12926/ 이다.
[3] [2]번의 사이트가 가장 자세히 설명하는 듯 하다.
7.2. 기본 개념
6장에서 양자암호 통신 메시지의 양자 상태를 다루었다. Alice 와 Bob 이 선택한 편광 기저에 따라 측정한 광자들은 |0> 또는 |1> 의 상태이든지 아니면 중첩 상태인 (|0> + |1>)√2 가 된다. Bob 이 선택하는 측정 기저에 대해 Alice 의 광자가 중첩 상태에 있을 때에는 Bob의 측정 결과는 마구잡이 상태가 된다.논리회로에서 "0"과 "1"을 다루는 대신에 중첩 상태를 입력하는 것을 생각해보자. "0"과 "1"을 입력할 때 |1> 과 |0> 을 사용하며, 중첩 상태인 (|0> + |1>)√2 는 |1> 과 |0> 을 동시에 함께 처리해야 한다. 기존의 AND, OR, XOR 등의 게이트들은 비가역적(irreversible)이기 때문에 양자 상태와 공존하기 어렵다. 다시 말해, 논리 게이트들은 일방 통행되는 거리와 같다. 비가역적인 이유는 게이트의 입력은 2개이고, 출력은 1개라서, "0"과 "1"로 이루어진 가능한 4가지 조합의 입력들은 결국 2가지 출력으로 나온다. AND 게이트의 결과가 "0"이라면, 가능한 입력 조합은 "0"+"0", "0"+"1", "1"+"0" 이다. 따라서 출력 값을 통해 입력 값을 구할 수 없다. 그러나 양자 역학은 값을 측정하지 않는 한 정보를 잃지 않으므로, 양자 상태를 갖는 논리회로의 게이트는 반드시 가역적(reversible)이어야 한다.
7.3. 가역성
논리연산 수행 중에 정보가 없어졌다면 논리게이트를 실현하고 있는 물리적 계는 반드시 열이 발산된다. 정보의 손실과 열효과를 피하려면 통상의 게이트는 가역적이어야한다. 가역적인 논리게이트를 만들려면 입력과 출력의 수가 같아야 한다. 따라서 단일 입력의 경우에는 단일 출력의 NOT 게이트가 적합하다. 두 개의 입력을 받으면 두 개의 출력이 되어야 하므로 XOR 게이트[1]가 가능하다. 란다우(Landauer)는 고전적 계산에서 가장 유용한 게이트는 3개의 입력과 출력을 갖는 가역 게이트임을 발견했다. 이런 게이트 중 두 예는 프레드킨 게이트(Fredkin gate) 와 토폴리 게이트(Toffoli gate)가 보편적으로 알려져 있다. 한편 비가역적 계산에서 보편적이면서도 간단한 게이트는 NAND 게이트이다.7.4. CNOT 게이트
CNOT 게이트는 NOT 게이트의 일종이며, 연산이 이루어지는 동안 변하지 않는 입력 값에 의해 제어된다. 만일 제어 입력이 "1" 이라면 표적 입력은 "0"에서 "1"로 변하거나, "1"에서 "0"으로 변한다. 제어 비트를 x, 표적 비트를 y라고 하면, 제어 비트 x 는 값을 유지하며, 표적 비트는 x ⊕ y 로 나타난다. 이 게이트는 각각의 입력쌍에 대해서 출력쌍이 대응하므로 출력을 알면 입력도 알 수 있는 가역성이 있다. 이제 CNOT 게이트를 양자 상태에 대입하면서 늘 기억해야 하는 것은 얽힘과 복제 불가의 원리이다. 양자의 상태가 두 개이므로 복합(곱)상태로 다루며, 복합 상태 |0> 과 |1> 은 단순히 |01> 로 쓴다. 따라서 CNOT 게이트는 아래와 같이 작용한다.
|00> → |00>
|01> → |01>
|10> → |11>
|11> → |10>
이제, 중첩 상태를 제어 입력으로 사용하고 표적 상태가 |0> 이면 다음과 같다.
(|0> + |1>)|0>) / √2
위 식을 다시 아래와 같이 쓸 수 있다.
(|00> + |10>) / √2
즉 입력 상태는 |00> / √2 와 |10> / √2 의 중첩이라는 의미이다. 이 중첩 상태를 CNOT 에 입력해보자. 양자 상태들은 중첩이 가능하므로 CNOT 게이트의 출력도 두 개의 입력 상태의 중첩이 될 것이다. 그러므로 CNOT 진리표의 복합 입력 상태를 따라 |00 / √2 는 |00> / √2 으로, |10 / √2 은 |11 / √2 로 출력된다. 따라서 위 복합 상태의 CNOT 출력은 다음과 같다.
(|00> + |11>) / √2
위 식을 보면 2개의 단일 입자 양자 상태들의 곱으로 나타낼 수 없다는 것을 알 수 있다. 복합 입력 상태 (|00> + |10>) / √2 는 두 개의 단일 입자 상태의 곱 상태인 (|0> + |1>)|0>) / √2 와 같았지만, CNOT 의 출력 상태는 분리되지 않는다. 다시 말해, CNOT 의 입력이 충접 상태과 |0>의 상태에서 출력 상태는 얽힘 상태로 바뀌었다. 얽힘 상태의 양자들은 특이한 성질을 갖는다. 두 양자 비트 중의 하나를 측정하면 동시에 다른 입자의 양자 상태가 결정된다. 하지만 측정 전에는 어떤 양자 비트에 대해서도 정확한 상태를 알 수 없다.
CNOT 게이트의 출력 상태를 보면 복제 불가능의 원리가 깨어지는 것 같이 보일 수 있다. 그러나 CNOT 은 '미지(0과 1이 아닌 그 사이의 어떤 값)'인 중첩 상태를 제어 입력으로 하면 단순하게 출력이 얽힘 상태로 유도된 것 뿐이다.
7.5. 새로운 것을 찾아서
이어서 표적 입력에 중첩 상태 (|0> - |1>) / √2 를 입력해보자. 제어 입력때 선택했던 (|0> + |1>) / √2 와 부호만 다를 뿐이다. 양자 상태들은 상대적 위상에 따라 값이 달라지므로 이 마이너스 부호는 중요한 의미를 갖는다. 양자 논리회로에서 |0> 과 |1> 의 기저를 다음과 같은 중첩 상태로 변환시키는 것을 하다마드 게이트(Hadamard gate)라 하며, 다음의 진리표를 갖는다.
|0> → (|0> + |1>) / √2
|1> → (|0> - |1>) / √2
그리고 양자 논리회로에서 자주 사용되는 토폴리 게이트(Toffoli gate)[2]의 진리표는 다음과 같다.
|000> → |000>
|001> → |001>
|010> → |010>
|011> → |011>
|100> → |100>
|101> → |101>
|110> → |111>
|111> → |110>
다시 돌아가서, 제어 입력과 표적 입력이 모두 중첩 상태일 때, 두 상태를 곱하여 전개하면,
((|0> + |1>) / √2) * ((|0> - |1>) / √2)
상기 식이 되고, 정리하면 아래의 식이 된다.
(|00> - |01> + |10> - |11>) / 2
위 식에 CNOT 게이트를 적용하면 아래와 같다. 밑줄은 CNOT 게이트를 통해 상태가 변한 비트이다.
(|00> - |01> + |11> - |10>) / 2
위 상태는 얽힘 상태가 아니므로 두 상태의 곱으로 쓸 수 있다.
(|0> - |1>) * (|0> - |1>) * 1/2
제어 입력을 중첩 상태로, 표적 입력을 단순 기저 상태로 입력하면 얽힘 상태가 나오는데, 표적 입력에도 중첩 상태를 사용하면 간단한 출력 상태를 얻게 된다. 이 경우 두 개의 출력은 중첩 상태들의 곱으로 분리된다. 기저 상태 |0> 과 |1>을 사용하여 중첩 상태를 측정하면 마구잡이의 결과를 얻지만, ±45도의 기저로 측정하면 출력에 얽힘 상태가 없으므로 정확한 결과를 얻을 수 있다. 따라서 Alice 와 Bob 이 통신할 때 Bob 이 Alice 와 같은 기저상태로 측정하면 정확한 결과를 얻게 된다.
7.6. 마술 같은 테스트
양자 컴퓨터에서 CNOT 게이트 하나가 고장이 난 경우를 생각해보자. 새 CNOT 게이트를 사려고 하는데 제어 비트가 전혀 동작하지 않는 게이트와 제어 비트와 무관하게 표적 비트를 바꾸는 게이트들 사이에 정상 CNOT 게이트가 섞여 있다고 하자. 이 경우, 제어 비트가 전혀 동작하지 않는 게이트의 진리표는 다음과 같다.
|00> → |00>
|01> → |01>
|10> → |11> 고장
|11> → |10> 고장
또, 제어 비트와 무관하게 표적 비트가 무조건 바뀌는 게이트의 진리표는 다음과 같다.
|00> → |01> 고장
|01> → |00> 고장
|10> → |11>
|11> → |10>
둘 중 표적 비트가 무조건 바뀌는 게이트에 앞서 사용한, 제어와 표적이 모두 중첩 상태인 두 비트를 입력하자. 두 입력의 초기 상태는 다음과 같을 때,
(|00> - |01> + |10> - |11>) / 2
이 상태를 표적 비트가 무조건 바뀌는 게이트에 통과시키면 아래와 같은 결과를 얻는다.
(|01> - |00> + |11> - |10>) / 2
위 상태도 얽힘 상태가 아니므로 두 상태의 곱으로 정리할 수 있다.
(|0> + |1>) * (|0> - |1>) * - 1/2
초기 상태를 정상적인 CNOT 게이트에 통과시키면 아래와 같은 결과를 얻는다.
(|00> - |01> + |11> - |10>) / 2
두 상태의 곱으로 정리하면 다음과 같다.
(|0> - |1>) * (|0> - |1>) * 1/2
7.7. 균형과 불균형
수학에서 입력 값과 출력 값의 경우의 수가 같은 함수는 균형 함수(balanced function), 입력 값과 관계 없이 동일한 출력 값을 같은 경우를 상수 함수(constant function)라고 한다. 예를 들어 f(0) = 0; f(1) = 1 인 함수는 균형 함수이고, f(0) = 0; f(1) = 0 인 함수는 상수 함수이다. 위에서 언급한 제어 비트가 전혀 동작하지 않는 게이트와 제어 비트와 무관하게 표적 비트를 바꾸는 게이트들은 상수 함수에 해당한다.도이치 알고리즘(Duetsch Algorithm)[3]은 상수 함수와 균형 함수를 단 한번의 시도로 구별하는 알고리즘이다. 이 알고리즘을 병렬로 동시에 처리할 수 있다고 하더라도 가능한 함수 값이 동시에 나오는 것은 아니다. 그럼에도 고전전인 논리와 달리 양자 논리를 사용하면 무언가 얻을 수 있는 희망이 보인다.
7.8. 한 단계 더 가까이
양자 컴퓨터는 고전 컴퓨터와 달리 입력과 출력 비트가 큐비트이다. 입력은 중첩 상태이며, 출력은 중첩 또는 얽힘 상태이다. 또한 모든 게이트들이 가역적이므로 컴퓨터의 연산 전체가 완전히 가역적이다. 마지막으로, 고전 컴퓨터는 일반적으로 출력 값에서 입력 값을 구할 수 없지만, 양자 컴퓨터는 완전히 가역적이므로 출력 값에서 입력 값을 구할 수 있다. 도이치 알고리즘은 원리적으로 양자컴퓨터 작업이 어떻게 이루어지는가를 보여주지만 실제로 활용하기는 어렵다. 다음 장에서 많은 사람들의 관심을 받은 알고리즘 두 개를 고찰해본다.[1] Carry 출력을 포함해야 두 개의 출력이 된다.
[2] xyz → xy(XOR(z,AND(x,y))) 이며, 관찰해보면 앞의 두 비트가 1일때 마지막 비트가 바뀐다. 수식의 출처는 https://horizon.kias.re.kr/12926/ 이다.
[3] [2]번의 사이트가 가장 자세히 설명하는 듯 하다.
댓글 없음:
댓글 쓰기