양자 컴퓨터의 원리: 큐비트, 양자 알고리즘, 양자 게이트

비트와 큐비트

지금 쓰는 컴퓨터를 양자 컴퓨터와 구별해 고전 컴퓨터라 부른다. 고전 컴퓨터의 최소 단위인 비트는 언제나 0 또는 1 중 하나다. 양자 컴퓨터의 최소 단위인 큐비트(qubit) 는 양자 중첩을 이용해 0과 1이 일정한 확률로 겹친 상태를 가질 수 있다.

구분	비트 3개	큐비트 3개
표현하는 상태	8가지 중 하나	8가지 전부의 중첩 (각 상태마다 확률 진폭)
읽었을 때	그 값	8가지 중 하나가 확률적으로 나온다

큐비트 n개의 상태는 2ⁿ개의 진폭으로 기술된다. 20개면 약 100만 개다. 하지만 읽어 낼 수 있는 것은 측정 한 번에 n비트뿐이다. 그래서 「큐비트가 정보를 2ⁿ개 저장한다」는 말은 반만 맞다. 이 거대한 상태 공간을 계산에 어떻게 쓰느냐가 양자 알고리즘의 몫이다.

큐비트는 특정 물질이 아니라 추상 개념이다. 두 양자 상태를 안정적으로 구별할 수 있는 것이면 무엇이든 큐비트가 된다. 전자의 스핀 업·다운을 0·1로 쓰는 스핀 큐비트 외에 초전도 회로, 이온 트랩, 중성 원자, 광자 방식이 경쟁 중이다.

양자 알고리즘: 간섭으로 정답 확률 키우기

흔한 오해: 「모든 답을 동시에 확인한다」

0~7 중 정답 하나를 맞히는 문제를 생각한다. 고전 컴퓨터는 하나씩 넣어 보는 수밖에 없고, 매 시도의 성공 확률은 1/8이다.

「큐비트에 0~7을 모두 중첩해 넣으면 한 번에 맞힌다」고 생각하기 쉽다. 그렇지 않다. 정답과 비교하려면 관측해야 하고, 관측하는 순간 중첩은 하나로 정해진다. 결국 정답이 나올 확률은 여전히 1/8이다.

진짜 원리: 확률 진폭의 간섭

일상의 확률은 0 이상이지만, 양자역학의 확률 진폭은 음수, 심지어 복소수도 될 수 있다. 관측 확률은 진폭 크기의 제곱이다. 진폭이 음수가 될 수 있으니 파동처럼 간섭한다.

간섭	효과
정답 쪽 진폭끼리 보강	정답이 관측될 확률이 커진다
오답 쪽 양·음 진폭이 상쇄	오답이 관측될 확률이 작아진다

양자 알고리즘은 관측하기 전에 간섭으로 정답 확률을 키우고 오답 확률을 줄인다. 그러면 시도 횟수가 줄어든다. 고전 확률론에는 음의 확률이 없어 이 방법을 쓸 수 없다. 그래서 양자 컴퓨팅을 「음의 부호가 있는 확률론」이라고도 부른다.

대표 알고리즘

알고리즘	푸는 문제	속도 향상
그로버(Grover)	정렬되지 않은 N개 중 조건에 맞는 것 찾기	고전 O(N) → O(√N). 100만 개면 약 1,000번
쇼어(Shor)	큰 수의 소인수분해, 이산 로그	고전 최선의 알고리즘보다 지수적으로 빠르다
도이치-조사(Deutsch–Jozsa)	함수가 상수인지 균형인지 판별	한 번의 질의로 판별. 원리 시연용

간섭을 쓸모 있게 설계한 알고리즘이 있어야만 빨라진다. 그런 알고리즘을 찾는 것 자체가 어렵다.

양자 게이트

고전 컴퓨터가 NOT, AND 같은 논리 게이트로 비트를 바꾸듯, 양자 컴퓨터는 양자 게이트로 큐비트 상태를 바꾼다.

블로흐 구면

큐비트 하나의 상태는 구 위의 한 점(중심에서 표면을 향한 화살표)으로 그릴 수 있다. 이를 블로흐 구면(Bloch sphere) 이라 한다.

        |0⟩  (북극: 0일 확률 100%)
         ↑
   ──────●──────  적도: 0과 1이 50%씩 중첩
         ↓
        |1⟩  (남극: 1일 확률 100%)

0과 1의 관측 확률은 z좌표(높이) 만으로 정해진다. 위에 있을수록 0일 확률이 높다.
x·y 방향은 관측 확률에는 영향이 없는 상대 위상이다. 위상은 간섭의 재료가 된다.
단일 큐비트 게이트는 이 화살표를 회전시키는 연산으로 볼 수 있어, 행렬 계산 없이도 직관적으로 이해할 수 있다.

주요 게이트

