양자 컴퓨터 (3) - 양자 컴퓨팅 종류 : 범용 양자컴퓨터

* 본 포스팅은 서울대학교 김태현 교수님의 '양자 컴퓨팅과 양자 암호 기술의 현재와 미래' 강의를 참고하여 작성 되었습니다.

 

 지난 포스팅에서는 양자현상이란 무엇인지 그리고 양자의 중첩 원리에 대해 살펴보았다. 또한 양자 정보 기술은 크게 (1) 범용 양자 컴퓨터, (2) 양자 시뮬레이터, (3) 양자 암호, (4) 양자 센서로 구분될 수 있다고 했다. 이번 포스팅에서는 본격적으로 양자 컴퓨팅에 대해 이해해보자.

---

양자컴퓨팅의 분류

(1) 범용 양자 컴퓨터	회로 기반 양자컴퓨터 알고리즘 수행이 목적 복잡한 계산에 특화
(2) 양자 시뮬레이터	하드웨어는 범용 양자컴퓨터와 유사 양자 역학 물리 문제 해결이 목적
(3) 단열 양자컴퓨터	양자 얽힘(Entanglement)을 이용 머신 러닝 최적화 문제에 사용

 양자컴퓨팅은 크게 (1) 범용 양자컴퓨터, (2) 양자 시뮬레이터, (3) 단열 양자컴퓨터로 분류할 수 있다.

 

 범용 양자컴퓨터는 회로 기반 양자컴퓨터라고도 불리며, 일반적인 알고리즘을 수행하는 데에 그 사용 목적이 있다. 복잡한 계산에 특화되어 있는 양자컴퓨터이다.

 

 양자 시뮬레이터는 하드웨어는 범용 양자컴퓨터와 비슷하다. 하지만 일반 계산 문제가 아니라, 양자 역학 물리 문제를 해결하기 위한 것이다. 실제 양자 역학에 사용되는 시뮬레이터라고 생각하면 된다.

 

 단열 양자컴퓨터는 양자의 성질 중 양자 얽힘을 이용한 양자컴퓨터라고 한다. 머신 러닝 최적화 문제에 사용될 수 있다.

 (하드웨어적인 부분은 좀 더 조사가 필요하다…)

---

범용 양자컴퓨터

양자 병렬 처리란?

 범용 양자컴퓨팅에 대한 설명에 앞서 양자 병렬 처리에 대해 알아보자.

 

 양자 병렬 처리를 이해하기 위해 먼저 퀀텀 레지스터(Quantum Register)를 이해해야 한다.

 퀀텀 레지스터(Quantum Register). 우리가 일반적으로 아는 0과 1을 표현하기 위한 컴퓨터 속의 레지스터 같으면서도 이것과는 굉장히 다를 것 같은 느낌이다. 이전 포스팅에서 설명했던 Qubit 여러 개를 모아 레지스터를 만들 수 있는데, 이것이 Quantum Register이다.

 Qubit 하나는 양자 하나라고 생각하면 되고, 우리는 양자에는 중첩의 원리가 적용되는 것을 알고 있다. (혹시라도 까먹었다면 이전 포스팅 참고)

 그럼 예를 들어 2-qubit register의 경우 무엇이 가능할까? 00, 01, 10, 11 4개의 값을 동시에 저장할 수 있다! 2bit짜리 레지스터면 00 또는 10 또는 10 또는 11을 저장할 수 있어야 하는데 모든 값을 한번에 저장한다니. 왜그럴까?

 이유는 여러 값들이 중첩될 수 있기 때문이다! 이전 포스팅에서 설명한 것을 토대로 생각해보면 대충 이해는 간다. 양자 하나는 0과 1을 동시에 저장할 수 있으니까 모든 경우의 수를 커버할 수 있다.

 

 근데 대체 어떻게 한다는 말일까?

 

대각선편광은 가로편광과 세로편광의 합이다.

 2개의 대각선방향의 광자를 편광 큐브에 쏜다고 해보자. 대각선방향의 광자는 가로방향의 광자와 세로방향의 광자의 합이다. 따라서 각 대각선방향의 광자는 가로방향의 광자, 세로방향의 광자를 모두 가지고 있다. 이는 다시 말해 0과 1의 상태를 동시에 가지고 있다는 말이다.

 

 실제로 위 2개의 광자를 편광 큐브에 넣는다면, 00, 01, 10, 11 4가지 중 하나가 나올 수 있으며 이는 확률에 기반한다. 이러한 확률은 가로방향의 벡터와 세로방향의 벡터의 크기에 의해 결정될 수 있다.

 

이를 표현하면 굳이 수식으로 표현하면 |00>+|01>+|10>+|11>으로 표현할 수 있다.

 

병렬 처리에 대한 고찰

