양자 게이트

1. 개요[편집]

양자 게이트 Quantum Gate
정체	큐비트 상태공간 위의 유니터리 행렬
가역성	항상 가역 (역게이트 = 켤레전치)
단일 큐비트	X, Y, Z, H, S, T, Rx, Ry, Rz
두 큐비트	CNOT, CZ, SWAP, iSWAP
범용 집합	{CNOT + 임의 단일큐빗}, 이산판 {H, T, CNOT}
비싼 자원	T 게이트 (비클리퍼드)

고전 논리 게이트는 정보를 버릴 수 있다. 양자 게이트는 못 버린다. 그래서 전부 되돌릴 수 있다.

양자 게이트(quantum gate)는 큐비트 레지스터의 상태벡터에 작용하는 유니터리 행렬이다. $n$ 큐비트 상태는 $2^n$ 차원 복소벡터이고, 게이트는 그 위의 $2^n\times2^n$ 유니터리 $U$ 로서 $|\psi\rangle \mapsto U|\psi\rangle$ 를 수행한다. 유니터리 조건 $U^\dagger U=\mathbb{1}$ 이 두 가지를 동시에 보장한다 — 확률의 총합이 보존되고($\||\psi\rangle\|=1$ 유지), 연산이 항상 가역이다($U^{-1}=U^\dagger$ 이 또 하나의 유효한 게이트다).

여기서 고전 회로와의 결정적 차이가 나온다. AND 게이트는 입력 두 비트를 받아 한 비트를 내놓으며 정보를 버리고, 그래서 되돌릴 수 없다. 양자 회로에는 그런 게이트가 없다. 고전 함수를 양자 회로로 옮기려면 $|x\rangle|y\rangle \mapsto |x\rangle|y\oplus f(x)\rangle$ 처럼 입력을 남겨 두는 가역 형태로 다시 써야 하고, 그 과정에서 생기는 쓰레기 큐비트(garbage)를 되돌려 지우는 것(uncomputation)이 양자 프로그래밍의 기본 노동이다.¹

단일 큐비트 게이트가 블로흐 구 위의 회전이라는 기하학적 그림은 그쪽 문서가 담당한다. 이 문서는 게이트 집합 · 분해 · 범용성 · 합성 비용, 즉 컴파일러가 실제로 하는 일을 다룬다.

2. 단일 큐비트 게이트 도감[편집]

계산 기저 $\{|0\rangle, |1\rangle\}$ 에서 행렬로 적으면 다음과 같다.

$$X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\quad Y=\begin{pmatrix}0&-i\\i&0\end{pmatrix},\quad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},\quad H=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}$$ $$S=\begin{pmatrix}1&0\\0&i\end{pmatrix},\qquad T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}$$

파울리 셋은 에르미트이면서 유니터리라 제곱하면 항등이다($X^2=Y^2=Z^2=\mathbb{1}$). $X$ 는 비트반전, $Z$ 는 위상반전, $Y=iXZ$ 는 둘 다다. 아다마르 $H$ 는 기저를 바꾸는 게이트로 $HZH=X$ 를 만족하며, $|0\rangle$ 을 $(|0\rangle+|1\rangle)/\sqrt2$ 로 보내 중첩을 만드는 사실상 모든 양자 알고리즘의 첫 줄이다. $S=T^2$, $Z=S^2$ 라는 사다리 구조도 기억해 둘 만하다.

연속 매개변수를 갖는 회전 게이트는 파울리를 생성원으로 하는 지수사상이다.

$$R_{\hat n}(\theta)=\exp\!\left(-i\frac{\theta}{2}\,\hat n\cdot\boldsymbol\sigma\right)=\cos\frac{\theta}{2}\,\mathbb{1}-i\sin\frac{\theta}{2}\,(\hat n\cdot\boldsymbol\sigma)$$

절반 각도 $\theta/2$ 가 나오는 이유는 $\mathrm{SU}(2)$ 가 $\mathrm{SO}(3)$ 의 이중 피복이기 때문이고, 이 이야기는 블로흐 구와 사원수에 있다. 하드웨어 관점에서는 $R_z$ 가 공짜에 가깝다는 점이 중요하다. 초전도 큐비트에서 $Z$ 회전은 이후 펄스의 위상 기준을 바꾸는 것으로 구현되므로(virtual-Z) 물리 시간도 오류도 거의 들지 않는다. 그래서 실제 백엔드의 네이티브 집합은 흔히 $\{R_z(\lambda),\ \sqrt{X},\ \text{2큐비트 게이트}\}$ 같은 모양이다.

