양자 컴퓨터(Quantum computer)

양자 컴퓨터(Quantum computer)

양자 컴퓨팅은 중첩, 얽힘 등의 양자 기계 현상을 이용하여 연산을 수행하는 것이다. 양자 계산을 수행하는 컴퓨터를 양자 컴퓨터라고 한다. 양자 컴퓨터는 정수 인자화(RSA 암호화의 기초가 되는)와 같은 특정 계산 문제를 클래식 컴퓨터보다 상당히 빠르게 해결할 수 있는 것으로 생각된다. 양자 컴퓨팅 연구는 양자 정보 과학의 하위 분야다.

양자 컴퓨팅은 물리학자 폴 베니오프가 튜링 머신의 양자 기계 모델을 제안하면서 1980년대 초에 시작되었다. 리처드 파인만과 유리 마닌은 나중에 양자 컴퓨터가 고전 컴퓨터가 할 수 없는 것들을 시뮬레이션 할 수 있는 잠재력을 가지고 있다고 제안했다. 1994년 Peter Shor는 RSA 암호화된 통신을 해독할 수 있는 잠재력이 있는 정수를 인수하기 위한 양자 알고리즘을 개발했다. 1990년대 후반 이후 지속적인 실험 진행에도 불구하고, 대부분의 연구자들은 "결함-내성 양자 컴퓨팅은 여전히 다소 먼 꿈"이라고 믿는다. 최근 들어 공공 부문과 민간 부문 모두 양자 컴퓨팅 연구에 대한 투자가 증가하고 있다. 2019년 10월 23일 구글 AI가 미국 항공우주국(NASA)과 손잡고 양자 패권을 달성했다고 주장하는 논문을 발표했다. 일부에서는 이 주장에 대해 이의를 제기했지만, 양자 컴퓨팅의 역사에서는 여전히 중대한 이정표다.

양자 컴퓨팅에는 양자 회로 모델, 양자 튜링 머신, 단방향 양자 컴퓨터, 다양한 양자 세포 자동화를 포함한 여러 가지 모델이 있다. 가장 널리 사용되는 모델은 양자 회로다. 양자회로는 고전적 연산의 비트(bit)와 다소 유사한 양자 비트(qubit)를 기반으로 한다. 쿼빗은 1 또는 0 양자 상태일 수도 있고, 1과 0 상태의 중첩 상태에 있을 수도 있다. 그러나 퀀트를 측정할 때 결과는 항상 0 또는 1이다. 이 두 결과의 확률은 측정 직전에 있었던 양자 상태에 따라 달라진다. 계산은 고전적 논리 게이트와 다소 유사하게 양자 논리 게이트로 퀘비트를 조작하여 수행된다.

현재 양자 컴퓨터를 물리적으로 구현하는 데는 아날로그와 디지털의 두 가지 주요 접근법이 있다. 아날로그 접근법은 양자 시뮬레이션, 양자 어닐링, 아디아바틱 양자 계산으로 더 크게 나뉜다. 디지털 양자 컴퓨터는 계산을 하기 위해 양자 논리 관문을 사용한다. 두 접근법 모두 양자 비트나 퀀텀 비트를 사용한다. 유용한 양자 컴퓨터 구성에는 현재 여러 가지 중요한 장애물이 있다. 특히 쿼빗의 양자 상태는 양자 해독에 취약해 유지하기가 어렵고, 양자 컴퓨터는 고전 컴퓨터보다 오류 발생이 훨씬 많아 상당한 오류 교정이 필요하다.

고전적인 컴퓨터로 해결할 수 있는 어떤 계산 문제도 원칙적으로 양자컴퓨터로 해결할 수 있다. 반대로 양자 컴퓨터는 Church-Turing 논문에 복종한다. 즉, 양자 컴퓨터가 해결할 수 있는 모든 계산 문제 역시 고전 컴퓨터로 해결할 수 있다. 이것은 양자 컴퓨터가 계산가능성의 측면에서 고전적인 컴퓨터에 대한 추가적인 힘을 제공하지 않는다는 것을 의미하지만, 이론적으로는 특정한 문제를 해결하는 시간의 복잡성에 관한 한 추가적인 힘을 제공한다. 특히 양자 컴퓨터는 어떤 클래식 컴퓨터도 실현 가능한 시간 안에 해결할 수 없는 특정한 문제를 신속하게 해결할 수 있다고 믿어진다. 양자 컴퓨터에 관한 문제의 계산적 복잡성에 대한 연구는 양자 복잡성 이론으로 알려져 있다.

암호학 : 양자암호법

공개키 암호 시스템의 보안을 뒷받침하는 정수 인자화는 소수 소수(예: 300자리 프리임 2개 제품)의 산물이라면 큰 정수에 대해서는 일반 컴퓨터로는 계산적으로 불가능하다고 생각된다. 그에 비해 양자 컴퓨터는 쇼르의 알고리즘을 사용하여 자신의 요인을 찾아 효율적으로 이 문제를 해결할 수 있었다. 이 능력은 양자 컴퓨터가 문제를 해결하기 위한 다항식 시간(정수의 자릿수) 알고리즘이 존재한다는 점에서 오늘날 사용되고 있는 많은 암호 시스템을 깨뜨릴 수 있게 해줄 것이다. 특히, 인기 있는 공개키 암호의 대부분은 정수의 인수 난이나 이산 로그 문제에 기초하고 있는데, 이 두 가지 모두 쇼르의 알고리즘으로 해결할 수 있다. 특히 RSA, Diffie-헬만, 그리고 타원곡선 디피-헬만 알고리즘이 깨질 수도 있어 이것들은 안전한 웹 페이지, 암호화된 이메일, 그리고 많은 다른 종류의 데이터를 보호하는 데 사용된다. 이를 어기는 것은 전자적 프라이버시와 보안에 중대한 영향을 미칠 것이다.

그러나 다른 암호 알고리즘은 그러한 알고리즘에 의해 깨지는 것으로 보이지 않는다. 일부 공개키 알고리즘은 코딩 이론의 문제에 기초한 McElice 암호 체계처럼 쇼어의 알고리즘이 적용되는 정수 인자화 및 이산 로그 문제 이외의 문제에 기초한다. 격자 기반 암호체계 역시 양자 컴퓨터에 의해 깨지는 것으로 알려져 있지 않으며, 격자 기반 암호체계를 많이 깨뜨릴 수 있는 이두하 숨겨진 부분군 문제를 해결하기 위한 다항식 시간 알고리즘을 찾는 것은 잘 연구된 개방문제다. Grover의 알고리즘을 적용하여 브루트 힘에 의한 대칭(비밀키) 알고리즘을 깨는 데는 대략 기본 암호 알고리즘의 호출과 동일한 시간이 필요하다는 것이 입증되었는데, 대칭 키 길이가 효과적으로 반감됨을 의미한다. 

양자암호법은 잠재적으로 공개키암호법의 일부 기능을 충족시킬 수 있다. 따라서 양자 기반 암호 시스템은 양자 해킹에 대한 기존 시스템보다 더 안전할 수 있다.