Description
노벨 물리학 수상자인 리차드 파인만(Richard Feynman)이 양자역학에 대해 “If you think you understand quantum mechanics, you don’t understand quantum mechanics.”라고 한 것은 그만큼 양자역학의 이해가 힘들다는 뜻이다. 시작부터 매우 실망스러운 말이다. 하지만 파인만은 1981년 “Simulating Physics with Computers”라는 제목의 소규모 MIT 강연에서 양자 시스템을 사용하여 고전(일반) 컴퓨터에서 매우 어렵거나 불가능한 계산을 수행하는 아이디어를 제안했다. 양자의 세계에서 일어나는 현상을 전반적으로 이해할 수는 없어도 양자를 이용한 계산은 당연히 가능하다.
양자 컴퓨터는 일반 컴퓨터와 본질적으로 다른 하드웨어이다. 양자 컴퓨터에는 CPU도 없고 하드디스크 같은 메모리도 없으며, 정보를 가지고 있는 큐비트의 상태를 다른 큐비트에 복사할 수도 없다. 그러나 양자 컴퓨터의 매우 큰 장점은 n개의 큐비트를 중첩하여 2의 n승개의 연산을 동시에 할 수 있는 것이다. 이는 일반 컴퓨터가 흉내 낼 수 없는 중요한 장점이다.
하지만 양자 컴퓨터가 2의 n승개의 연산을 동시에 수행하더라도 중간에 결과를 알고 싶다면 n 큐비트를 측정해야 하는데, 실제로 n 큐비트를 측정하면 2의 n승개의 연산 결과 중 오직 1개의 결과만 알 수 있고, 다른 모든 2의 n승-1개의 중간 결과는 모두 사라진다. 일반 컴퓨터에서는 이러한 불상사는 안 일어난다. 즉, 일반 컴퓨터에서는 중간 결과 일부분을 읽고 처리하여도 중간 결과는 사라지지 않는다. 이는 양자 컴퓨터의 큰 제약점이며, 양자 컴퓨터가 일반 컴퓨터가 해결할 수 있는 모든 문제를 해결할 수 없는 근본적인 이유 중 하나이다.
그러나 양자 컴퓨터는 데이터의 패턴 추측이나 주기(period)를 찾는 문제, 최대 또는 최솟값을 찾는 최적화 문제, 최소 고윳값을 찾는 문제 등을 2의 n승개의 병렬 연산을 이용하여 기하급수적으로 빠르게 해결한다. 아무리 빠른 슈퍼컴퓨터를 수백 수천 대를 가지고 동시에 위에 말한 문제를 해결하려해도 앞으로 만들어질 오류 보정 기능을 갖춘 양자 컴퓨터 1대를 따라갈 수 없다.
30년 넘게 알고리즘을 강의하고 피터 쇼어의 소인수분해 양자 알고리즘도 수년간 강의해보았다. 매년 쇼어의 소인수분해 알고리즘을 컴퓨터과학과 학부생들에게 강의할 때마다 양자역학의 기본 지식 이해는커녕 양자역학의 용어부터 학부생들에게 매우 높은 장벽이 되는 것을 느꼈다. 기말시험에 쇼어 알고리즘에 대해 문제가 나온다고 하고, 실제 출제하면 답을 비슷하게 쓰는 학생은 8∼90명 중 두셋 정도였다.
이 책을 접하는 독자 대부분은 일반 컴퓨터의 알고리즘에 익숙하다고 본다. 그런데 양자 알고리즘을 처음 보면 일반 컴퓨터의 알고리즘과 비교하여 그 형태도 다르고, 알고리즘의 입력이 어디에 있는지조차 불분명하며, 큐비트 상태를 나타내는 생소한 양자 식으로 알고리즘의 단계를 설명하는 등 ‘알고리즘’이라는 용어만이 일반 컴퓨터 알고리즘과 같다는 것을 느낄 것이다. 이러한 장벽은 양자역학의 용어뿐 아니라, 앞서 설명한 양자 컴퓨터 자체의 특수한 하드웨어에 기인한다. 양자역학 용어 중, 중첩이나 얽힘은 누구나 들어본 용어라 별문제 없지만, 위상이나 간섭 효과만 해도 생소해지기 시작한다. 눈으로 볼 수 있는 것도 아니고, 체감할 수 있는 것도 아니기 때문이다.
양자 컴퓨터는 일반 컴퓨터와 본질적으로 다른 하드웨어이다. 양자 컴퓨터에는 CPU도 없고 하드디스크 같은 메모리도 없으며, 정보를 가지고 있는 큐비트의 상태를 다른 큐비트에 복사할 수도 없다. 그러나 양자 컴퓨터의 매우 큰 장점은 n개의 큐비트를 중첩하여 2의 n승개의 연산을 동시에 할 수 있는 것이다. 이는 일반 컴퓨터가 흉내 낼 수 없는 중요한 장점이다.
하지만 양자 컴퓨터가 2의 n승개의 연산을 동시에 수행하더라도 중간에 결과를 알고 싶다면 n 큐비트를 측정해야 하는데, 실제로 n 큐비트를 측정하면 2의 n승개의 연산 결과 중 오직 1개의 결과만 알 수 있고, 다른 모든 2의 n승-1개의 중간 결과는 모두 사라진다. 일반 컴퓨터에서는 이러한 불상사는 안 일어난다. 즉, 일반 컴퓨터에서는 중간 결과 일부분을 읽고 처리하여도 중간 결과는 사라지지 않는다. 이는 양자 컴퓨터의 큰 제약점이며, 양자 컴퓨터가 일반 컴퓨터가 해결할 수 있는 모든 문제를 해결할 수 없는 근본적인 이유 중 하나이다.
그러나 양자 컴퓨터는 데이터의 패턴 추측이나 주기(period)를 찾는 문제, 최대 또는 최솟값을 찾는 최적화 문제, 최소 고윳값을 찾는 문제 등을 2의 n승개의 병렬 연산을 이용하여 기하급수적으로 빠르게 해결한다. 아무리 빠른 슈퍼컴퓨터를 수백 수천 대를 가지고 동시에 위에 말한 문제를 해결하려해도 앞으로 만들어질 오류 보정 기능을 갖춘 양자 컴퓨터 1대를 따라갈 수 없다.
30년 넘게 알고리즘을 강의하고 피터 쇼어의 소인수분해 양자 알고리즘도 수년간 강의해보았다. 매년 쇼어의 소인수분해 알고리즘을 컴퓨터과학과 학부생들에게 강의할 때마다 양자역학의 기본 지식 이해는커녕 양자역학의 용어부터 학부생들에게 매우 높은 장벽이 되는 것을 느꼈다. 기말시험에 쇼어 알고리즘에 대해 문제가 나온다고 하고, 실제 출제하면 답을 비슷하게 쓰는 학생은 8∼90명 중 두셋 정도였다.
이 책을 접하는 독자 대부분은 일반 컴퓨터의 알고리즘에 익숙하다고 본다. 그런데 양자 알고리즘을 처음 보면 일반 컴퓨터의 알고리즘과 비교하여 그 형태도 다르고, 알고리즘의 입력이 어디에 있는지조차 불분명하며, 큐비트 상태를 나타내는 생소한 양자 식으로 알고리즘의 단계를 설명하는 등 ‘알고리즘’이라는 용어만이 일반 컴퓨터 알고리즘과 같다는 것을 느낄 것이다. 이러한 장벽은 양자역학의 용어뿐 아니라, 앞서 설명한 양자 컴퓨터 자체의 특수한 하드웨어에 기인한다. 양자역학 용어 중, 중첩이나 얽힘은 누구나 들어본 용어라 별문제 없지만, 위상이나 간섭 효과만 해도 생소해지기 시작한다. 눈으로 볼 수 있는 것도 아니고, 체감할 수 있는 것도 아니기 때문이다.
양자 알고리즘
$27.00