양자 오류 정정

1. 개요[편집]

양자 오류 정정 Quantum Error Correction (QEC)
넘어야 할 벽	복제 불가 · 연속 오류 · 측정 붕괴
핵심 트릭	오류 이산화 + 신드롬 측정
최초의 부호	쇼어 9큐빗 (1995)
표기	[[n, k, d]] — 물리 n, 논리 k, 거리 d
현재 주류	표면 부호 (surface code)
회로 수준 문턱	대략 0.5~1 % (잡음 모형 의존)

고전 오류 정정은 “세 번 적어 두고 다수결”이면 끝난다. 양자에서는 그 첫 줄부터 금지되어 있다.

양자 오류 정정(quantum error correction)은 여러 개의 물리 큐비트에 하나의 논리 큐비트를 얽힌 형태로 분산 저장하고, 논리 상태를 읽지 않은 채 오류의 흔적만 측정해 되돌리는 기법이다. 결어긋남과 게이트 오류가 물리 큐비트를 갉아먹는 속도가 유용한 알고리즘의 길이보다 압도적으로 빠르기 때문에, 대규모 양자 계산은 예외 없이 이 층 위에서만 존재할 수 있다.

문제는 고전 부호를 그대로 옮겨 올 수 없다는 것이고, 막는 벽이 정확히 셋이다.

• 복제 불가 정리. 미지의 상태 $|\psi\rangle$ 를 복사하는 유니터리는 존재하지 않는다. 선형성만으로 증명되는 아주 싼 정리인데, 덕분에 “세 벌 복사” 반복 부호가 원천 봉쇄된다.
• 연속 오류. 고전 비트의 오류는 뒤집힘 하나뿐이지만, 큐비트는 블로흐 구 위에서 $\epsilon$ 만큼 아주 조금 기울어질 수 있다. 오류의 집합이 연속체라 유한 개의 경우로 분류할 수 없어 보인다.
• 측정 붕괴. 무엇이 잘못됐는지 알려면 재야 하는데, 재는 순간 중첩이 붕괴해서 지키려던 정보가 파괴된다.

세 벽을 한꺼번에 무너뜨리는 것이 아래 두 아이디어다. 하나는 오류를 파울리 기저로 펴서 이산화하는 것, 다른 하나는 논리 정보와 교환하는 관측량만 골라 재는 것이다.

2. 오류 이산화 — 연속이 이산이 되는 마법[편집]

큐비트 하나에 임의의 오류가 걸렸다고 하자. 개방 양자계 언어로 그것은 크라우스 연산자 $E_k$ 들의 작용이고, $2\times2$ 행렬은 항상 파울리 넷의 선형결합이므로

$$E_k = \alpha_k \mathbb{1} + \beta_k X + \gamma_k Y + \delta_k Z$$

로 쓸 수 있다. 즉 부호가 $X$, $Z$, 그리고 그 곱 $Y$ 만 고칠 수 있으면 임의의 단일 큐비트 오류를 고친다. 신드롬을 측정하는 순간 이 중첩이 네 항 중 하나로 사영되고, 그다음은 이산적인 정정 문제다. 회전각이 $\epsilon$ 인 미세한 오류는 확률 $O(\epsilon^2)$ 로 “완전한 $X$ 오류”로 사영되고 나머지 확률로 “오류 없음”으로 사영된다 — 조금 틀린 상태를 조금 고치는 것이 아니라, 가끔 완전히 틀리고 그때 완전히 고치는 것이다. QEC 입문에서 가장 반직관적이면서 가장 중요한 문장이 이거다.

정정 가능성의 정확한 조건은 크닐–라플람 조건이다. 부호공간 사영자를 $P$, 고치려는 오류 집합을 $\{E_a\}$ 라 할 때

$$P\,E_a^\dagger E_b\,P = c_{ab}\,P$$

