양자 시뮬레이션의 핵심 아이디어 - 고전 컴퓨터와 서로 다른 n 입자 양자계의 일반 상태를 저장하는데 필요한 메모리 ( 지수 vs 선형 )

서로 다른 성분 n 개로 이루어진 양자계가 있고, 각 겅분이 가질 수 있는 상태 수가 c 개라고 한다.

그러면 전체 계의 상태 공간 차원은 

c^n

이 된다.

즉, 전체 파동 함수는 보통

위 처럼 쓰이며, 계수 alpha_i1 ... in 의 개수가 대략 c^n 개 필요하다.

 

왜 고전 컴퓨터에서는 메모리가 폭증하나

고전 컴퓨터로 이 양자상태를 그대로 저장하려면, 각 기저상태에 대한 복소수 진폭을 모두 저장해야 한다.

그래서 필요한 메모리량은 본질적으로

O(c^n)

에 비례한다.

정확히 말하면 c^n 비트라고 하기보다는ㄴ

• c^n 개의 복소수 개수
• 또는 정밀도 까지 포함하면 O(c^n)메모리

라고 말하는 편이 더 정확하다

왜냐하면 각 진폭 하나도 실제로는 부동소수점 수 몇 개로 저장해야 하기 때문이다.

 

왜 양자 컴퓨터에서는 훨씬 더 적은 자원으로 표현 가능한가

양자 컴퓨터는 그 상태를 직접 양자상태 자체로 담는다.

각 성분의 상태 수가 c 개라면, 한 성분을 표현하는 데 필요한 큐비트 수는 대략

k = log c

이다.

따라서 n 개의 성분 전체를 표혀녀하려면

kn = n log c

개의 큐비트가 필요하다

즉

• 고전 저장 : 지수적 O(c^n)
• 양자 표현 : 선형적 O(n log c)

라는 차이가 생긴다

 

가장 익숙한 경우 : 2 준위 계

각 성분이 큐비트처럼 두 상태만 가진다면 c = 2

k = log 2 = 1

이므로 n 개의 성분은 그냥 n 큐비트로 표현된다.

 

하지만 

이걸 곧바로 양자 컴퓨터는 모든 양자계를 쉽게 시뮬레이션한다로 받아들이면 안 된다.

이유는 두 가지

상태를 표현하는 것과 읽어내는 것은 다르다

양자 컴퓨터는 kn 큐비트에 상태를 담을 수 있지만,

그 안에 들어 있는 c^n 개의 진폭을 한 번에 전부 고전적으로 꺼낼 수는 없다.

측정하면 일부 정보만 나온다.

 

시뮬레이션이 효율적이려면 헤밀토니안 구조가 좋아야 한다.

실제로 효율적인 양자 시뮬레이션이 가능하려면 보통

• 국소적 상호작용
• 희소한 헤밀토니안
• 물리적으로 자연스러운 시간 발전

같은 구조가 필요하다.