양자 알고리즘의 중요성
양자 컴퓨터의 장점이 중첩에 있는 것처럼 말해 놓고 이제 와서 무슨 소리냐고 할 수도 있겠다. 물론 둘 다 틀린 말은 아니고, 함수값을 모두 한 번에 계산할 수는 있지만 그것을 모두 읽어내는 것은 불가능하다는 말이다. 따라서 우리가 알고 싶은 함수값의 확률을 높여서 잘 골라내는 일이 중요한데, 이것이 바로 양자 알고리즘에 해당한다. 예를 들어 어떤 함수의 최소값을 찾는 문제를 생각하자. 이런 문제는 최소값 자체보다는 최소값을 주는 입력값을 알고 싶은 경우가 많은데, 여기서는 이 입력값이 가질 수 있는 값은 상당히 많다고 가정하자. 보통 변수가 10개이고, 변수당 가질 수 있는 값이 100개만 되어도 모든 값을 계산해 보려면 10010 = 1020번 계산해야 한다. 초당 1억번 계산한다고 해도 1012초, 30000년 이상 걸리는 셈이다. 그런데 알려진 양자 알고리즘을 이용하면 1010번만 계산해도 된다. 똑같이 초당 1억번 계산하는 양자 컴퓨터라면 불과 100초 밖에 걸리지 않는다.
이 양자 알고리즘은 모든 입력값을 중첩해 한 번에 계산한 다음, 함수값을 서로 서로 비교해 (이것 역시 중첩을 이용해 단 한번에) 최소값의 확률을 아주 약간 높이는 방법을 취한다. 이 과정을 1010번 반복하면 최소값의 확률이 거의 1에 근접하고, 이때 측정하면 최소값을 알아낼 수 있다. 물론 아주 작지만 실패할 확률도 있다. 그럴 때는 몇 번 더 해보면 되는 일이다. 그래도 불과 100초 밖에 걸리지 않으니 말이다. 자연은 우리에게 모든 함수값을 한 번에 계산할 수 있도록 허락했지만 그것을 모두 읽어낼 수 있도록 하지는 않은 것이다. 참 오묘한 일이다. 여기에 사람들의 지혜가 더해지면 기존의 컴퓨터로는 도저히 풀 수 없는 문제들을 빨리 풀 수 있다. 현재까지 발견된 대표적인 양자 알고리즘으로는 소인수분해, 검색, 행렬 대각화 알고리즘 등이 있는데, 이것 각각만 하더라도 엄청난 유용성을 갖고 있다. 최소값을 찾는 알고리즘은 검색 알고리즘에 대응하며, 이것은 알려진 양자 알고리즘 중에서도 느린 편에 속한다.
중첩을 이용하면 양자 역학적 시스템을 시뮬레이션 하는 것도 가능해진다. 앞서 양자 비트가 두 개 있다면 가능한 상태가 네 가지라고 했다. 양자 비트가 n개라면 2n개의 고유상태가 존재하고 이는 고전적인 비트도 마찬가지다. 하지만 고전적인 비트는 한 번에 하나의 고유상태만 있기 (하나의 값만을 갖기) 때문에 그 값을 n개의 비트를 이용하면 표현할 수 있다. 하지만 양자 비트가 갖는 2n개의 상태는 모두 동시에 중첩돼 있을 수 있기 때문에 양자 비트의 상태를 표현하려면 각 고유상태의 계수를 모두 알아야 한다. 이 계수는 보통 복소수로 주어지므로 2n개의 복소수를 표현할 수 있는 변수가 필요하며, 이로 인해 양자 비트의 상태를 비트로 시뮬레이션 한다는 것은 거의 불가능하다. 양자 비트가 100개만 있어도 2100 = 1030개의 복소수를 표현하기 위한 변수들이 필요하기 때문이다.
그런데 양자 비트 100개를 시뮬레이션 하기 위해서는 당연히 100개의 양자 비트만 필요하다. 복잡한 양자 시스템을 시뮬레이션 할 수 있는 방법은 양자 컴퓨터 밖에 없으며, 만약 양자 컴퓨터가 실용화된다면 사람이 시뮬레이션 할 수 있는 한계를 획기적으로 늘림에 따라 물리학뿐만 아니라 전자, 전산, 화학, 생물, 신약 개발 등의 분야에서 새로운 지평을 열 수 있다.
|