를 만족하는 에르미트 행렬 $c_{ab}$ 가 존재하면 그 집합은 정정 가능하다. 해석은 두 갈래다. $a=b$ 대각 성분은 “오류가 부호어의 정체에 대한 정보를 새게 하지 않는다”(모든 부호어에서 같은 확률로 일어난다)는 뜻이고, $a\neq b$ 비대각 성분은 “서로 다른 오류는 서로 구별 가능한 곳으로 상태를 보낸다”는 뜻이다. 정보가 새지 않는다는 조건과 오류를 식별할 수 있다는 조건이 한 식에 들어 있는 것이 이 정리의 아름다움이다.

3. 3큐빗 비트플립 부호 — 신드롬이 상태를 안 죽이는 이유[편집]

가장 작은 예제. 논리 상태를 이렇게 인코딩한다.

$$|0_L\rangle = |000\rangle,\qquad |1_L\rangle=|111\rangle,\qquad \alpha|0_L\rangle+\beta|1_L\rangle = \alpha|000\rangle+\beta|111\rangle$$

복사가 아니다. $(\alpha|0\rangle+\beta|1\rangle)^{\otimes3}$ 과는 전혀 다른, 세 큐비트가 얽힌 GHZ 꼴 상태다. 복제 불가 정리에 걸리지 않는 이유가 이것이다.

이제 어느 큐비트가 뒤집혔는지 알아내야 하는데, 개별 큐비트를 재면 안 된다. 대신 패리티만 잰다.

$$S_1 = Z_1Z_2,\qquad S_2=Z_2Z_3$$

이 두 관측량은 $|000\rangle$ 과 $|111\rangle$ 을 모두 고윳값 $+1$ 로 안정화한다. 따라서 부호공간 안의 어떤 중첩에 대해서도 측정 결과가 확정적으로 $+1$ 이고, 측정이 $\alpha,\beta$ 를 건드리지 않는다. 이것이 요점 — 재는 관측량을 논리 연산자($X_L=X_1X_2X_3$, $Z_L=Z_1Z_2Z_3$)와 교환하도록 고르면 측정이 논리 정보를 보지 못한다.

오류가 걸리면 반교환 관계가 부호를 뒤집는다.

오류	Z₁Z₂	Z₂Z₃	판정
없음	+1	+1	그대로 둔다
X₁	−1	+1	1번에 X
X₂	−1	−1	2번에 X
X₃	+1	−1	3번에 X

두 비트의 신드롬이 네 가지 경우를 정확히 구분한다. 물론 이 부호는 위상 오류 $Z$ 에 완전히 무력하다 — $Z_1$ 은 두 안정자와 모두 교환하므로 신드롬이 $(+1,+1)$ 로 나오고, 그러는 사이 논리 상태는 $\alpha|0_L\rangle-\beta|1_L\rangle$ 로 망가진다. 반쪽짜리 부호다.

4. 쇼어 9큐빗 부호와 안정자 형식론[편집]

피터 쇼어(1995)의 해법은 부호를 겹쳐 쌓는 것이다. 아다마르로 기저를 돌리면 $Z$ 오류가 $X$ 오류로 보이므로, 같은 3큐빗 반복 부호가 위상 오류 부호로 변신한다. 바깥층에 위상 부호를, 각 블록 안에 비트 부호를 넣으면

$$|0_L\rangle=\frac{1}{2\sqrt2}\big(|000\rangle+|111\rangle\big)^{\otimes 3},\qquad |1_L\rangle=\frac{1}{2\sqrt2}\big(|000\rangle-|111\rangle\big)^{\otimes 3}$$

가 되고, 이것이 임의의 단일 큐비트 오류를 고치는 최초의 부호 $[[9,1,3]]$ 이다. 이후 스틴의 $[[7,1,3]]$(고전 해밍 부호에서 유도되는 CSS 부호)과 다섯 큐비트로 같은 일을 하는 $[[5,1,3]]$ 완전 부호가 나왔다. 다섯이 하한이라는 것도 증명되어 있다.