게이트	블로흐 구면에서	하는 일
Pauli X	x축 기준 180° 회전	0과 1의 확률을 뒤바꾼다. 고전 NOT에 대응. 80:20 → 20:80
Pauli Y, Z	y축, z축 기준 180° 회전	Z는 확률은 그대로 두고 위상만 바꾼다
Hadamard (H)	x축과 z축 사이 대각선 기준 180° 회전	확정된 0을 0·1 반반 중첩으로 만든다. 중첩을 만드는 기본 게이트
CNOT (CX)	큐비트 2개	컨트롤 큐비트가 1일 때만 타깃 큐비트에 X를 건다. CY, CZ도 있다

H와 CNOT을 이어 붙이면 얽힘이 생긴다. 첫 큐비트에 H를 걸어 중첩을 만들고 그것을 컨트롤로 CNOT을 걸면, 두 큐비트는 「둘 다 0」과 「둘 다 1」이 겹친 얽힘 상태(벨 상태)가 된다. 실제 양자 알고리즘은 이런 게이트를 이어 붙인 양자 회로로 표현한다.

암호에 미치는 영향

RSA는 큰 수를 곱하기는 쉽고 소인수분해하기는 어렵다는 사실에 기댄다. 타원 곡선 암호도 비슷하게 이산 로그 문제에 기댄다. 쇼어 알고리즘을 돌릴 만큼 큰 오류 정정 양자 컴퓨터가 나오면 이런 공개키 암호는 깨진다.

지금 그런 컴퓨터는 없다. 하지만 지금 암호문을 모아 뒀다가 나중에 푸는 「지금 수집, 나중에 해독(harvest now, decrypt later)」 위협 때문에 전환은 미리 해야 한다.
미국 NIST는 2024년 8월 양자내성암호(PQC) 표준 세 가지를 확정했다. 키 교환용 ML-KEM(FIPS 203), 서명용 ML-DSA(FIPS 204)와 SLH-DSA(FIPS 205)다. 2025년에는 예비 키 교환 알고리즘으로 HQC를 골랐다. RSA·ECC는 2030년 이후 신규 사용 중단, 2035년 이후 금지하는 일정이 제안돼 있다.
AES 같은 대칭키 암호는 그로버 알고리즘으로 보안 강도가 절반쯤으로 줄 뿐이라, 키 길이를 늘리면(AES-256) 대응된다.
웹에서는 이미 주요 브라우저와 TLS 라이브러리가 ML-KEM을 섞은 하이브리드 키 교환을 쓴다(HTTPS와 TLS).

흔한 오해

오해	실제
양자 컴퓨터는 고전 컴퓨터보다 빠르다	특정 문제만 빠르다. 쓸 만한 양자 알고리즘이 없는 문제는 빨라지지 않는다
모든 가능성을 병렬로 계산한다	측정하면 하나만 나온다. 속도는 간섭을 설계한 알고리즘에서 나온다
이미 암호를 다 뚫을 수 있다	아직 그만한 규모의 오류 정정 양자 컴퓨터는 없다. 다만 대비는 지금 시작됐다
고전 컴퓨터를 대체할 것이다	가능성이 매우 낮다. 극저온 등 까다로운 운영 조건과 비용 때문에, 슈퍼컴퓨터처럼 특정 문제(화학·재료 시뮬레이션, 최적화 등)를 위한 보조 장치로 쓰일 가능성이 크다

큐비트는 주변과의 상호작용으로 중첩이 쉽게 깨진다(결어긋남, decoherence). 그래서 여러 물리 큐비트를 묶어 오류가 정정된 논리 큐비트 하나를 만드는 양자 오류 정정이 핵심 과제다. 물리 큐비트는 2023년에 1,000개를 넘긴 칩(IBM Condor, 1,121개)이 나왔고(Scientific American), 논리 큐비트는 같은 해 중성 원자로 48개를 얽어 회로를 돌린 실험이 보고됐다(Bluvstein 외, Nature). IBM은 2029년 논리 큐비트 200개로 1억 번의 연산을 돌리는 오류 내성 시스템(Starling)을 목표로 하고 있다(IBM, 2025).

정리

큐비트는 중첩 상태를 갖지만, 측정하면 하나의 값만 나온다.
양자 알고리즘의 힘은 「동시 계산」이 아니라 확률 진폭의 간섭에서 나온다.
단일 큐비트 게이트는 블로흐 구면 위의 회전이고, H + CNOT으로 얽힘을 만든다.
그로버는 √N, 쇼어는 소인수분해를 지수적으로 빠르게 한다. 쇼어 때문에 RSA·ECC는 양자내성암호로 옮겨 가는 중이다.
양자 컴퓨터는 고전 컴퓨터의 대체가 아니라 특정 문제용 가속기다. 최대 과제는 오류 정정이다.

버그 제보