📚 지식 노트

비트와 큐비트

고전 비트는 언제나 0 아니면 1이다. 큐비트의 상태는 두 기저 |0⟩과 |1⟩의 선형 결합 α|0⟩ + β|1⟩이고, α와 β는 복소수 진폭(amplitude)이며 |α|² + |β|² = 1을 지킨다. 전체에 같은 위상을 곱한 상태는 물리적으로 구별되지 않으므로, 큐비트 하나는 결국 각도 두 개 θ와 φ로 적을 수 있고 이것이 구 위의 한 점이 된다. 이 구를 블로흐 구(Bloch sphere)라 한다.

흔히 "큐비트는 0과 1을 동시에 가진다"고 말하지만 정확하지 않다. 큐비트 하나를 재면 비트 하나만 나오고, n큐비트에서 한 번에 꺼낼 수 있는 고전 정보도 n비트다(홀레보 한계). 다른 점은 n큐비트의 상태를 적는 데 진폭이 2ⁿ개 필요하다는 것, 그리고 그 진폭들이 서로 더해지고 지워질 수 있다는 것이다. 양자 알고리즘은 이 간섭을 설계해 원하는 답의 진폭만 키운다.

중첩과 측정

측정 결과의 확률은 진폭 크기의 제곱이다(본 규칙, Born rule). 진폭이 0.6과 0.8i라면 0이 나올 확률은 0.6² = 0.36, 1이 나올 확률은 |0.8i|² = 0.64다. 허수 단위 i는 확률에는 드러나지 않지만, 다른 경로와 만날 때 더해지는 방향을 바꿔 결과를 달리 만든다.

측정은 되돌릴 수 없다. 재는 순간 상태는 나온 결과의 기저 상태가 되고, 원래 진폭은 사라진다. 그래서 양자 회로는 계산 내내 재지 않고 진폭을 다듬다가 마지막에 한 번 잰다. 회로 밖 환경이 큐비트를 "재 버리는" 것이 결어긋남(decoherence)이고, 이것이 양자 하드웨어가 싸우는 노이즈의 정체다.

게이트: 상태에 곱하는 행렬

양자 게이트는 상태 벡터에 곱하는 유니터리 행렬이다. 유니터리라서 확률의 합 1을 지키고, 거꾸로 되돌릴 수 있다. X는 0과 1을 바꾸는 NOT, Z는 |1⟩의 부호만 뒤집고, H(아다마르)는 |0⟩을 (|0⟩ + |1⟩)/√2인 |+⟩로 보낸다. 두 큐비트 게이트 CNOT은 제어 큐비트가 1일 때만 표적 큐비트를 뒤집는다.

n큐비트 중 하나에 게이트를 거는 것은 2×2 행렬과 나머지 큐비트의 항등 행렬의 텐서곱, 곧 2ⁿ×2ⁿ 행렬을 곱하는 것과 같다. 시뮬레이터는 이 큰 행렬을 만들지 않고, 해당 큐비트 비트만 다른 칸 두 개씩 짝지어 2×2를 곱한다. 한 큐비트 게이트 몇 개와 CNOT만 있으면 어떤 유니터리든 원하는 정밀도로 근사할 수 있다(보편 게이트 집합).

유니터리라는 조건에서 곧바로 나오는 제약이 복제 불가 정리(no-cloning theorem)다. 1982년 Wootters·Zurek과 Dieks가 각각 증명했다. 모르는 상태 |φ⟩를 받아 |φ⟩|φ⟩로 복사하는 게이트 U가 있다고 하자. 두 상태 φ, ψ를 모두 복사할 수 있다면 유니터리는 내적을 지키므로 |⟨φ|ψ⟩|² = |⟨φ|ψ⟩|이어야 하고, 이는 두 상태가 같거나(내적의 크기 1) 직교할 때(0)만 성립한다. 그러니 아무 상태나 복사하는 장치는 없다. 고전 비트처럼 백업을 떠 둘 수 없어 오류 정정이 어려워지고(아래 오류 정정 절), 얽힘으로 빛보다 빠른 신호를 보낼 수 없다는 결론과도 맞물린다.

회로: H와 CNOT으로 벨 상태 만들기

양자 회로는 가로줄 하나가 큐비트 하나이고, 왼쪽에서 오른쪽으로 시간이 흐른다. 가장 작은 흥미로운 회로는 |00⟩에서 첫 큐비트에 H, 이어 CNOT을 거는 것이다. 단계마다 상태 벡터가 어떻게 바뀌는지 넘겨 보면 된다.