이 예제들을 하나로 묶는 언어가 안정자 형식론이다. 파울리 군의 아벨 부분군 $\mathcal{S}$ 를 잡고(단, $-\mathbb{1}\notin\mathcal{S}$), 그 모든 원소가 $+1$ 로 안정화하는 상태들의 부분공간을 부호공간으로 정의한다. $n$ 큐비트에서 독립 생성원이 $n-k$ 개면 부호공간의 차원이 $2^k$, 즉 논리 큐비트 $k$ 개다.

• $[[n,k,d]]$ 표기. $n$ 물리, $k$ 논리, $d$ 는 거리 — 안정자와 모두 교환하면서 안정자에 속하지는 않는(즉 논리 상태를 실제로 바꾸는) 최소 무게 파울리 연산자의 무게다. $t=\lfloor (d-1)/2\rfloor$ 개까지의 오류를 고친다.
• 신드롬 = 반교환 패턴. 오류 $E$ 에 대해 각 생성원과의 교환/반교환이 신드롬 비트가 된다. 오류 정정은 신드롬 비트열로부터 가장 그럴듯한 오류를 추정하는 고전 디코딩 문제로 환원된다.
• 이중선형 대수. 파울리 연산자를 $\mathbb{F}_2$ 위의 $2n$ 비트 벡터로 적으면 교환 관계가 심플렉틱 내적이 되고, 안정자 부호 전체가 유한체 위의 자기직교 선형 부호와 같은 대상이 된다. 고전 부호 이론의 도구가 통째로 넘어오는 통로다.

여기서 양자 게이트 문서의 클리퍼드 군이 다시 등장한다. 클리퍼드 게이트가 안정자를 안정자로 보내기 때문에 부호를 유지한 채 논리 연산을 하기가 쉽고, 반대로 $T$ 게이트는 그렇지 않아 마법 상태 증류라는 별도 공장이 필요하다. 이스트–니일 정리에 따르면 어떤 부호도 범용 집합 전체를 횡단적으로 가질 수 없어서, 이 비대칭은 우회가 아니라 원리적 제약이다.

5. 표면 부호 — 실제로 만들 물건[편집]

표면 부호는 2차원 격자 위에 물리 큐비트를 깔고 국소적인 검사만 쓴다. 데이터 큐비트를 변 위에 두면 안정자는 두 종류다.

$$A_v=\prod_{e \ni v} X_e \quad(\text{버텍스/스타 검사}),\qquad B_p=\prod_{e\in\partial p} Z_e \quad(\text{플라켓 검사})$$

각 검사가 이웃한 네 개의 데이터 큐비트에만 닿고, 보조 큐비트 하나와 CNOT 네 번으로 측정된다. 모든 상호작용이 최근접 이웃이라는 점이 초전도 칩 같은 평면 하드웨어에 이 부호가 채택된 결정적 이유다. 거리 $d$ 논리 큐비트 하나에 데이터 큐비트가 $O(d^2)$ 개 필요하고(회전판 기준 정확히 $d^2$, 신드롬 보조까지 세면 대략 그 두 배)¹, 논리 연산자는 격자를 가로지르는 길이 $d$ 짜리 사슬이다 — 논리 오류가 나려면 국소 오류가 격자를 관통하는 길이로 줄지어 일어나야 한다는 것이 이 부호의 강건함의 정체다.

디코딩은 예쁜 그래프 문제가 된다. $X$ 오류 사슬의 양 끝에서만 플라켓 검사가 $-1$ 로 켜지므로, 신드롬은 격자 위에 흩어진 점들의 집합으로 나타난다. 이 점들을 짝지어 잇는 사슬 중 총 길이가 최소인 것을 찾으면 가장 그럴듯한 오류 추정이 되고, 이것이 최소 가중 완전 매칭(MWPM) — 에드먼즈의 블로섬 알고리즘이 다항 시간에 푸는 바로 그 문제다.² 실시간 디코딩에서는 이것도 느려서 유니온–파인드 디코더(거의 선형 시간), 믿음 전파 + 정렬 통계 디코딩, 신경망 디코더 등이 경쟁한다. 디코더 지연이 신드롬 생성 속도를 못 따라가면 백로그가 지수적으로 밀린다는 것이 이 바닥의 하드 제약이라, 정확도보다 처리량이 먼저인 경우가 많다.

