양자컴퓨터는 양자 얽힘(quantum entanglement) 및 중첩(superposition) 원리를 활용해 고전 컴퓨터에 비해 계산 속도를 크게 향상한다.

쇼어 알고리즘(Shor algorithm)은 잘 알려진 일반적인 사례로 확장된 양자 컴퓨터에서 기하급수적으로 속도를 높일 수 있다.

글로버 알고리즘(Grover algorithm)은 기존 지수 이하(sub-exponential) 속도 개선 알고리즘에 비해 다항 가속(polynomial speedup)으로 종종 인용되는 또 다른 예이다.

최근 로빈 코사리(Robin Kothari)가 이끄는 MS(Microsoft) 연구팀은 20년 동안 답을 찾아온 문제에서 성과를 거뒀다. 이 팀은 비구조화 문제(unstructured problems) 가운데 몇 가지 중요한 문제에 대해 가능한 최대 양자 속도 향상 문제를 재검토했다.

연구자들은 하오 황(Hao Huang)이 제시한 2019년 혁신적 연구의 함의를 조사한 결과, 악명 높은 감도 추측(sensitivity conjecture)로 불리는 불 함수(Boolean functions)를 해결, 구조화되지 않은 문제에 대해 가능한 최고의 양자 가속(quantum speedup)이 사차(quartic)임을 입증했다(T vs. T^4). 20년 넘게 해결되지 않았던 난제에 대한 해답이다.

즉, 고전 컴퓨터에서는 백만 단계가 걸리는 문제를 양자 컴퓨터는 1,000 단계에서 해결할 수 있다. 한편, 지수적 속도 향상은 양자 컴퓨터에서 ‘T’ 시간이 걸리지만 고전 컴퓨터는 2^T가 소요된다. 여기서 T가 100일대 100과 2^100의 차이다. 이러한 놀라운 속도 향상은 양자 컴퓨터의 가장 유망하고 매력적인 측면 중 하나다.

또한 이 팀은 동일한 입증 기술을 사용해 구조화되지 않은 대량의 데이터 세트를 분석하고 기본 연결 및 패턴을 찾는 그래프 문제에 대한 양자 가속에 대한 오래된 추측을 해결할 수 있음을 발견했다.

연구 결과는 논문(Quantum Implications of Huang’s Sensitivity Theorem)에서 자세히 설명했다.

그래프 문제 가속

모노톤 그래프 속성의 쿼리 복잡성은 1970 년대부터 연구됐다. 오늘날까지도 해결되지 않은 ‘Aanderaa–Karp–Rosenberg 추측‘은 고전적인 무작위 알고리즘이 모노톤 그래프 속성을 결정하기 위해 Ω (n2) 쿼리를 만들어야한다고 명시하고 있다.

1999년 버만과 연구자들은(Buhrman et al.) 모든 양자 알고리즘은 모노톤 그래프 속성을 결정하기 위해 Ω (√n) 쿼리를 해야한다는 것을 보여주었다.

코사리는 “추측한 답은 Ω (n)이었으며 글로버 알고리즘을 사용해 Ο(n) 양자 쿼리로 해결할 수 있는 그래프 속성이 있기 때문에 기대할 수 있는 최선의 방법”이라며 “동일한 증명 기술을 사용해 이 추측을 최적으로 해결한다. 고전적인 버전은 여전히 해결되지 않은 상태에서 추측의 양자 아날로그를 완전히 해결할 수 있기 때문에 이것은 놀라운 일”이라고 설명했다.

추측된 답은 글로버 알고리즘을 사용해 달성할 수 있는 최악의 경우 Ω(n)인 선형 시간 복잡성이다.

코사리 팀은 이같은 구조화되지 않은 문제에 대해 양자 컴퓨터가 제공하는 최대 속도 향상에 관한 오래된 문제에 최적의 해답을 블로그에서 공개했다.

쇼어/글로버 알고리즘

