보안정보

전문화된 보안 관련 자료, 보안 트렌드를 엿볼 수 있는
차세대 통합보안관리 기업 이글루코퍼레이션 보안정보입니다.

양자컴퓨터와 양자알고리즘

2020.03.31

34,389


 

 

 

 

 

01. 개요

 

2019년 10월, 영국의 과학 학술지 ‘네이처’에는 암호학계에 큰 파장을 일으킬 논문하나가 발표되었다. 구글에서 발표한 ‘Quantum supremacy using a programmable superconducting processor’로 주요 골자는 현존하는 가장 강력한 슈퍼컴퓨터에서도 약 1만년이 소요되는 연산을 단 200초만에 처리할 수 있는 양자컴퓨터 기술을 구현했다는 내용이다.

 

기존 암호체계는 알고리즘 기반의 대칭키와 비대칭키를 주로 사용하고 있으나 키관리 및 보안수준, 연산속도 등의 문제가 발생되어 이를 해결하고자 블록체인기술을 통한 암화체계 구축을 수행해왔다. 하지만 양자컴퓨터가 현존하는 가장 강력한 슈퍼컴퓨터를 능가하는 지점인 ‘양자 우월성(Quantum supremacy)’에 도달하였다는 것은 암호학계에 실로 놀라운 발표라고 볼 수 있다. 

 

양자컴퓨터 기술의 발전은 분산 및 합의알고리즘 기반의 블록체인기술이 적용된 암호화폐시장의  가격폭락이라는 영향을 주기도 하였다. 이처럼 물리학의 발전은 양자역학기술을 과학수준에서 공학수준으로 탈바꿈 하게 함으로써 새로운 변환점으로 작용하고 있다. 

 

머신러닝이나 인공지능이 4차 산업혁명의 주요 기술요소로 자리잡은것과 같이 양자컴퓨터도 하드웨어의 새로운 주요기술요소로 자리잡힐 것으로 예측하고 있다. 특히 양자 기계는 기존의 CPU, GPU, TPU 등 하드웨어 컴퓨팅 기술을 능가하는 성능을 이용하여 머신러닝이나 인공지능의 데이터 분석능력을 향상시켜 빠른 데이터 처리를 통한 정보의 통찰력(Insight)을 찾아낼 수 있을 것이다.

 

양자컴퓨팅의 실용화는 현 보안체계에서 발생되는 문제점을 보완할 수 있는 대체수단으로 제시될 수 있기 때문에 ‘양자정보과학기술’의 범주에 속해있는 ‘양자컴퓨팅’과 ‘양자암호통신‘, ‘양자센서‘등의 개념과 기술요소들에 대해서 살펴봐야 하는 시기라고 볼 수 있다. 따라서 이번 호에서는 양자정보과학기술 중에서도 핵심요소라고 볼 수 있는 ‘양자컴퓨터‘와 ‘양자알고리즘’을 사용하는 ‘양자컴퓨팅’에 대해서 살펴보고자 한다.

 

02. 양자컴퓨터와 양자알고리즘을 이용한 양자컴퓨팅

 

양자컴퓨팅, 양자통신, 양자센서 등의 기술은 정보과학이 물리학의 양자효과에 의존한다는 아이디어에 기초한 연구분야를 의미하는 ‘양자 정보 과학(QIS, Quantum Information Science)’의 응용분야로 일반적으로 양자컴퓨팅에 한정되어 있다.

 

 

[그림 1] 양자기술 구조도 / 출처: KISTEP 기술동향브리프 19호

 

‘양자정보과학기술’의 응용분야는 크게 양자컴퓨팅, 양자통신과 양자센서 등으로 구분될 수 있다. 양자정보통신(양자통신)은 국내에서만 사용되는 용어로 미국에서는 양자정보과학(Quantum Information Science), 유럽은 양자기술(Quantum Technology) 등 양자정보통신을 지칭하는 용어가 국가별로 상이하거나, 공통적으로 양자통신, 양자컴퓨팅, 양자센서 등을 포함하고 있다.

 

국내에서는 ‘양자정보과학기술’을 △ 양자컴퓨터와 양자알고리즘을 통해 데이터를 처리하는 모든 행위를 의미하는 양자컴퓨팅(양자 시뮬레이션, 물리양자비트, 논리양자비트, 양자소프트웨어 등 4가지 분류), △ 0과 1이 중첩되어 있는 양자상태를 송신부에서 수신부로 전송하는 모든 기술을 의미하는 양자통신(양자암호, 양자전송, 양자네트워크 등의 3가지 분류), △ 고전적인 측정 한계를 극복한 고정밀 데이터를 제공하는 기술을 의미하는 양자센서(양자측정, 양자센싱, 양자 이미징 등 3가지 분류)로 분류하고 있다.

 