측정 자체도 틀린다는 점을 잊으면 안 된다. 그래서 실제로는 신드롬을 $d$ 회 반복 측정해 시간 축을 하나 더한 3차원 매칭 그래프를 만든다. 공간 2차원 + 시간 1차원의 이 구조는 3차원 이징 모형의 무작위 결합 판본과 대응되고, 문턱값이 그 통계역학 모형의 상전이점으로 번역된다는 것이 데니스·키타예프·란달·프레스킬(2002)의 유명한 결과다.

6. 문턱값 정리 — 왜 이게 통하는가[편집]

거리 $d$ 부호의 논리 오류율은 물리 오류율 $p$ 에 대해 대략

$$p_L \;\approx\; A\left(\frac{p}{p_{\rm th}}\right)^{\lfloor (d+1)/2\rfloor}$$

로 간다. 지수가 $\lfloor(d+1)/2\rfloor$ 인 이유는 논리 오류를 내려면 최소 그만큼의 물리 오류가 동시에 일어나야 하기 때문이다. 이 식이 말하는 그림은 명확하다.

• $p > p_{\rm th}$ 이면 괄호 안이 1보다 커서 거리를 키울수록 논리 오류율이 오른다. 큐비트를 더 넣을수록 나빠지는 구간이다.
• $p < p_{\rm th}$ 이면 괄호 안이 1보다 작아 거리를 키우면 논리 오류율이 지수적으로 내려간다. 자원은 $d^2$ 로 다항적으로 늘 뿐인데 오류는 지수적으로 준다.

즉 $p=p_{\rm th}$ 에서 서로 다른 $d$ 의 곡선들이 한 점에서 교차하고, 그 교차점이 문턱이다. 실험에서 문턱을 확인하는 표준 그림이 정확히 이 교차이며, 거리를 $d$ 에서 $d+2$ 로 늘렸을 때 논리 오류율이 줄어드는 비 $\Lambda = p_L(d)/p_L(d+2)$ 가 1보다 크면 “문턱 아래”에 들어왔다고 말한다. 구글 연구진이 표면 부호를 $d=3\to5$, 이어서 $d=7$ 까지 키우며 $\Lambda>1$ 을 보고한 것이 이 분야가 원리 검증을 넘어선 지점으로 꼽힌다.

문턱값 정리(아로노프–벤오르, 키타예프, 크닐–라플람–주렉 등, 1996~97)는 이것을 정리로 만든다. 물리 오류율이 상수 문턱 $p_{\rm th}$ 아래이고 오류가 충분히 국소적·비상관이면, 길이 $L$ 의 임의의 양자 회로를 오류 $\varepsilon$ 이내로 실행하는 데 $O(L\,\mathrm{polylog}(L/\varepsilon))$ 의 오버헤드면 충분하다. 결함허용(fault tolerance)이라는 말은 여기에 붙는 추가 요구를 가리킨다 — 정정 회로 자체도 틀리므로, 하나의 오류가 블록 안에서 두 개 이상으로 번지지 않도록 게이트와 신드롬 추출 회로를 설계해야 한다. 횡단 게이트가 사랑받는 이유가 이거다.

문턱값의 숫자는 잡음 모형에 따라 크게 달라진다. 측정이 완벽하고 $X$·$Z$ 오류가 독립인 이상화된 모형에서 표면 부호의 문턱은 10% 대까지 올라가지만, 신드롬 추출 회로의 모든 게이트와 측정에 오류를 넣은 회로 수준 잡음에서는 대략 0.5~1% 수준으로 내려앉는다. 논문에서 문턱 숫자를 인용할 때 잡음 모형을 같이 적지 않으면 아무 의미가 없는 이유다.³

