양자컴퓨터
기존 컴퓨터는 트랜지스터로 이루어져 있고
전기가 흐르냐 안흐르냐에 따라 0과 1로 데이터를 다룬다.
그런데 기술의 발전으로 트랜지스터가 점점 작아지고 나노미터단위가 되면서
양자 영역으로 진입하게 되었고, (원자 한개가 0.1 나노미터)
트랜지스터의 채널과 절연막의 두께가 전자의 파동이 미치는 범위만큼 얇아지면서
전자가 벽을 뚫고 지나가는 현상이 발생하기 시작했다.
(양자역학으로 인해 전자가 존재할 확률이 절연체 너머에서도 나타남)
따라서 스위치를 꺼도 전류가 흐르는 '누설 전류'가 발생하면서
스위치로서의 기능을 상실하기 시작하는데...
공상과학 소설에 등장하는 이야기 같지만, 양자 컴퓨터란 이렇게
미시세계에서의 양자역학적 현상을 이용한 컴퓨터를 설계 및 계산하는 것이고,
따라서 양자역학적 현상이 있는 원자, 빛, 스핀, 초전도체 등
다양한 것을 활용해서 만들 수 있다
양자 컴퓨터의 핵심은,
1. 양자에 자기장을 걸어서 상태를 변경 시키는 방식으로 전통적인 트랜지스터처럼 NOT, CNOT 같은 논리 게이트를 만든다
2. 원하는 결과가 나올 때까지 이리저리 자기장을 준다.
3. 결과가 나온 뒤에 양자들을 관측하면 중첩이 풀리면서 중간 과정을 알 수 있다.
보통 미로를 예시로 든다.
기존에는 손오공 한명이 길을 다 가보고 결과를 알았다면
양자컴퓨터는 손오공 한명이 분신술을 써서 동시에 계속 길을 찾고
막다른 길로 간 분신들은 서로 상쇄되어 사라지고,
출구로 간 분신들만 서로 합쳐져서(간섭) 정답일 확률이 극대화된다.
실제로는 이것을 양자 푸리에 변환으로 풀게 된다.
이 수식에서 가장 중요한 부분은 자연상수 e가 허수 i를 지수로 가지고 있어서
회전을 나타낸다는 점이다.
(e는 변화율이 자기 자신의 크기에 비례하는 자연계의 현상에서 비롯한 자연상수로,
미분하면 자기 자신이 나와서 내 크기가 곧 내가 변하는 속도라는 의미를 가진다)
데이터를 일정한 각도로 계속 회전 시키다 보면 원래 위치로 돌아오는 '주기'가 생기고,
이 회전의 빈도를 측정하여 숫자의 소인수 분해나 복잡한 패턴을 쉽게 찾아낼 수 있다.
고전적인 이산 푸리에 변환은
$$O(N^2)$$ 의 계산량이 필요하지만,
양자 회로에서는 이 '회전 게이트(Rotation Gate)'들을 중첩된 상태에 동시에 적용함으로써
$$O((\log N)^2)$$
이라는 압도적인 속도 향상을 보인다.
컴퓨터가 하나씩 대조해가면서 정답을 찾는다면,
양자 컴퓨터는 데이터를 파동으로 바꾸어 그 간섭 현상을 이용해 정답을 뽑아내는 것이다.
그리고 정답을 뽑아낸 뒤 관측하면 그 계산이 어떻게 이루어졌는지 알 수 있다.
보안 위협 (쇼어 알고리즘)
1. 1보다 크고 N보다 작은 작은 정수 a를 임의로 선택2. gcd (N,A)가 1이 아니면 gcd (N, a)가 N의 소인수이다1이라면, 함수$$f(x) = a^x (mod N)$$의 주기 r을 찾는다.3. r이 홀수이면 1번부터 다시 시작하고, r이 짝수이면 다음과 같은 gcd1, gcd2 를 구한다.$$ gcd_1 = gcd(N, a^{r/2} +1) $$
$$ gcd_2 = gcd(N, a^{r/2} -1) $$4. gcd1, gcd2 이 1과 N이라면 처음부터 다시 시작하고, 아니라면 gcd1, gcd2 가 N의 소인수이다.
글