양자컴퓨팅의 능력을 이해하려면 베이스가 되는 ‘양자역학(Quantum mechanics)’의 원리에 대해 알아야 한다. ‘양자(Quantum)’란 상호작용과 관련된 모든 물리적 독립체의 최소단위로 복사 에너지에서 처음 발견하였다. 양자역학은 이러한 양자 현상을 연구하는 물리학의 분야로 아무리 기이하고 터무니 없는 사건이라 해도 발생 확률이 0이 아닌 이상 반드시 일어난다는 물리학적 아이디어에 기초한다. 

 

양자와 양자역학의 기본 정의를 이용하여, 양자 중첩, 얽힘 등의 현상을 이용하여 특정 연산에 최적화된 초고속 대용량 컴퓨터가 양자컴퓨터이며, 양자컴퓨터에서 사용할 수 있는 알고리즘을 양자알고리즘이라고 부른다. 양자알고리즘에는 △ 소인수분해를 푸는 Shor 알고리즘, △ 검색속도 향상을 위한 Grover 알고리즘, △Bernstein–Vazirani 알고리즘, △Deutsch–Jozsa 알고리즘, △shift 알고리즘 등이 있다.

 


[표 1] 양자컴퓨팅의 정의 및 관련기술

 

03. 양자컴퓨팅의 핵심요소 - (1) 양자컴퓨터

 

양자컴퓨팅의 핵심요소 중 하나인 양자컴퓨터는 다수의 정보를 동시에 초고속으로 처리할 수 있는 새로운 개념의 컴퓨터를 의미한다. 양자컴퓨터를 구성하는 특징은 양자 역학 고유의 중첩, 얽힘 등이 있다. 양자 역학의 요소는 중첩, 얽힘 뿐만 아니라 측정에서의 양자 상태의 붕괴, 불확정성, 얽힘에 의한 비국소성, 비분리성 등이 있으며, 이번 호에서는 양자컴퓨터와 가장 밀접한 요소인 중첩과 얽힘, 그리고 불확정성에 대해 서술하고자 한다.

 

중첩이란 두 개의 성질을 동시에 갖는 특징을 가지고 있어, 0 이면서 동시에 1인 상태를 말하며, 얽힘이란 두 개의 양자를 특별한 처리를 통해 만든 상태로, 얽힘 상태일 경우 한쪽의 동작이 변화하면 연결된 다른 쪽도 변화한다는 원리이다. 

 

양자역학의 불확정성 원리는 서로 다른 특징을 갖는 상태의 중첩에 의해 측정값이 확률적으로 주어지게 되는 것을 응용하여 이른바 ‘큐비트(Qubit)’라 불리는 양자비트 하나로 0과 1의 두 상태를 동시에 표시할 수 있다. 따라서 데이터를 병렬적으로 동시에 처리할 수도 있고 또한 큐비트의 수가 늘어날수록 처리 가능한 정보량도 기하급수적으로 늘어나게 된다.

 

이와 같이 양자컴퓨터는 동시에 여러 개의 상태에 있을 수 있고, 동시에 모든 상태에 작용할 수 있기 때문에 디지털 컴퓨터와는 달리 1개의 처리 장치로 동시에 수많은 계산을 할 수 있다.

 

 

[표 2] 양자컴퓨팅의 특징

 




[그림 2] 일반 컴퓨터와 양자컴퓨터의 기본 단위

 

n개의 큐비트라면 2의 n 제곱만큼 중첩시키는 것이 가능하다. 이런 식으로 연산을 할 경우 이진법에 비해 빠른 속도로 연산이 가능하므로 큐비트를 사용하는 양자컴퓨터가 주목을 받고 있는 것이다. 

 

 

[그림 3] 기존컴퓨터와 양자컴퓨터 단위 비교 / 출처: KISTEP 기술동향브리프 19호(일부발췌)

 

04. 양자컴퓨팅의 핵심요소 - (2) 양자알고리즘

 


  

[표 3] Shor 양자 알고리즘과 Grover 양자 알고리즘의 특징과 사례

 

1) Shor 알고리즘 

 

 

[그림 4] Shor 양자 알고리즘

 

 

2) Grover 알고리즘

 

Grover의 알고리즘은 목록의 항목이 검색 중인 항목인지 여부를 묻는다. 이를 위해 각 계수 또는 확률 진폭을 사용하여 목록의 인덱스에 대한 양자 중첩을 생성하여 특정 인덱스가 찾고 있는 인덱스일 확률을 나타낸다. 알고리즘의 핵심에는 해당 계수의 확률 진폭이 1에 도달할 때까지 찾고 있는 인덱스의 계수를 점진적으로 증가시키는 두 단계가 있다.

 

다음의 알고리즘은 특정 표시된 상태를 찾기 위해 실행 가능한 모든 입력을 검색하기 위한 Grover 알고리즘을 적용한다.

 


[그림 5] Grover 양자 알고리즘(1) / 출처 : Microsoft

 


 

 

[그림 6] Grover 양자 알고리즘(2) / 출처 : Microsoft

 


 

 


[그림 7] Grover 양자 알고리즘(3) / 출처 : Microsoft

 


[그림 8] Grover 양자 알고리즘 실행 결과

 

 

 

 