임의의 단일 큐비트 유니터리는 전역 위상을 빼면 오일러 각 셋으로 완전히 적힌다.

$$U=e^{i\alpha}\,R_z(\beta)\,R_y(\gamma)\,R_z(\delta)$$

이 ZYZ 분해가 컴파일러의 첫 번째 도구다. 자유도를 세어 보면 $\mathrm{U}(2)$ 는 실수 4개, 전역 위상 하나를 빼면 3개 — 각도 셋과 정확히 맞는다. 구현은 오일러각에서 회전행렬을 뽑는 것과 완전히 같은 대수이고, 실제로 수치적으로는 $U$ 의 성분에서 $\arctan2$ 로 각도를 읽는다. 전역 위상 $e^{i\alpha}$ 는 관측 가능한 효과가 없어 보통 버리지만, 이 게이트가 제어 게이트의 표적으로 들어가는 순간 상대 위상이 되어 관측 가능해진다. 위상을 버리고 controlled-$U$ 를 만들었다가 결과가 틀리는 사고가 여기서 나온다.

3. 두 큐비트 게이트와 얽힘 생성[편집]

단일 큐비트 게이트만 아무리 쌓아도 곱상태는 곱상태로 남는다. 얽힘을 만들려면 두 큐비트에 동시에 작용하는 게이트가 필요하다.

게이트	하는 일	관계
CNOT	제어가 1이면 표적에 X	$\mathrm{CZ}$ 의 표적을 $H$ 로 감싼 것
CZ	두 큐비트가 모두 1인 성분에 −1	제어·표적 구분이 없음(대칭)
SWAP	두 큐비트 교환	CNOT 3개
iSWAP	교환 + 위상 $i$	초전도 하드웨어의 네이티브

CNOT은 $|00\rangle,|01\rangle,|10\rangle,|11\rangle$ 기저에서 뒤쪽 두 성분을 맞바꾸는 치환행렬이다. 얽힘 생성의 국룰 회로는 두 줄뿐이다 — 첫 큐비트에 $H$, 그다음 CNOT.

$$|00\rangle \xrightarrow{\ H\otimes\mathbb{1}\ } \frac{|00\rangle+|10\rangle}{\sqrt2} \xrightarrow{\ \mathrm{CNOT}\ } \frac{|00\rangle+|11\rangle}{\sqrt2}=|\Phi^+\rangle$$

이 벨 상태의 성질은 양자 얽힘이 다룬다. 여기서 중요한 건 곱상태에서 최대 얽힘까지 게이트 두 개면 된다는 것, 그리고 역으로 CNOT을 한 번 더 걸면 얽힘이 완전히 풀린다는 것이다. 얽힘은 자원이지만 게이트 수준에서는 그냥 가역 연산의 부산물이다.

두 큐비트 유니터리의 분해에는 깔끔한 정리가 있다. 임의의 $\mathrm{SU}(4)$ 원소는 CNOT 3개와 단일 큐비트 게이트들로 정확히 구현되며, 3개가 최악의 경우 최적이다(카르탄/KAK 분해). SWAP이 CNOT 3개인 것은 이 상한이 실제로 조인다는 예시다. 반면 $n$ 큐비트 일반 유니터리는 $\Theta(4^n)$ 개의 CNOT을 요구한다 — 매개변수 개수 세기에서 곧바로 나오는 하한이고, “임의의 유니터리를 효율적으로 구현할 수 있다”는 기대는 처음부터 틀렸다는 뜻이다. 효율적으로 구현되는 것은 구조를 가진 극소수의 유니터리뿐이다.

4. 범용성 — 무엇이면 다 되는가[편집]

{CNOT + 모든 단일 큐비트 유니터리}는 범용이다. 임의의 $n$ 큐비트 유니터리를 이 집합의 유한 곱으로 정확히 쓸 수 있다. 증명의 뼈대는 세 단계다. (1) 임의 유니터리를 2준위 유니터리(두 기저 상태만 섞는 것)들의 곱으로 분해한다 — 특이값 분해 계열의 기븐스 회전 소거와 같은 논리다. (2) 각 2준위 유니터리를 그레이 부호 경로를 따라 다중제어 게이트로 옮긴다. (3) 다중제어 게이트를 보조 큐비트와 CNOT으로 분해한다.

