안정자 부호

편집 역사 토론
양자역학 계산물리 수치해석 마지막 수정: 2026-09-01 04:14:26
상위 문서: 양자 오류 정정

1. 개요[편집]

안정자 부호
Stabilizer Code
정의 도구파울리 군의 아벨 부분군 S
조건−1 ∉ S, 원소끼리 전부 교환
표기[[n, k, d]] — 생성원 n−k 개
등가 언어F₂ 위의 자기직교 심플렉틱 부호
대표 부호[[5,1,3]] · 스틴 [[7,1,3]] · 쇼어 [[9,1,3]]
결정적 정리고트스만–크닐 (고전 다항시간 시뮬)

상태를 적지 말고, 그 상태를 가만두는 연산자들을 적어라. 지수 크기가 다항 크기로 접힌다.

안정자 부호(stabilizer code)는 파울리 군의 아벨 부분군 S\mathcal{S} 를 하나 고르고, S\mathcal{S} 의 모든 원소가 고윳값 +1+1 로 안정화하는 상태들의 부분공간을 부호공간으로 정의하는 양자 오류 정정 부호다. 상태를 2n2^n 개의 복소 진폭으로 기술하는 대신 그 상태를 불변으로 두는 연산자 목록으로 기술하겠다는 발상 하나가 이 형식론의 전부이고, 그 하나로 부호 설계·신드롬 해석·고전 시뮬레이션이 전부 선형대수 문제로 내려앉는다.

양자 오류 정정 문서가 “왜 오류를 고칠 수 있는가”(오류 이산화, 크닐–라플람 조건)를 다룬다면, 이 문서는 그 부호를 실제로 적고 다루는 언어를 다룬다. 오늘날 진지하게 제안되는 양자 부호는 표면 부호를 포함해 사실상 전부 안정자 부호이며, 예외는 손에 꼽는다.1

2. 파울리 군에서 시작한다[편집]

nn 큐비트 파울리 군 Pn\mathcal{P}_n 은 {1,X,Y,Z}\{\mathbb{1}, X, Y, Z\} 의 nn 겹 텐서곱에 위상 {±1,±i}\{\pm1, \pm i\} 를 붙인 집합이다. 원소 수는 4n+14^{n+1} 이지만 위상을 무시하면 4n4^n 개, 즉 F22n\mathbb{F}_2^{2n} 만큼이다. 이 군의 핵심 성질은 아무 두 원소나 잡으면 교환하거나 반교환하거나 둘 중 하나라는 것이다. 중간이 없다.

부분군 S⊆Pn\mathcal{S}\subseteq\mathcal{P}_n 이 다음 두 조건을 만족하면 안정자 군이라 부른다.

  • 아벨: 모든 원소끼리 서로 교환한다. 그래야 동시 고유상태가 존재한다.
  • −1∉S-\mathbb{1}\notin\mathcal{S}: 이게 없으면 gg 와 −g-g 가 동시에 들어가 부호공간이 {0}\{0\} 이 되어 버린다. 실무적으로는 생성원의 부호를 잘못 잡았을 때 터지는 조건이다.2

독립 생성원이 n−kn-k 개면 ∣S∣=2n−k|\mathcal{S}|=2^{n-k} 이고, 부호공간의 사영자는 생성원마다 하나씩 곱해서 얻는다.

P=∏i=1n−k1+gi2,Tr⁡P=2n2n−k=2kP=\prod_{i=1}^{n-k}\frac{\mathbb{1}+g_i}{2},\qquad \operatorname{Tr}P=\frac{2^n}{2^{n-k}}=2^{k}

즉 생성원 하나가 힐베르트 공간을 반으로 자른다. nn 개 큐비트에서 n−kn-k 번 자르면 2k2^k 차원이 남고, 그게 논리 큐비트 kk 개다. 이 산수가 [[n,k,d]][[n,k,d]] 표기의 앞 두 숫자의 전부다.

3. 신드롬이 상태를 안 죽이는 이유, 다시[편집]

측정하는 관측량이 gig_i 라는 점이 결정적이다. 부호공간의 어떤 상태 ∣ψ⟩|\psi\rangle 에 대해서도 gi∣ψ⟩=∣ψ⟩g_i|\psi\rangle=|\psi\rangle 이므로 측정 결과는 확률 1로 +1+1 이고, 사영 후에도 상태가 그대로다. 논리 정보 α,β\alpha,\beta 는 측정 통계에 아예 나타나지 않는다 — 재고 있는 것이 논리 상태가 아니라 부호공간에서 벗어났는지 여부이기 때문이다.

