그림으로 배우는 양자 컴퓨터(3)

 '그림으로 배우는 양자 컴퓨터' 세 번째 시간입니다. 양자 컴퓨터 쪽 분야를 연구하는 것을 목표로 공부하고 있지만, 이론을 배우면 배울수록 내가 컴퓨터를 공부하는 건지 물리학을 공부하는 건지 구분하기 너무 어렵습니다 ㅎㅎ.. 한계가 느껴지기 전까지 최선을 다해 공부해며 도전해보려고 합니다.

그림으로 배우는 양자 컴퓨터

 그래서, 오늘 리뷰할 단원은 3단원 '원리로부터 풀어내는 양자 컴퓨터'와 4단원 '양자 알고리즘의 작동 방식을 알아봅시다'입니다. 3단원에서는 양자 컴퓨터의 구조와 연산 원리를 다루고 있습니다. 양자 컴퓨터의 구조를 알려면 기존 컴퓨터의 구조를 먼저 알아야 합니다. 기존 컴퓨터는 크게 CPU(제어장치 + 연산장치)와 입력장치(ex) 키보드, 마우스), 기억장치(ex), 메모리, 하드디스크), 그리고 출력장치(ex) 모니터, 스피커)로 구성되어있습니다. 

 

컴퓨터의 5대 기능(출처: 그림으로 배우는 양자 컴퓨터)

 그럼 양자 컴퓨터는 어떤 구조로 되어있을까요? 양자 컴퓨터는 '빠른 계산 속도'를 목표로 하는 만큼 '연산장치'를 중심으로 연구되고 있습니다. 이는 양자 컴퓨터의 연산에 필요한 '양자 상태'를 유지하는 기술이 아직 연구 중에 있기 때문인데요, 양자 상태를 유지하는 시간, '코히어런스 시간'을 유지할 수 있는 시간이 현재 100 마이크로초에서 1밀리 초 사이로 아주 짧은 시간이기 때문이라고 합니다. 때문에 양자 상태를 유지하는 양자 메모리를 제작하기에는 아직 연구가 부족하여 현재의 양자 컴퓨터는 연산장치로만 구성되며, 입력장치와 기억장치는 기존 컴퓨터의 장비를 사용합니다.

 

 양자 컴퓨터는 앞에 나온 양자 상태의 양자 비트를 이용하여 연산을 수행합니다. 양자 비트는 0부터 1사이의 방향을 나타내는 '상태 벡터'라는 벡터로 표현됩니다. 양자 비트는 0과 1의 확률로 나타나고, 양자 상태의 관찰 확률의 합은 항상 1이 됩니다. 양자 상태의 관찰 확률을 나타낼 때는 '브라켓 표기법'을 사용합니다. 이전에 '블로흐 구'를 다루면서 나왔던 |0>과 |1>이 브라켓 표시법의 예시인데요, 관측 결과가 100% 확률로 '0'이 됨을 나타낼 때 |0>, 100% 확률로 '1'이 됨을 나타낼 때 |1>로 나타냅니다. 양자 컴퓨터의 연산은 양자 비트를 |0>으로 초기화한 뒤 블로흐 구의 x축, y축, z축, y=x 그래프 등을 기준으로 회전하며 0과 1의 확률을 변화시키며 연산합니다. 예를 들어 |0> 상태의 양자 비트가 x축을 기준으로 180도 회전한다면 |1>인 상태로 변하는 것을 확인할 수 있습니다.

 