[그림 9] Grover 알고리즘의 구성도 / 출처 : 도리의 디지털라이프

 

05. 결론

 

앞에서 확인한 바와 같이 MIT연구원들은 양자 알고리즘을 활용한 양자 컴퓨터가 다양한 암호화 알고리즘을 깰 수 있다는 것을 보여주었다. 이로 인해 양자컴퓨터 기술의 발전이 비트코인 등 블록체인 기술에 큰 위협이 될  수 있다는 전망이 제기되고 있다. 양자컴퓨터가 실현 된다면 암호화폐를 보호하는 키 보안과 블록체인 합의 알고리즘에 위협이 될 수 있기 때문이다. 

 

블록체인뿐만 아니라 금융 시스템의 기존 암호화 보안 체계도 흔들릴 수 있다는 우려도 있다. 하지만 현재 개발된 양자컴퓨터의 구조는 단기간 블록체인의 암호화 키를 해독하는 것과 같이 매우 복잡한 기능을 수행하기에는 역부족이라고 판단하고 있다. 

 

양자컴퓨터의 상용화를 위한 국내외의 연구는 끊임없이 진행되고 있다. D-Wave 시스템은 양자 컴퓨팅을 주력사업 대상으로 하는 캐나다의 하드웨어 기업으로, D-Wave One을 최초 16큐비트 양자 프로세서를 프로토타입으로 개발하여 상용화하였으며, 2017년 2000 큐비트 모델을 출시하였다. 최근 차세대 5000큐비트 양자컴퓨터 개발에 주력하고 있으며, 구글, IBM, 인텔(Intel) 및 리게티 컴퓨팅(Rigetti Computing) 연구원들은 컴퓨팅 문제를 해결할 수 있는 범용 양자 컴퓨터를 만드는 데 힘쓰고 있다.

 

또한, 유럽은 양자 역학이 태동한 곳으로 양자 정보 전송과 양자 컴퓨터 연구가 활발히 진행되고 있으며, 미국은 IBM, HP, Bell 연구소 등에서 연구가 진행 중이다. 일본은 초전도 소자 큐비트 연구에서 가장 앞서 의미 있는 결과를 발표하고 있다. 중국은 상대적으로 양자시스템 연구의 후발주자이지만 2005년 양자암호 시스템 개발에 주력 하고 있으며 복수 지점 간 암호키 분배를 시험하고 있다.

 


[그림 10] 미국, 일본, 호주의 양자정보관련 연구비 증액 현황 / 출처 : 고려대학교 양자통신의 개요 및 전망

 

 

[표 4] 양자컴퓨팅 기술개발사업 주요 내용 / 출처 : 과학기술정보통신부(2019)

 

국내에서는 2013년부터 양자컴퓨팅 기술개발을 진행하였으나 이후 기술개발의 전략을 양자암호 통신에 집중하였다. 2019년 1월 과기부는 “양자컴퓨팅 기술개발사업 추진계획”을 마련하고 5년간 총 445억 원의 투자계획을 발표하였다.

 

국내외에서 양자컴퓨터의 상용화와 개발로 인해 양자컴퓨팅에 대한 기업의 관심이 증가 하고 있다. 현시점에서 국내외의 기업은 양자 컴퓨팅에 대한 현재 암호화 방식의 취약점 대비를 위해, 리스크를 이해하고 양자 암호화 성숙 모델을 구축하며, 조직의 암호화 민첩성 수준의 중요성을 이해하고 핵심 대응 방안을 수립하기 위한 전략과 솔루션에 관심을 가져야 한다.

 

06. 참고자료

 

[1] 양자컴퓨터 구조 및 응용 - http://www.krnet.or.kr/board/data/dprogram/2350/C1-1_%C7%E3%C1%D8.pdf

[2] 양자컴퓨터의 원리, 개념, 발전방향 - https://m.blog.naver.com/PostView.nhn?blogId=hmin011&logNo=221001358881

[3] 양자암호통신, 앞으로의 미래는? - http://www.igloosec.co.kr/BLOG_%EC%96%91%EC%9E%90%EC%95%94%ED%98%

B8%ED%86%B5%EC%8B%A0,%20%EC%95%9E%EC%9C%BC%EB%A1%9C%EC%9D%98%20%EB%AF%B8%EB%9E%98%EB%8A%94[qs]?searchItem=&searchWord=&bbsCateId=17&gotoPage=3

[4] Shor’s factoring algorithm- https://leejaekyung.com/?p=1120

[5] 양자컴퓨터 관련 뉴스

  -  https://news.joins.com/article/22486587

  - https://www.epnc.co.kr/news/articleView.html?idxno=92783

  - http://it.chosun.com/site/data/html_dir/2018/05/10/2018051085067.html

  - https://www.mk.co.kr/news/business/view/2018/08/515351/

[6] 양자컴퓨터 개발 동향과 시사점- www.iitp.kr

[7] 범용양자컴퓨터- http://www.kistep.re.kr/

[8] 양자통신의 개요 및 전망