H 뒤의 상태 (|00⟩ + |10⟩)/√2는 (|0⟩ + |1⟩)/√2 ⊗ |0⟩으로 큐비트별로 나뉜다. CNOT 뒤의 (|00⟩ + |11⟩)/√2는 어떤 두 한 큐비트 상태의 곱으로도 적을 수 없다. 이렇게 나뉘지 않는 상태를 얽힌(entangled) 상태라 하고, 이 특정한 상태를 벨 상태라 한다.

얽힘

벨 상태의 두 큐비트를 재면 결과는 00 아니면 11이다. 각자만 보면 50 : 50의 무작위지만, 둘을 맞춰 보면 늘 같다. 같은 50 : 50이라도 |+⟩|+⟩ 같은 곱 상태는 네 결과가 고르게 나와 서로 상관이 없다. 두 큐비트 진폭 a, b, c, d를 2×2로 늘어놓았을 때 행렬식 ad − bc가 0이면 곱 상태로 나뉘고, 0이 아니면 얽혀 있다.

얽힘은 신호를 빛보다 빨리 보내는 수단이 아니다. 한쪽에서 무엇을 하든 다른 쪽의 결과 분포는 50 : 50 그대로이고, 상관은 두 결과를 고전 통신으로 맞춰 볼 때에만 드러난다. 그래도 얽힘은 순간 이동(teleportation) 프로토콜, 오류 정정의 신드롬 측정, 그리고 거의 모든 양자 속도 향상의 재료다.

간섭: H를 두 번 걸면 제자리

H를 한 번 걸면 |0⟩이 반반의 중첩이 된다. 한 번 더 걸면 다시 반반으로 섞일 것 같지만, 실제로는 확률 100%로 |0⟩에 돌아온다. 진폭이 경로마다 곱해져 더해지기 때문이다. |1⟩로 가는 두 경로 중 하나는 H 행렬의 −1/√2 칸을 지나 부호가 뒤집히고, 그래서 +½과 −½이 정확히 지워진다.

고전적인 동전 던지기를 두 번 하면 여전히 반반이다. 확률은 음수가 없어 더할수록 섞이기만 한다. 양자 알고리즘의 요령은 틀린 답으로 가는 경로들이 서로 지워지고 맞는 답으로 가는 경로들이 서로 보강되도록 게이트를 배치하는 것이다. 다음 절들의 알고리즘은 모두 이 한 가지 생각의 변주다.

작은 알고리즘: 번스타인–바지라니

비밀 비트열 s가 있고, x를 넣으면 s·x (mod 2), 곧 s와 x가 함께 1인 자리 수의 홀짝을 알려 주는 함수(오라클)가 있다. 고전적으로는 x = 100, 010, 001처럼 한 자리씩 물어 n번 불러야 s를 안다. 양자 회로는 모든 x의 중첩을 한꺼번에 넣고, 오라클이 그 결과를 진폭의 부호로 새기게 한 뒤, H로 간섭시켜 한 번에 s를 읽는다.

오라클 직후에는 8칸 모두 크기가 같아서 재도 아무것도 모른다. 정보는 부호 무늬에만 있다. 마지막 H가 그 무늬를 한 칸으로 모으는 것이 간섭이다. 같은 구조로 함수가 상수인지 균형인지를 한 번에 가리는 도이치–조사 알고리즘도 있다. 둘 다 실용 문제는 아니지만, 쇼어 알고리즘의 "중첩 → 오라클 → 푸리에 변환 → 측정" 뼈대를 가장 작은 크기로 보여 준다.

그로버 탐색: √N번이면 된다

정렬되지 않은 N개 중 조건을 만족하는 하나를 찾는다. 고전적으로는 평균 (N+1)/2번 확인해야 한다. 그로버 알고리즘은 고른 중첩에서 시작해 "표시된 칸의 부호 뒤집기(오라클) → 평균에 대해 뒤집기(확산)"를 약 π/4·√N번 되풀이한다. 한 번 돌 때마다 표시된 칸의 진폭이 조금씩 커지는데, 이것을 진폭 증폭(amplitude amplification)이라 한다.

N = 100만이면 고전 탐색은 평균 500,001번, 그로버는 785번이다. 극적으로 보이지만 제곱근 속도 향상일 뿐이라 지수적이지 않고, 오라클 한 번이 고전 확인 한 번보다 훨씬 비싼 실제 기기에서는 이득이 크게 줄어든다. 구조 없는 탐색에서는 √N보다 빠를 수 없다는 것도 증명되어 있어서, 양자 컴퓨터가 NP-완전 문제를 효율적으로 푼다고 기대할 근거는 없다. 대칭키 암호에 미치는 영향(키 길이를 두 배로)은 아래 쇼어 절의 링크에 정리되어 있다.

쇼어 알고리즘과 RSA