오류 E∈PnE\in\mathcal{P}_n 이 걸리면 각 생성원과 교환하거나 반교환한다.

gi (E∣ψ⟩)=± E gi∣ψ⟩=± E∣ψ⟩g_i\,(E|\psi\rangle) = \pm\,E\,g_i|\psi\rangle = \pm\,E|\psi\rangle

부호가 −- 면 그 생성원의 측정값이 −1-1 로 뒤집힌다. 그래서 신드롬은 오류와 생성원들의 반교환 패턴을 적은 n−kn-k 비트열이다. 여기서 세 집합의 계층이 나온다.

  • S\mathcal{S} 안의 연산자 — 부호공간에 아무 일도 안 한다. 오류로 걸려도 무해하다.
  • S\mathcal{S} 의 정규화군 N(S)N(\mathcal{S}) 에 있지만 S\mathcal{S} 에는 없는 연산자 — 신드롬이 전부 00 인데 논리 상태를 바꾼다. 논리 연산자이자 동시에 검출조차 안 되는 치명적 오류다.
  • 나머지 — 신드롬이 켜진다. 정정 대상.

논리 연산자의 군은 정확히 몫군 N(S)/SN(\mathcal{S})/\mathcal{S} 이고, 거리 dd 는 N(S)∖SN(\mathcal{S})\setminus\mathcal{S} 원소 중 최소 무게(항등원이 아닌 자리의 개수)로 정의된다. 논리 연산자를 “몫”으로 잡는 이유는, 안정자를 곱해도 같은 논리 연산이기 때문이다 — 논리 XLX_L 의 표현은 하나가 아니라 2n−k2^{n-k} 개 있고, 하드웨어에서는 그중 가장 짧고 가장 편한 경로를 골라 쓴다. 표면 부호에서 논리 연산자를 격자 위에서 이리저리 변형해도 되는 것이 이 몫 구조의 직접적 결과다.

4. 검사행렬 — 양자 부호가 고전 부호가 되는 통로[편집]

위상을 무시하면 파울리 XaZbX^{\mathbf a}Z^{\mathbf b} 는 F2\mathbb{F}_2 위의 2n2n 비트 벡터 (a ∣ b)(\mathbf a\,|\,\mathbf b) 다. 두 연산자의 교환 관계는 이 벡터들의 심플렉틱 내적 하나로 결정된다.

⟨(a∣b), (a′∣b′)⟩s=a⋅b′+a′⋅b(mod2)\langle (\mathbf a|\mathbf b),\,(\mathbf a'|\mathbf b')\rangle_s = \mathbf a\cdot\mathbf b' + \mathbf a'\cdot\mathbf b \pmod 2

00 이면 교환, 11 이면 반교환이다. 생성원들을 행으로 쌓아 검사행렬 H=(HX ∣ HZ)H=(H_X\,|\,H_Z) 를 만들면 “아벨”이라는 조건이 통째로 한 줄의 행렬 등식이 된다.

HXHZT+HZHXT=0H_X H_Z^{\mathsf T} + H_Z H_X^{\mathsf T} = 0

이게 이 문서에서 가장 실용적인 식이다. 양자 부호를 설계하는 일이 F2\mathbb{F}_2 위에서 이 자기직교 조건을 만족하는 행렬을 찾는 순수 선형대수 문제로 환원되고, 신드롬 계산은 F2\mathbb{F}_2 행렬-벡터 곱, 논리 연산자 찾기는 영공간 계산이다. 고전 부호 이론의 도구가 통째로 건너오는 다리이며, 유한체 위 선형대수 라이브러리를 그대로 쓸 수 있다는 뜻이기도 하다. 안정자 부호를 ”F4\mathbb{F}_4 위의 가법 부호”로 보는 관점(칼더뱅크–레인스–쇼어–슬론)도 같은 통로에서 나온다.

5. CSS 부호 — 고전 부호 두 개를 포개기[편집]

가장 다루기 쉬운 하위 계열은 HXH_X 와 HZH_Z 를 아예 분리한 것이다. 즉 생성원이 순수 XX 형과 순수 ZZ 형으로만 이루어지면 자기직교 조건이

HXHZT=0H_X H_Z^{\mathsf T}=0

으로 간단해진다. 이런 부호를 CSS 부호(Calderbank–Shor–Steane)라 부른다. 고전 선형 부호 C2⊂C1C_2\subset C_1 을 잡아 ZZ 검사는 C1C_1 의 패리티 검사에서, XX 검사는 C2⊥C_2^\perp 의 패리티 검사에서 가져오면 [[n, k1−k2]][[n,\,k_1-k_2]] 부호가 나오고, 논리 상태는 잉여류의 균등 중첩이다.