양자 컴퓨터가 주목받기 시작한 것은 1994년 벨연구소의 피터 쇼어(Peter W. Shor)가 ‘소인수 분해 알고리즘’을 발표하면서다. 강력한 암호 체계 중 하나인 ‘공개키’암호시스템은 곱셈보다 소인수분해가 훨씬 더 어렵다는 점을 이용한다. 300자리 정도의 수를 소인수분해하는 데 기존 컴퓨터는 우주 나이보다 긴 시간이 필요하다고 여겨진다.

절차도 절차 설명
① 인수분해 대상 N 보다
작은 m 선택하여,
m, N 최대공약수 계산
② m6 mod n 의 주기 P 계산
③ p가 홀수이면 ①로 이동
짝수이면 ④로 이동
④ (mp/2 – 1)(mp/2 + 1)
= m– 1 = 0 mod N
mp/2 + 1 = 0 mod N 시 ①로
⑤ mp/2 – 1와 N 최대공약수

*②가 양자 푸리에 변환 사용 단계로, 인수분해 문제가 고전 컴퓨터와 달리 폴리노미얼 타임으로 해결이 가능하다.

쇼어에 이어 같은 벨연구소의 로브 그로버(Lov Kumar Grover)도 독자적 양자 알고리즘을 개발했다. 그로버 양자 알고리즘은 효율적인 데이터 검색 알고리즘으로, 숫자를 하나씩 대입해가면서 답을 확인할 때 더 빠르게 답을 찾는 알고리즘이다.



① 하다마르드 게이트(Hadamard gate, H) 이용 시스템 동일 중첩 상태 만듦
② 양자 오라클(Quantum oracle)이라 불리는 부분 통과해 찾고자 하는 원소에 맞게 시스템 변화
③ 디퓨전 변환(diffusion transform)을 통해 위상이 평균보다 큰 경우 평균보다 낮게 변화, 평균보다 낮은 경우 크게 변화
④ 고전적 측정으로 결과 평가하여 O(1)의 확률로 옳은 값 출력

* 글로버 알고리즘은 정렬되지 않은 데이터베이스 원소를 찾는 양자 알고리즘이다. 고전 컴퓨터로 N개의 원소 중 하나 찾으려면 O(N) 검색 필요한 반면 글로버 알고리즘은 O(N1/2) 검색으로 원하는 요소를 찾을 수 있다.

글로버 알고리즘은 대칭키 암호, 쇼어 알고리즘은 공개키 암호에 큰 영향을 미친다. 글로버 알고리즘은 검색 속도를 향상시키기 때문에 대칭키의 경우는 키 길이 증가, 해시함수의 경우 출력 길이의 증가가 필요하다. 하지만 쇼어 알고리즘은 서브-지수적(sub-exponential time) 인수분해 문제를 다항적(polynomial time)으로 축소시키기 때문에 공개키 암호 시스템은 더 이상 안전하지 않다.

credit:도리의 디지털라이프

이에 충분히 빠른 연산으로 암호를 해독할 수 있는 양자 컴퓨터가 주목받기 시작했다. 더욱이 암호 문제는 금융 분야뿐만 아니라 국가보안과 관련해서도 문제가 될 수 있다. 각국이 경쟁적으로 양자컴퓨터 개발에 뛰어든 배경이다.

최초의 양자 머신은 미국 표준기술연구소(NIST)에서 1995년 ‘이온 트랩(ion trap)’을 이용한 장치다. 전기장을 이용해 이온을 여기하고 각 이온들의 스핀을 큐비트로 양자 게이트를 구현할 수 있음을 증명했다. 1998년에는 2큐비트의 핵자기공명 양자 머신으로 양자 알고리즘을 구현했다. 이 장치는 핵스핀을 큐비트로 이용해 결맞음 시간이 길었지만 일정 이상 큐비트를 구현하고 제어하기 힘들다는 단점이 있었다. 결맞음 시간은 계산에 필요한 큐비트의 1이나 0, 중첩이 유지되는 시간으로 양자 컴퓨터 구현에 있어서 중요한 요소다.