양자컴퓨터가 정말로 더 빠를 수 있을까?

그때 그곳

1980년대에 '자연을 흉내 내려면 양자로 도는 기계가 필요하다'는 말이 나온 뒤에도, 양자컴퓨터는 상상 속 기계였습니다. 있으면 좋겠지만 **무엇에 쓸지** 아무도 보이지 못했습니다. 보통 컴퓨터로 못 하는 일을 정말 할 수 있는지도요.

왜 이 질문이었나

벨연구소의 수학자 쇼어는 거꾸로 물었습니다. 큐비트가 잘하는 일이 있다면 그건 무엇인가.

큐비트는 두 가지를 잘합니다. 여럿을 묶으면 가능성이 2배, 4배, 8배로 불어난다는 것. 그리고 가능성끼리 만나 **서로 지워질 수 있다**는 것.

그는 이 둘에 딱 맞는 문제를 찾았습니다. 큰 수를 두 소수의 곱으로 쪼개는 문제입니다. 15는 3 곱하고 5, 쉽습니다. 그런데 300자리 수라면 보통 컴퓨터로 우주의 나이보다 오래 걸립니다. 쪼개려면 그 수 안에 숨은 '되풀이되는 박자'를 찾아야 하는데, 박자 찾기는 틀린 후보들이 서로 지워지게 만들기 좋은 모양이었습니다.

알아낸 것

1994년, 쇼어는 종이 위에서 증명했습니다. 충분히 큰 양자컴퓨터라면 300자리 수도 **몇 시간이면** 쪼갤 수 있다.

하필 그 문제가 인터넷 자물쇠였습니다. 은행과 이메일과 쇼핑을 지키는 암호는 거의 전부 '큰 수는 쪼개기 어렵다'는 사실 하나에 기대고 있었습니다. 열쇠가 없어서 안전한 게 아니라, 열쇠를 만드는 데 우주의 나이가 걸려서 안전했던 것입니다.

상상 속 기계 이야기가 하루아침에 자물쇠 문제가 됐습니다.