∣x+C2⟩=1∣C2∣∑y∈C2∣x+y⟩,x∈C1|x + C_2\rangle = \frac{1}{\sqrt{|C_2|}}\sum_{y\in C_2}|x+y\rangle,\qquad x\in C_1

CSS의 실용적 의미는 XX 오류와 ZZ 오류를 완전히 분리해 각각 고전 디코더로 처리할 수 있다는 것이다. 대가는 YY 오류(XX 와 ZZ 가 같은 자리에 동시에)의 상관관계를 버린다는 점이고, 그래서 탈분극 잡음에서 CSS 디코더는 원리적으로 손해를 본다.3 그럼에도 거의 모든 실용 부호가 CSS인 이유는 횡단 CNOT이 공짜로 나오고 신드롬 추출 회로가 단순해지기 때문이다.

스틴 부호가 교과서적 예시다. [7,4,3][7,4,3] 해밍 부호는 자기 쌍대를 포함하므로(C⊥⊂CC^\perp\subset C) 같은 패리티 검사행렬을 XX 쪽과 ZZ 쪽에 그대로 두 번 쓰면 된다.

H=(000111101100111010101)H=\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{pmatrix}

XX 형 3개 + ZZ 형 3개 = 생성원 6개, k=7−6=1k=7-6=1, 거리 3. 즉 [[7,1,3]][[7,1,3]] 이다.

6. 부호 동물원과 한계[편집]

부호계열특징
[[5,1,3]][[5,1,3]]비CSS단일 오류 정정 최소 크기, 양자 해밍 한계를 포화(완전 부호)
[[7,1,3]][[7,1,3]] 스틴CSS클리퍼드 전체가 횡단적
[[9,1,3]][[9,1,3]] 쇼어CSS, 축퇴최초의 부호, 연접(concatenation)의 원형
[[4,2,2]][[4,2,2]]CSS, 검출 전용d=2d=2 — 정정은 못 하고 검출만, NISQ 실험 단골
토릭 / 표면 부호CSS, 위상적검사 무게 4, 국소성

[[5,1,3]][[5,1,3]] 의 생성원은 하나를 순환이동한 네 개로 예쁘게 적힌다.

XZZXI,IXZZX,XIXZZ,ZXIXZXZZXI,\quad IXZZX,\quad XIXZZ,\quad ZXIXZ

크기의 하한은 두 부등식이 잡는다. 양자 싱글턴 한계 n−k≥2(d−1)n-k\ge 2(d-1) 는 모든 안정자 부호에 성립하고 [[5,1,3]][[5,1,3]] 이 이를 포화한다(4=44=4). 양자 해밍 한계는 축퇴가 없는 부호에만 성립하는데, t=⌊(d−1)/2⌋t=\lfloor(d-1)/2\rfloor 에 대해

∑j=0t3j(nj)≤2 n−k\sum_{j=0}^{t}3^{j}\binom{n}{j}\le 2^{\,n-k}

이고 [[5,1,3]][[5,1,3]] 에서 1+3⋅5=16=241+3\cdot5=16=2^4 로 등호가 성립한다. 그래서 완전 부호다.

7. 축퇴 — 양자에만 있는 공짜 점심[편집]

고전 부호에서 서로 다른 오류는 서로 다른 곳으로 부호어를 보낸다. 양자에서는 서로 다른 오류가 부호공간 위에서 완전히 같은 작용을 할 수 있다. 두 오류의 곱이 안정자 안에 들어가 버리는 경우다. 이런 부호를 축퇴(degenerate)되었다고 한다.

쇼어 [[9,1,3]][[9,1,3]] 이 대표적이다. 한 블록 안의 Z1Z_1, Z2Z_2, Z3Z_3 는 세 개 다 논리 상태에 똑같은 짓을 한다 — 실제로 Z1Z2Z_1Z_2 가 안정자다. 디코더 입장에서는 어느 것이 진짜 일어났는지 구별할 필요가 없다. 아무거나 골라 되돌리면 맞는다.

이게 왜 중요하냐면, 축퇴 부호는 “구별해야 할 오류의 가짓수”가 줄어들어 해밍 한계 같은 셈이 부과하는 벽을 넘어갈 수 있기 때문이다. 대신 디코딩 문제의 성격이 바뀐다. 최적 디코딩은 개별 오류의 확률이 아니라 오류의 동치류(coset) 전체의 확률 합을 최대화해야 하는데, 이 정확한 계산은 일반적으로 어렵다. 실무 디코더 대부분이 “가장 그럴듯한 개별 오류”를 찾는 최소무게 방식을 쓰는 것은 편의이지 최적성이 아니며, 축퇴가 심한 부호(양자 LDPC 계열)에서 믿음 전파 디코더가 고전 LDPC만큼 잘 안 도는 원인 중 하나가 이 동치류 축퇴다.

