양자컴퓨터
기존 컴퓨터는 트랜지스터로 이루어져 있고
전기가 흐르냐 안흐르냐에 따라 0과 1로 데이터를 다룬다.
그런데 기술의 발전으로 트랜지스터가 점점 작아지고 나노미터단위가 되면서
양자 영역으로 진입하게 되었고, (원자 한개가 대략 0.1 나노미터)
트랜지스터의 채널과 절연막의 두께가 전자의 파동이 미치는 범위만큼 얇아지면서
전자가 벽을 뚫고 지나가는 현상이 발생하기 시작했다.
(양자역학으로 인해 전자가 존재할 확률이 절연체 너머에서도 나타남)
따라서 스위치를 꺼도 전류가 흐르는 '누설 전류'가 발생하면서
스위치로서의 기능을 상실하기 시작하는데...
공상과학 소설에 등장하는 이야기 같지만, 양자 컴퓨터란 이렇게
미시세계에서의 양자역학적 현상을 이용한 컴퓨터를 설계 및 계산하는 것이다.
따라서 원자, 빛, 스핀, 초전도체(전하량/위상) 등 양자역학적 현상이 있는 것이라면
무엇이든 활용해서 양자컴퓨터를 만들 수 있다
기존에는 손오공 한명이 길을 다 가보고 결과를 알았다면,
양자 컴퓨터는 손오공 한명이 분신술을 써서 동시에 계속 길을 찾고
막다른 길로 간 분신들은 서로 상쇄되어 사라지고,
출구로 간 분신들만 서로 합쳐져서 정답일 확률이 극대화된다.
구체적인 방식은 아래와 같다.
1. 큐비트(Qubit)에 자기장이나 레이저를 정밀하게 쏘아 상태를 변화 시키고, 기존 컴퓨터의 NOT, CNOT 같은 양자 논리 게이트를 구현
2. 양자 상태를 중첩시키고 간섭을 일으켜서 찾는 정답이 나올 확률을 증폭시킴
3. 양자를 관측하면, 중첩되어 있던 상태가 하나로 붕괴되면서 최종 결과가 나옴
수학적으로는 양자 푸리에 변환으로 풀게 된다.
이 수식에서 가장 중요한 부분은 자연상수 e가 허수 i를 지수로 가지고 있어서
회전을 나타낸다는 점이다.
(e는 변화율이 자기 자신의 크기에 비례하는 자연계의 현상에서 비롯한 자연상수로,
미분하면 자기 자신이 나와서 내 크기가 곧 내가 변하는 속도라는 의미를 가진다)
데이터를 일정한 각도로 계속 회전 시키다 보면 원래 위치로 돌아오는 '주기'가 생기고,
이 회전의 빈도를 측정하여 숫자의 소인수 분해나 복잡한 패턴을 쉽게 찾아낼 수 있다.
고전적인 이산 푸리에 변환은
$$O(N^2)$$ 의 계산량이 필요하지만, (고속 푸리에 변환도 $$O((\N log N))$$
양자 회로에서는 이 '회전 게이트(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의 소인수이다.
글