Computer 회로의 예시

 디지털 컴퓨터는 특정 회로의 출력을 알기 위해선 모든 경우의 수를 입력으로 넣어봐야 한다. 만약 입력이 2bit라면, 2^2=4개의 입력 조합을, 3bit라면 2^3=8개의 입력 조합을 직접 넣어봐야 한다. 이를 병렬처리 하기 위한 방법이 여러 가지가 있겠지만, 디지털 컴퓨터에 여러 CPU를 두거나 GPU를 이용하는 등 HW적으로 처리하는 방법이 대부분이며, 이 방법들은 물리적으로 공간을 많이 차지한다.

 

 양자컴퓨터는 한번의 입력에 모든 경우를 중첩할 수 있다. 위에서 언급한 2-qubit register처럼, 2개의 광자로 4가지의 상태를 중첩시킬 수 있고, 이를 양자 회로의 입력으로 사용하면, 나올 수 있는 모든 출력의 경우가 중첩되어 출력된다. 따라서 입력되는 bit수가 증가해도 단 한번의 입력만 하면 중첩된 출력으로 모든 출력의 경우를 알 수 있다.

 

 하지만! 여기서 측정의 문제가 발생한다. 앞서 설명한대로, 중첩된 결과를 통해 각 경우를 뽑아내려면 편광 큐브에 이를 통과시켜야 되는데, 적어도 4번의 측정이 필요하다. 여기서 '적어도'라는 것은 각 가장 happy한 상황이 4번 측정이고, 만약 측정 결과가 동일하다면 최악의 경우 무한대의 측정이 필요하다고도 할 수 있다. 이것이 양자컴퓨터의 측정의 한계이다.

 

그럼 대체 언제 도움이 되나?

 양자컴퓨터의 이러한 중첩의 성질은 패턴을 파악하고 싶을 때 매우 유용하게 사용된다. 출력의 각 경우를 뽑아내는 경우가 아닌, 중첩된 결과를 통해 어떤 패턴을 알고 싶을 때 활용이 가능하다.

 예를 들어, 위처럼 1개의 양자 회로가 아닌 양자 회로를 거친 출력을 다른 양자 회로의 입력으로 사용하는 경우, 어떤 패턴을 가지는지 확인할 수 있다.

 이러한 원리가 응용되는 분야에는 고전 암호 해독이나 머신 러닝을 포함한 최적화 문제 등이 있다.

 

 한번 실제 예시를 통해 알아보자.

 

[예시 1] 소인수분해

 

 고전 컴퓨터는 소인수분해 문제를 해결하기 위해서는 Looping을 해야만 한다. 다시 말해, 소인수분해를 하고자 하는 숫자가 1, 2, 3, 4, ... 와 같이 제수(divisor)를 쭉 증가시키면서 나눠 떨어지는지 확인한다는 것이다. 이는 굉장히 비효율적이다. 조금 효율적으로 계산하기 위해 이런저런 방법 (e.g. 2로 나누어 떨어지지 않으면 모든 짝수는 제외시킴 등)으로 개선은 할 수 있지만 본질적인 해결책은 아니다.

 

 그렇다면 양자 컴퓨터는 어떻게 할까?

1. 중첩된 입력으로 패턴을 쉽게 찾을 수 있음
2. 패턴의 주기를 찾기 위한 '양자 푸리에 변환'을 양자 컴퓨터에서 하면 굉장히 효율적임

 사실 위 계산 과정에 대해 100% 이해는 하지 않았지만 (1) 패턴을 쉽게 찾을 수 있다는 점과 (2) 양자 푸리에 변환에 양자컴퓨터를 이용하면 굉장히 효율적이라는 정도만 알아두자.

 

[예시 2] Search 알고리즘

 

 N개의 데이터가 있을 때, 고전 컴퓨터는 Search를 위한 횟수가 O(N)에 비례해서 증가한다. 하지만 양자 컴퓨터는 O(√N)에 비례해서 증가한다. 이는 어디서 활용할 수 있을까?

 Search 알고리즘에서 나타나는 이점은 Blockchain에 이용될 수 있다. Blockchain의 원리를 보면 데이터의 무결성을 판단하기 위해 앞 데이터를 참조하여 'nonce'라는 수를 생성한다. 이 때 nonce는 데이터를 Blockchain 기술에서 말하는 'Chaining' 작업을 할 때마다 생성되어야 한다. 앞서 search 알고리즘에서 살펴본 위 논리에 의해 생성해야할 nonce의 개수가 제곱근만큼 줄어드는 효과가 있다.

 

소인수분해와 Search 알고리즘 예시의 경우 아직 수학적으로 완벽하게 이해하지는 못했다. (죄송..) 하지만 양자컴퓨터의 중첩의 성질과 이를 통한 패턴 파악이 용이하다는 것이 각 예시에 사용된다는 점만 이해하고 넘어가자. (죄송(2)...)

---

 다음 포스팅에 이어서...! (양자 시뮬레이터 정리 예정)