Quantum Computing

 

이 슈뢰딩거의 고양이 실험을 요약하면 상자 안의 고양이가 1시간 뒤 절반의 확률로 살아남을 수 있고, 나머지 절반의 확률로 죽는다. 문제는 양자역학의 해석에 따르자면 이 고양이의 생사 여부를 확인해보기 전까지는 이 고양이의 상태를 살아있으면서도 동시에 죽어있는 상태라고 규정한다는 것이다

 

Qubit와 중첩 상태

일반 컴퓨터는 0과 1로 정보를 처리하고 저장하지만

양자 컴퓨터는 0과 1의 상태를 동시에 갖는 Qubit 단위로 처리하고 저장한다.

 

양자 역학은 0과 1의 두 가지 상태가 동시에 공존하는 중첩을 허용한다. 하지만 관측을 통해 상태를 확인하면 0 또는 1 가운데 하나의 값을 갖게 된다. 이처럼 관측을 통해 중첩을 깨뜨려 상태를 하나로 확정하는 과정을 결어긋남이라고 한다. 이 용어는 파동이라는 현상에서 온 것인데, 직관적으로 그 관계를 이해하기는 어렵다. 실제 결어긋남은 대상이 되는 시스템과 외부 사이에 존재하는 모든 종류의 상호 작용을 통해 일어날 수 있다.

 

"편광 필터 실험"

 

양자 컴퓨터의 용도

- 양자 시스템 시뮬레이션

입자 수가 늘어나면 관리해야 하는 계수들의 수가 기하급수적으로 증가

- 이외에도 신약개발, 화학, 화공

- 재료 또는 물질 설계

- 양자 기계 학습 (효율적인 선형대수)

 

- 공개키 암호 알고리즘에 대한 공격 : Shor's Algorithm - 정수의 효율적인 분해

 

 

양자 컴퓨터의 구현

결어긋남: 관찰을 통해 양자 상태를 붕괴시킴

 

논리적 큐빗: 물리적 큐빗 여럿을 모아 양자오류정정부호를 통해 논리적 큐빗을 구성 (결맞음을 유지)

물리적 큐빗: 시간이 지나면 결어긋남이 발생 (현재 연구 상태)

 

 

양자 알고리즘

양자 상태를 이용하는 알고리즘 or 양자 컴퓨터가 계산하는 것

 

가역성 - Reversible computing

벤자민 버튼처럼 거꾸로 흐르는 것이 가역성

반응 시 초기 상황으로 되돌아올 수 있는지의 여부를 일컫는 말이다. 가능하면 가역, 불가능한 것을 비가역이라고 한다.

엔트로피의 증가

 

입력 - 출력이 일대일 대응 함수가 아니라면?

x -> f(x) 가 아닌 x -> (x, f(x)) 

 

문제는 Garbage collection

f(x)의 중간단계를 어떻게 하면 없앨 수 있을까

이를 Upcomputing으로 해결

F와 G과 가역적이므로 F를 uncompute해서 계산의 중간값을 없앰

 

 

 

양자 중첩과 병렬 계산

고전 컴퓨터보다 빠른 이유 :병렬

무작위로 하나 골라진 대상에 대해서 출력을 알게 됨. -> 몬테 카를로 마냥

그래서 고전 컴퓨터 보다 항상 빠르다고 할 수 없음

전수 조사에는 고전 컴퓨터가 낮지만, 

데이터양이 방대하여 랜덤으로 시도해보는 것을 양자 컴퓨팅

 

그래서 확률과 연관됨. 전체에서 10%만 계산해보는 등.

(그래서 암호 비밀키 해독에 중요함)

 

Grover's algorithm

f(x)=1인 x가 하나만 존재하고 나머지는 f(x)=0

 

주기성 분석: 푸리에 변환

함수의 주기성을 분석

Fast Fourier Transform : 푸리에 변환을 효율적으로 하는 알고리즘 

양자 푸리에 변환(QFT) : 효율적으로 푸리에 변환을 할 수 있는 양자 알고리즘

그러나 QFT가 FFT를 대체할 수 없다.

데이터 입출력이 어렵기 때문

다만 Shor's algorithm은 QFT를 이용해서 a^x mod N의 주기를 계산

 

 

암호/보안

Post-quantum crypto

- 양자 컴퓨터로도 풀기 어려운  암호 체계 : 격자 기반, 다항식 기반, 부호 기반 등등

Quantum crypto

- Quantum key distribution

     송수신자가 양자 프로토콜을 통해, 비밀키 k를 공유하고, 이를 이용해 암호 통신을 진행

     비밀키 공유 과정에서 도청 발생 시, 그 사실을 송수신자가 감지 가능

 

Killer application

주로 컴퓨터 프로그래밍 소프트웨어 제품 중에 그 인기나 유용성이 아주 높아서 그 제품을 사용하기 위해서 필요한 하드웨어나 운영체제 등의 플랫폼까지도 구매하게 만들 정도로 인기와 수요가 높은 응용 프로그램 제품을 말한다.

 

 

양자 우월성

양자 컴퓨터가 고전 컴퓨터가 못 하는 것을 해낸 경우에 지칭