7. 자원 비용이라는 청구서[편집]

문턱을 넘었다고 끝이 아니다. 알고리즘이 요구하는 논리 오류율이 $10^{-10}$ 급이라면 물리 오류율 $10^{-3}$ 에서 거리 $d\sim 20{\sim}30$ 이 필요하고, 논리 큐비트 하나에 물리 큐비트 1000개 안팎이 붙는다. 여기에 $T$ 게이트를 공급하는 마법 상태 증류 공장이 별도로 큰 면적을 먹는다. 암호 해독급 알고리즘의 자원 산정 논문들이 물리 큐비트 수백만 개를 이야기하는 이유가 이 곱셈이다.

그래서 최근의 연구는 두 방향으로 간다. 하나는 부호율을 올리는 것 — 표면 부호는 $k/n \to 0$ 이라 근본적으로 낭비가 심하고, 상수 부호율과 선형 거리를 동시에 갖는 양자 LDPC 부호(좋은 부호의 존재는 2021~22년에 구성적으로 해결됐다)가 대안이다. 대신 검사가 국소적이지 않아 하드웨어 연결성 요구가 커진다는 청구서가 붙는다. 다른 하나는 하드웨어에서 오류를 편향시키는 것 — 고양이 큐비트처럼 비트플립을 지수적으로 억제해 사실상 위상 오류만 남기면, 그 비대칭을 이용해 훨씬 적은 자원으로 같은 논리 오류율에 도달할 수 있다.

수치해석 하는 입장에서 재미있는 점은, 이 분야의 실제 계산 노동 대부분이 양자적이지 않다는 것이다. 문턱을 재는 것은 몬테카를로 방법으로 안정자 회로를 돌리는 일이고(고트스만–크닐 덕분에 고전 컴퓨터로 가능하다), 디코딩은 그래프 매칭이고, 자원 산정은 조합 최적화다. 양자 컴퓨터를 만드는 일의 절반은 고전 알고리즘 문제다.

8. 관련 문서[편집]

• 양자 게이트 · 양자 얽힘 · 블로흐 구
• 결어긋남 · 개방 양자계 · 밀도행렬
• 양자 키 분배 · 숨은 변수 이론
• 안정자 부호 · 표면 부호 · 초전도 큐비트
• 블로섬 알고리즘 · 이분 매칭 · 믿음 전파
• 유한체 · 이징 모형 · 몬테카를로 방법

9. Footnotes[편집]

1. “회전 표면 부호(rotated surface code)“라는 이름으로 도는 판본이 데이터 큐비트 $d^2$ 개짜리다. 격자를 45° 돌려 같은 거리를 더 적은 큐비트로 내는 것인데, 논문마다 회전판을 쓰는지 아닌지를 안 밝히고 큐비트 수만 적는 바람에 같은 $d$ 에 대해 숫자가 두 배 차이 나는 표가 흔하게 돌아다닌다. ↩

2. 1965년에 조합최적화 하려고 만든 알고리즘이 60년 뒤 초전도 냉동기 옆에서 실시간으로 돌게 될 줄은 에드먼즈도 몰랐을 것이다. 참고로 매칭 그래프의 간선 가중치는 보통 $-\log$ 확률로 잡는다 — 최소 가중 매칭이 곧 최대 우도 오류 추정이 되도록. ↩

3. “표면 부호 문턱이 1%“와 “표면 부호 문턱이 11%“가 둘 다 맞는 문장이라는 사실이 이 분야 발표 자리에서 가장 자주 터지는 오해다. 앞은 회로 수준, 뒤는 측정이 완벽한 현상론적 모형이다. 숫자만 들고 와서 하드웨어 목표치를 잡으면 한 자릿수를 통째로 낙관하게 된다. ↩