양자 비트의 X축 회전(출처: 그림으로 읽는 양자 컴퓨터)

 

 4단원은 양자 알고리즘에 대해 다루고 있습니다. 양자 알고리즘은 기존 컴퓨터의 알고리즘과는 방식이 많이 다릅니다. 양자 컴퓨터의 목적 자체가 기존 컴퓨터에서 계산이 오래걸리는 문제를 빠르게 해결하는 것이기 때문입니다. 이러한 성질을 양자 컴퓨터의 '고속성'이라고 합니다. 또한, 기존 컴퓨터에서 가능한 연산을 빨리 해결하기 위해 양자 컴퓨터를 사용하므로 양자 컴퓨터로 계산할 수 있는 연산은 기존 컴퓨터에서도 사용 가능합니다. 이런 성질을 '범용성'이라고 합니다. 두 가지 성질을 종합해보면 기존 컴퓨터에서 사용 가능한 알고리즘을 양자 컴퓨터에서 그대로 사용한다면 양자 컴퓨터를 사용하는 의미가 없습니다. 고속 연산을 위한 양자 컴퓨터만의 특별한 알고리즘이 필요합니다.

 

 양자 컴퓨터는 데이터를 부풀려서 연산하는 특징을 갖고있습니다. 이러한 양자 컴퓨터의 특징과 가장 맞는 알고리즘이 탐색 알고리즘과 암호 알고리즘, 조합 알고리즘과 같은 알고리즘입니다. 현재 양자 알고리즘은 크게 '만능형'과 'NISQ형'으로 구분됩니다. NISQ는 'Noisy Intermediate-Scale Quantum Computer'의 약자로 연산 과정에서 발생하는 다양한 노이즈를 제거하지 못한 양자 컴퓨터를 의미합니다. 현재 모든 양자 컴퓨터가 노이즈(오류)를 해결하지 못하는 NISQ형 양자 컴퓨터이고, 이와 반대로 오류 정정 기능을 가진 완성형 양자 컴퓨터가 '만능형'입니다. 즉, 지금 개발되고 있는 양자 알고리즘의 대부분은 오류를 고려해도 답을 도출할 수 있을 정도의 사용하기 쉬운 알고리즘이 주류입니다.

 

 양자 알고리즘은 계산 방식에 따라 '위상 추정형'과 '그로버형'으로 분류됩니다. 소인수분해를 하는 대표적인 양자 알고리즘인 쇼어 알고리즘이 위상 추정형에 속하며, 목표 달성을 위한 최솟값을 구하는데 목표를 두고 있습니다. 반대로 그로버형은 데이터를 정리하는 알고리즘처럼 계산을 반복하여 기존 컴퓨터보다 고속으로 결과를 냅니다.

 

 쇼어 알고리즘은 등차수열의 푸리에 변환을 이용하여 고속으로 소인수분해를 수행하는 알고리즘입니다. 소인수분해의 '주기성'을 바탕으로 해를 구하는 방식으로 N비트로 나타내지는 2^N개의 숫자에 대해 소인수분해를 수행하려면 고전 컴퓨터는 2^N 대가 필요하지만, 양자 컴퓨터는 단일 컴퓨터로 연산이 가능합니다.

 

쇼어 알고리즘(출처: 그림으로 배우는 양자 컴퓨터)

 

 쇼어 알고리즘을 사용하면 기존 컴퓨터보다 적은 비용으로 소인수분해가 가능하다는 것인데, 문제는 현재 인터넷 인증에 사용되고 있는 공개키 암호 방식인 RSA 암호는 거대한 두 소수의 곱을 이용하여 암호를 제작한다는 점입니다. 이후 정밀화된 양자 컴퓨터가 개발된다면 쇼어 알고리즘으로 인한 RSA 암호의 붕괴를 걱정하지 않을 수 없습니다. 양자 컴퓨터로 인해 기존의 암호화 방식이 붕괴된다면 양자 컴퓨터를 기반으로 한 새로운 암호화 방식이 필요함을 알 수 있습니다. 때문에 등장한 개념이 '양자 암호 기술'입니다. 양자 정보가 관측하면 붕괴되는 특징을 이용하는 방식으로 연구 중인 기술인데요, 양자 암호 기술을 포함하여 양자 컴퓨터를 이용한 다양한 기술을 다음 시간에 5단원 '양자 컴퓨터로 할 수 있는 일'을 리뷰하며 다루어보고자 합니다.

 

 부족한 글을 읽어주셔서 감사합니다.

 

 

 

참고

미나토 유이치로, 그림으로 배우는 양자 컴퓨터(영진 닷컴)

김태현, 양자컴퓨터의 소개 및 전망(전자공학회지)

김재완, 양자 암호(Quantum cryptography)(정보보호학회지)

이순칠, 공개키 암호 체계와 Shor 알고리듬(정보보호학회지)

손수덕 외 3명, 양자비트와 양자기반 탐색 알고리즘의 연산자(한국공간구조학회지)