보통 컴퓨터의 비트는 0 또는 1입니다. 양자컴퓨터의 큐비트는 0과 1의 중첩일 수 있습니다(첫걸음 8장). 큐비트 \(n\)개면 \(2^n\)개의 조합이 동시에 관여할 수 있으니 «엄청나게 빠르다»고 흔히 설명합니다.
그런데 이 설명은 절반만 맞고, 나머지 절반이 더 중요합니다. 중첩 상태를 측정하면 결국 하나만 나옵니다. \(2^n\)가지를 동시에 계산해도 답을 한 개만 꺼낼 수 있다면 소용이 없습니다.
진짜 열쇠는 간섭입니다(둘째 걸음 1장). 양자 알고리즘은 계산 과정을 교묘하게 설계해서, 틀린 답에 해당하는 파동함수들이 서로 상쇄되고 맞는 답 쪽만 보강되게 만듭니다. 측정했을 때 정답이 나올 확률이 높아지도록 «확률을 몰아 주는» 것입니다. 그래서 양자컴퓨터는 만능이 아니라, 이런 몰아 주기를 설계할 수 있는 특정 문제에서만 빠릅니다.
대표적인 것이 두 가지입니다. ① 쇼어 알고리즘(1994) — 큰 수를 소인수분해합니다. 오늘날 인터넷 암호(RSA)는 «큰 수를 소인수분해하기 어렵다»는 데 기대고 있으므로, 충분히 큰 양자컴퓨터가 나오면 이 암호가 깨집니다. ② 그로버 알고리즘(1996) — 정렬되지 않은 자료에서 찾기를 \(N\)번이 아니라 \(\sqrt{N}\)번쯤으로 줄입니다.
현실의 어려움은 결어긋남입니다(첫걸음 8장 심화). 큐비트는 주변과 조금만 상호작용해도 중첩이 흐트러집니다. 그래서 절대영도 가까이 냉각하고 차폐하며, 오류를 정정하기 위해 «논리 큐비트 하나»에 물리 큐비트를 수백~수천 개 쓰는 방식이 연구되고 있습니다. 지금 단계는 «특정 과제에서 앞선다»를 보이는 수준이며, 범용 실용화까지는 아직 갈 길이 멉니다.