문제는 이 집합이 연속체라는 것이다. 실제 하드웨어는 각도를 무한 정밀도로 낼 수 없고, 양자 오류 정정을 얹으면 결함허용하게 구현 가능한 게이트가 유한 개로 제한된다. 그래서 진짜로 쓰는 것은 이산 집합이다.

$$\{\,H,\ T,\ \mathrm{CNOT}\,\}$$

이 셋은 근사적 범용이다. 임의의 유니터리를 정확히 만들지는 못하지만 원하는 정밀도 $\varepsilon$ 까지 근사할 수 있다. 이유는 $HTH$ 와 $T$ 가 블로흐 구에서 서로 다른 축 둘레의 무리수 배수 회전을 만들어, 그 곱들이 $\mathrm{SU}(2)$ 안에서 조밀(dense)한 부분군을 이루기 때문이다.

여기서 솔로베이–키타예프 정리가 등장한다. 역원에 대해 닫힌 조밀 생성집합이 주어지면, 임의의 단일 큐비트 유니터리를 오차 $\varepsilon$ 이내로 근사하는 데

$$O\!\left(\log^{c}\frac1\varepsilon\right)$$

개의 게이트면 충분하고, 그 회로를 찾는 고전 알고리즘도 비슷한 다항로그 시간에 돈다. 지수 $c$ 는 분석에 따라 다른데 원 논문 계열의 보수적 값은 4에 가깝고 이후 개선으로 2 근처까지 내려왔다.² 요점은 비용이 $1/\varepsilon$ 이 아니라 $\log(1/\varepsilon)$ 의 다항식이라는 것 — 정밀도를 열 배 올리는 값이 상수 배 수준이라 실용적으로 감당된다는 뜻이다.

다만 클리퍼드+T라는 구체적 집합에서는 SK보다 훨씬 좋은 방법이 알려져 있다. 대수적 정수론을 쓰는 로스–셀린저 합성은 $z$ 회전을 오차 $\varepsilon$ 로 근사하는 데 T 게이트를 약 $3\log_2(1/\varepsilon)$ 개만 쓰며, 이는 가산상수 범위에서 최적이다. 컴파일러가 실제로 부르는 건 SK가 아니라 이쪽이다.

5. 왜 T 게이트만 비싼가 — 고트스만–크닐[편집]

$\{H, S, \mathrm{CNOT}\}$ 이 생성하는 군을 클리퍼드 군이라 부른다. 정의는 “파울리 군을 파울리 군으로 보내는 유니터리들”이다: $C P C^\dagger \in \mathcal{P}_n$. 이 성질 덕분에 상태를 벡터가 아니라 그것을 안정화하는 파울리 연산자들의 목록으로 추적할 수 있고, 게이트를 적용할 때마다 그 목록만 갱신하면 된다.

고트스만–크닐 정리: 계산 기저 준비 · 클리퍼드 게이트 · 파울리 측정만으로 이루어진 회로는 고전 컴퓨터로 다항 시간에 시뮬레이션된다. 애런슨–고트스만의 태블로 표현으로는 게이트당 $O(n^2)$, $2^n$ 짜리 상태벡터는 근처에도 안 간다. 즉 얽힘이 아무리 많아도 그것만으로는 양자 우위가 안 나온다. 벨 상태도, 수백 큐비트 GHZ 상태도 전부 클리퍼드다.

그래서 남는 자원이 비클리퍼드 게이트, 대표적으로 $T$ 다. $T$ 를 $t$ 개 섞으면 고전 시뮬레이션 비용이 $t$ 에 대해 지수적으로 오르고(안정자 랭크 기반 방법에서 대략 $2^{0.23t}$ 규모), 그 지수가 곧 양자 계산의 “진짜 어려움”의 눈금이 된다.

결함허용 층에서도 똑같은 비대칭이 나타난다. 대부분의 부호에서 클리퍼드 게이트는 횡단적(transversal)으로, 즉 물리 큐비트마다 따로 걸어서 값싸게 구현된다. 반면 $T$ 는 그렇게 안 되고 — 이건 이스트–니일 정리로 어떤 부호도 범용 게이트 집합 전체를 횡단적으로 가질 수 없다는 일반 사실이다 — 마법 상태 증류라는 별도 공장을 돌려야 한다. 결함허용 자원 산정에서 회로의 비용을 CNOT 수가 아니라 T-count와 T-depth로 재는 관행이 여기서 나왔다. 양자 오류 정정 문서가 이 층을 다룬다.