8. 고트스만–크닐 — 그리고 이 바닥의 계산 노동[편집]

안정자 형식론의 진짜 위력은 부호 설계가 아니라 시뮬레이션에서 나온다. 상태를 안정자 생성원 nn 개의 목록으로 적고, 클리퍼드 게이트를 걸 때마다 그 목록을 켤레변환으로 갱신한다. CXC†CXC^\dagger 가 다시 파울리이므로 목록은 목록으로 남는다.

H:  X↦Z, Z↦XS:  X↦Y, Z↦ZCNOT:  X1↦X1X2, Z2↦Z1Z2H:\; X\mapsto Z,\ Z\mapsto X \qquad S:\; X\mapsto Y,\ Z\mapsto Z \qquad \mathrm{CNOT}:\; X_1\mapsto X_1X_2,\ Z_2\mapsto Z_1Z_2

고트스만–크닐 정리는 여기서 나온다. 계산 기저 준비 · 클리퍼드 게이트 · 파울리 측정만으로 된 회로는 고전 컴퓨터로 다항 시간에 정확히 시뮬레이션된다. 애런슨–고트스만의 태블로 표현에서는 2n×(2n+1)2n\times(2n+1) 비트만 들고 다니며 게이트당 O(n)O(n), 측정당 O(n2)O(n^2) 로 돈다.4 2n2^n 짜리 상태벡터는 근처에도 안 간다.

여기서 나오는 문장이 이 분야를 관통한다 — 얽힘이 아무리 많아도 그것만으로는 양자 우위가 아니다. GHZ든 벨 상태든 표면 부호의 거대한 얽힘이든 전부 안정자 상태다. 우위를 만드는 자원은 비클리퍼드성이고, 그 얘기는 양자 게이트 문서에 있다.

수치해석 하는 사람 입장에서 더 재미있는 함의는 이거다. QEC 연구의 계산 노동 대부분이 고전 계산이다. 문턱값을 재는 것은 안정자 시뮬레이터로 10710^7 회 규모의 몬테카를로 방법 표본을 돌리는 일이고(Stim 같은 도구가 초당 수백만 샷을 낸다), 디코딩은 그래프 매칭이고, 부호 탐색은 F2\mathbb{F}_2 선형대수 + 조합 최적화다. 양자 컴퓨터를 설계하는 코드의 절대다수는 비트 연산으로 짜인 고전 코드다.

9. 관련 문서[편집]

10. Footnotes[편집]

  1. 비안정자 부호가 아예 없지는 않다. 연속변수 계열의 GKP 부호나 일부 손으로 깎은 ((5,6,2))((5,6,2)) 급 부호처럼 안정자 틀 밖에서 더 좋은 파라미터를 내는 예가 있다. 다만 “생성원 목록만 적으면 부호가 정의된다”는 편의를 포기하는 값이 워낙 비싸서, 하드웨어 로드맵에 올라가는 부호는 사실상 전부 안정자 부호다. ↩

  2. −1∉S-\mathbb{1}\notin\mathcal{S} 조건을 실수로 깨는 가장 흔한 경로는 생성원의 부호(±)를 손으로 적다가 하나 빠뜨리는 것이다. 결과는 조용하다 — 사영자가 0이 되고, 시뮬레이터는 “부호공간 차원 0”이라는 참말을 뱉으며 정상 종료한다. 디버깅할 때 제일 먼저 Tr⁡P\operatorname{Tr}P 를 세어 보자. ↩

  3. YY 오류 하나를 CSS 디코더는 ”XX 오류 하나 + ZZ 오류 하나”로 따로 세고, 그 둘이 같은 큐비트에서 났다는 정보를 버린다. 이 상관을 살리면 탈분극 잡음의 문턱이 눈에 띄게 올라가서, 상관 매칭(correlated matching)이나 F4\mathbb{F}_4 위의 디코더가 이걸 되찾으려고 나온 물건들이다. 공짜로 얻는 단순함의 청구서는 늘 문턱값 소수점 몇 자리로 온다. ↩

  4. 태블로 시뮬레이터의 이름 CHP는 CNOT–Hadamard–Phase의 머리글자다. 클리퍼드 군 생성에 이 셋이면 충분하다는 사실을 그대로 프로그램 이름으로 삼았다. 이름 짓는 데 5초 걸렸을 것 같은 작명이지만, 20년 넘게 이 바닥의 표준 벤치마크로 남아 있다. ↩