쇼어 알고리즘은 소인수분해를 주기 찾기로 바꾼다. N과 서로소인 a를 골라 a^x mod N이 되풀이되는 주기 r을 찾으면, r이 짝수일 때 gcd(a^r/2 ± 1, N)이 N의 약수를 준다. 주기를 찾는 부분만 양자 회로(양자 푸리에 변환)가 맡고, 나머지는 고전 계산이다.

주기 찾기는 함수값이 r마다 되풀이된다는 "부호 무늬"를 양자 푸리에 변환으로 간섭시켜 r의 배수 근처에 진폭을 모으는 일이다. 번스타인–바지라니의 마지막 H가 하던 일을 더 큰 규모로 하는 셈이다. RSA·타원 곡선 암호가 이 때문에 어떻게 깨지는지, 그 대비로 무엇이 표준이 되었는지는 암호학 노트의 양자내성 절에서 다룬다. 다만 필요한 기계의 크기는 짚어 둔다. Gidney(2025)는 게이트 오류율 0.1%를 가정할 때 RSA-2048을 일주일 안에 인수분해하는 데 노이즈 있는 큐비트 100만 개 미만이면 된다고 추정했다. 오늘의 기기는 그보다 몇 자릿수 작다.

양자 오류 정정

고전 컴퓨터는 비트를 복사해 다수결로 오류를 고친다. 큐비트는 복제 불가 정리 때문에 복사할 수 없고, 재면 상태가 무너진다. 해법은 정보를 여러 큐비트의 얽힘에 나눠 담고 데이터는 재지 않고 큐비트 사이의 패리티만 재는 것이다. 가장 작은 예가 3큐비트 비트 뒤집기 부호다. α|0⟩ + β|1⟩을 α|000⟩ + β|111⟩으로 늘려 두고, 이웃끼리의 패리티 두 개(신드롬)를 재면 α와 β는 그대로 둔 채 어느 큐비트가 뒤집혔는지만 알 수 있다.

물리 오류율이 1%라면 둘 이상이 동시에 뒤집힐 때만 실패하므로 논리 오류율은 약 0.03%로 준다. 이처럼 물리 오류가 어떤 문턱(threshold) 아래에 있어야 부호를 키울수록 이득이 난다. 실용 후보인 표면 부호(surface code)는 2차원 격자에 데이터 큐비트와 측정 큐비트를 번갈아 놓고 이웃 넷의 패리티만 반복해 잰다. 회전 표면 부호의 거리 d에는 데이터 d²개와 측정 d² − 1개가 들어, 거리 7이면 97개로 논리 큐비트 하나를 만든다.

2024년 구글은 문턱 아래 표면 부호 실험에서 거리 7 부호(큐비트 101개)의 논리 오류를 사이클당 약 0.143%로 보였고, 거리를 2 늘릴 때마다 오류가 Λ ≈ 2.14배 준다고 보고했다. 같은 비율이 이어진다고 가정하면 거리 13에서 약 0.015%, 큐비트 337개쯤이다. 쇼어 알고리즘에 필요한 오류율은 이보다 훨씬 낮아서, 실용 규모에서는 논리 큐비트 하나에 지금 실험보다 훨씬 많은 물리 큐비트가 들 것으로 본다. "큐비트 몇 개짜리 기기"라는 말을 들으면 물리 큐비트인지 논리 큐비트인지부터 확인해야 하는 이유다.

하드웨어 방식

큐비트는 두 준위를 가진 양자계라면 무엇으로든 만들 수 있다. 지금 경쟁하는 대표 방식은 넷이다. 초전도 회로는 극저온의 조셉슨 접합 회로를 인공 원자로 쓰고, 이온 트랩은 전자기장에 가둔 이온의 에너지 준위를, 중성 원자는 레이저 광학 집게로 늘어놓은 원자를, 광자 방식은 빛의 편광·경로·모드를 쓴다.

직접 확인한 이정표만 적는다. 2019년 10월 구글은 초전도 기기 Sycamore로 무작위 회로 샘플링을 시연했다(발표). 2020년 12월 Zhong 등의 연구진은 광자 기기로 가우스 보손 샘플링을 보고했다(arXiv:2012.01625). 2023년 12월 Bluvstein 등의 연구진은 중성 원자 최대 280개로 논리 큐비트 최대 48개의 회로를 돌렸다(arXiv:2312.03982). 2024년 12월 구글은 105큐비트 Willow와 문턱 아래 오류 정정 결과를 발표했다(발표). 이온 트랩은 충실도 높은 게이트로 꾸준히 앞선 결과를 내 왔지만, 여기서는 날짜를 확인한 자료가 없어 경향만 적는다.

NISQ와 '양자 우위' 논쟁