6. 회로 깊이와 하드웨어 네이티브 게이트[편집]

논리적으로 옳은 회로와 실제로 돌아가는 회로는 다른 물건이다. 결어긋남 시간 $T_2$ 안에 끝나야 하므로 깊이(depth)가 곧 예산이고, 컴파일(트랜스파일)은 대체로 다음을 한다.

• 네이티브 게이트로 재작성. 초전도 트랜스몬은 CZ·교차공명(CR)·iSWAP 계열, 이온 트랩은 묄머–쇠렌센 $XX$ 게이트, 중성원자는 리드베르크 봉쇄 CZ가 네이티브다. CNOT은 대개 이들 위에 단일 큐비트 게이트를 씌워 만든다.
• 연결성 맞추기(routing). 초전도 칩은 이웃하는 큐비트끼리만 2큐비트 게이트가 되므로, 멀리 있는 쌍을 붙이려면 SWAP을 삽입해야 한다. SWAP 하나가 CNOT 3개고 2큐비트 게이트 오류율이 단일 큐비트보다 한 자릿수 높으니, 라우팅이 오류 예산의 주범이 된다. 이온 트랩이 전연결(all-to-all)이라 이 비용이 없는 대신 게이트 속도가 느린 것이 대표적인 트레이드오프다.
• 합성과 상쇄. 이웃한 단일 큐비트 회전은 ZYZ로 합쳐 하나로 만들고, $\mathrm{CNOT}\cdot\mathrm{CNOT}=\mathbb{1}$ 같은 항등식으로 지운다. 정확한 최적화는 일반적으로 어려운 문제라 실무는 규칙 기반 재작성 + 국소 탐색이고, 작은 블록에 대해서만 정수계획법이나 SAT 기반 최적 합성을 돌린다.

컴파일 결과를 검증하는 표준은 두 유니터리가 전역 위상까지 같은지를 재는 것이다. 프로세스 충실도

$$F=\frac{\left|\operatorname{Tr}(U_{\rm ideal}^\dagger U_{\rm actual})\right|^2}{4^n}$$

가 1에서 얼마나 떨어졌는지로 본다. 절댓값을 씌우는 것이 전역 위상을 무시하는 장치다.³ 실험 쪽에서는 개별 게이트를 재는 대신 무작위 클리퍼드 열의 길이에 따른 생존확률 감쇠를 보는 무작위 벤치마킹을 쓰는데, 상태 준비·측정 오차와 게이트 오차를 분리해 준다는 점에서 실용적이다. 이 방법이 성립하는 이유가 또 클리퍼드 군의 특별함이라는 게 재미있는 지점.

7. 관련 문서[편집]

• 블로흐 구 · 양자 얽힘 · 밀도행렬
• 양자 오류 정정 · 양자 키 분배
• 결어긋남 · 개방 양자계
• 양자 회로 · 양자 알고리즘 · 초전도 큐비트
• 오일러각 · 사원수 · 회전행렬 · 리 군
• 특이값 분해 · 크로네커 곱 · 텐서 네트워크

8. Footnotes[편집]

1. 쓰레기를 안 지우면 그 큐비트가 계산 결과와 얽힌 채 남고, 간섭이 필요한 순간에 결맞음이 죽는다. 베넷의 uncomputation 트릭(계산 → 답 복사 → 역계산)은 그래서 선택이 아니라 필수다. “메모리 해제 안 하면 느려질 뿐”인 고전 프로그래밍과 달리 여기선 답이 틀린다. ↩

2. 지수 $c$ 를 정확히 인용하려는 시도는 대체로 사고로 끝난다. 원 증명의 재귀 구조에서 나오는 값과, 이후 개선된 분석 값과, 특정 게이트 집합에 특화된 값이 문헌마다 다르게 돌아다니기 때문이다. 실무에서 중요한 건 “다항로그”라는 사실이고, 클리퍼드+T를 쓴다면 애초에 SK가 아니라 로스–셀린저를 부르게 된다. ↩

3. 이 절댓값을 빼먹고 $\operatorname{Tr}(U^\dagger V)/2^n$ 의 실수부만 보다가 “완벽히 같은 회로인데 충실도가 −1이 나온다”며 밤을 새우는 것은 양자 컴파일러 구현자의 통과의례에 가깝다. 전역 위상은 물리적으로 없는데 행렬에는 남아 있다. ↩