Preskill(2018)은 오류 정정 없이 큐비트 50~100개쯤을 쓰는 지금의 기기를 NISQ(Noisy Intermediate-Scale Quantum)라 불렀다. 노이즈 때문에 회로를 깊게 돌릴 수 없어서, 유용한 문제보다는 "고전 컴퓨터로 흉내 내기 어려운 무언가"를 보이는 시연이 먼저 나왔다. 이것이 양자 우위(quantum supremacy, quantum advantage) 주장이다.

논쟁의 핵심은 "고전 쪽의 최선"이 움직이는 표적이라는 점이다. 2019년 IBM의 반론과 시뮬레이션 논문처럼, 더 나은 고전 알고리즘이 나오면 격차가 크게 줄곤 한다. 또 무작위 회로 샘플링은 그 자체로 쓸모 있는 계산이 아니다. 그래서 오늘의 질문은 "고전보다 빠른가"보다 "쓸모 있는 문제에서, 오류 정정된 논리 큐비트로, 고전 최선보다 나은가"로 옮겨 가고 있다. 양자 화학·재료 시뮬레이션이 그 첫 후보로 자주 꼽히지만, 아직 그런 결과가 합의된 단계는 아니다.

직접 해 보기: Qiskit과 Cirq 시뮬레이터

실제 기기 없이도 노트북에서 회로를 시뮬레이션할 수 있다. IBM의 Qiskit은 pip install qiskit, 노이즈 모델까지 갖춘 시뮬레이터 Qiskit Aer는 pip install qiskit-aer로 설치한다. 구글의 Cirq는 python -m pip install cirq로 설치하고(설치 안내), 파동 함수와 밀도 행렬 시뮬레이터가 들어 있다. 이 노트의 벨 상태 회로를 그대로 옮겨 적고 1,000번쯤 돌려 00과 11만 반씩 나오는지 확인하는 것이 좋은 첫 연습이다.

상태 벡터를 통째로 들고 다니는 시뮬레이터는 30큐비트에 16 GiB, 50큐비트에 16 PiB가 든다. 이 벽이 곧 "양자 컴퓨터가 고전 컴퓨터로 흉내 내기 어려운 이유"를 손으로 느끼게 해 준다. 얽힘이 적은 회로는 텐서 네트워크처럼 더 영리한 방법으로 훨씬 많은 큐비트를 흉내 낼 수 있는데, 양자 우위 논쟁의 고전 쪽 반론이 대개 이런 기법에서 나온다. 노이즈 모델을 켜고 같은 회로를 돌려 보면 결과가 00·11 말고도 조금씩 새는 것을 볼 수 있다. NISQ 기기가 겪는 일이 바로 그것이다.

흔한 오해

이 노트 곳곳에서 바로잡은 오해를 모으면 이렇다. 큐비트가 0과 1을 "동시에 가진다"는 설명(비트와 큐비트 절), 얽힘으로 신호를 빛보다 빨리 보낸다는 생각(얽힘 절), 양자 컴퓨터가 NP-완전 문제를 효율적으로 푼다는 기대(그로버 절), 큐비트 수만 보면 된다는 생각(오류 정정 절의 물리·논리 큐비트)이다. 여기에 두 가지를 더한다.

• "양자 컴퓨터가 고전 컴퓨터를 대체한다": 지수적인 속도 향상이 알려진 것은 소인수분해의 주기 찾기처럼 특별한 구조가 있는 문제다. 구조 없는 탐색은 제곱근만큼만 빨라지고, 결과도 측정 한 번에 큐비트 수만큼의 비트만 꺼낼 수 있다. 양자 기기는 고전 컴퓨터가 붙어 제어하는 가속기로 보는 편이 맞다.
• "양자 암호와 양자내성 암호는 같은 말이다": 양자 키 분배(QKD)는 양자 상태를 실은 빛으로 열쇠를 나누는 물리 장치다. 전용 광섬유나 가시선 경로와 인증된 고전 통신 채널이 필요하고, 거리가 늘면 열쇠를 만드는 속도가 지수로 준다(Wikipedia의 Quantum key distribution). 양자내성 암호(PQC)는 지금의 컴퓨터에서 도는 새 수학 알고리즘으로, NIST가 2024년 8월 ML-KEM(FIPS 203), ML-DSA(FIPS 204), SLH-DSA(FIPS 205)를 표준으로 냈다(NIST PQC 프로젝트). 쇼어 알고리즘에 대비하는 소프트웨어 이야기는 암호학 노트에 있다.

핵심 자료

요지는 직접 정리한 한 줄이다. 양자 컴퓨터가 암호에 주는 영향은 암호학 노트, 복잡도 클래스 BQP는 계산 이론 노트에 있다.