양자 회로

양자역학 계산물리 소프트웨어 마지막 수정: 2026-09-01 04:22:47

1. 개요[편집]

양자 회로 Quantum Circuit
모형	게이트 모형 — 준비 → 유니터리 열 → 측정
도식	가로선 = 큐비트, 왼쪽 → 오른쪽 = 시간
금지 사항	선 분기(팬아웃) · 되먹임 고리 없음
비용 척도	깊이 · 폭 · 2큐비트 게이트 수 · T-count
고전 시뮬	상태벡터 · 밀도행렬 · 텐서망 · 안정자
메모리 벽	40큐비트 상태벡터 = 16 TiB

회로도 한 장이 곧 프로그램이다. 반복문도 조건문도 없고, 선을 복사할 수도 없다. 이 빈약한 문법으로 인수분해를 한다.

양자 회로(quantum circuit)는 큐비트 레지스터를 기저 상태로 준비하고, 시간 순서대로 배열된 유한 개의 양자 게이트를 걸고, 마지막에 측정해 고전 비트를 읽는 계산 모형이다. 고전 논리 회로의 직접적 유비이면서 세 가지 결정적 제약이 붙는다 — 선은 갈라질 수 없고(복제 불가 정리), 고리를 만들 수 없으며(유니터리는 되돌릴 수 있어야 한다), 중간에 정보를 버릴 수 없다.

게이트 하나하나의 정체와 분해는 양자 게이트가 담당한다. 이 문서는 그 위층 — 회로를 계산 모형으로 보는 관점, 비용 척도, 컴파일 파이프라인, 그리고 회로를 고전 컴퓨터로 시뮬레이션하는 방법을 다룬다. 마지막 항목이 특히 중요한데, 지금 지구에서 돌아가는 양자 회로의 절대다수는 고전 컴퓨터 위에서 돌기 때문이다.

2. 도식 규약[편집]

가로선 하나가 큐비트 하나이고, 시간은 왼쪽에서 오른쪽으로 흐른다. 상자는 단일 큐비트 게이트, 검은 점–십자 쌍은 CNOT(점이 제어), 계기판 그림은 측정이다. 이중선은 측정 이후의 고전 비트로, 조건부 게이트의 제어에 쓰인다.

|0> ──[H]──●───────────  얽힘 생성 + 측정
           │
|0> ───────⊕──[M]══╤═══
                   ║
|ψ> ──────────────[X]───  고전 제어(피드포워드)

읽을 때 자주 틀리는 지점 셋.

도식의 왼쪽이 행렬 곱의 오른쪽이다. 회로가 $A$ 다음 $B$ 면 유니터리는 $BA$ 다. 부호가 뒤집힌 결과를 얻고 세 시간 헤매는 통과의례가 여기 있다.¹
세로로 겹치지 않는 게이트는 같은 층(layer)이다. 회로는 사실 게이트를 노드로 하는 방향 비순환 그래프(DAG)이고, 도식의 가로 위치는 그 DAG의 한 위상 정렬일 뿐이다. 컴파일러는 이 DAG 위에서 논다.
측정은 마지막에만 있는 게 아니다. 중간 측정 + 고전 피드포워드는 오류 정정과 게이트 순간이동의 필수 요소다.

다만 이론적으로는 측정 연기 원리(deferred measurement)가 성립한다. 중간 측정과 그 결과로 제어되는 고전 조건부 게이트는, 측정을 맨 뒤로 미루고 조건부 게이트를 양자 제어 게이트로 바꾸면 언제나 같은 회로가 된다. 그래서 “회로 = 유니터리 하나 + 마지막 측정”이라는 단순한 그림으로 이론을 전개해도 일반성을 잃지 않는다. 실무에서 이 정리를 그대로 쓰면 안 되는 이유는 명확하다 — 미루는 대가로 보조 큐비트가 늘고, 실제 하드웨어에서 큐비트는 시간보다 비싸다.

3. 계산 모형으로서[편집]

회로 하나는 고정된 입력 크기에만 대응한다. 알고리즘은 회로 족 $\{C_n\}$ 이고, 여기에 균일성(uniformity) 조건이 붙는다 — $n$ 을 받아 $C_n$ 의 설계도를 뱉는 고전 다항시간 알고리즘이 존재해야 한다. 이 조건이 없으면 회로 족은 정보를 무한히 숨겨 놓고 결정 불가능한 문제까지 “풀어” 버린다. 비균일 모형이 계산 복잡도에서 조심스럽게 다뤄지는 이유다.

이 모형은 양자 튜링 기계와 다항 시간 안에서 동등하고, 그렇게 정의된 클래스가 BQP다. 회로 모형이 표준이 된 것은 동등성 때문이 아니라 쓰기 쉽고 하드웨어에 그대로 대응되기 때문이다. 측정 기반 계산(클러스터 상태), 단열 계산(양자 어닐링 계열), 위상적 계산도 다항 시간 안에서 서로 동등하지만, 사람이 알고리즘을 짤 때 손에 잡히는 건 회로다.

4. 비용 척도 — 무엇을 세는가[편집]

고전 알고리즘에서 연산 횟수 하나면 되던 자리에, 양자 회로는 척도가 넷이다.

척도	정의	왜 중요한가
폭 (width)	큐비트 수	하드웨어 상한. 지금은 이게 벽이다
깊이 (depth)	DAG의 최장 경로	결어긋남 시간 $T_2$ 안에 끝나야 한다
2큐비트 게이트 수	CNOT/CZ 개수	오류율이 단일 큐비트보다 한 자릿수 높다
T-count / T-depth	비클리퍼드 게이트 수	결함허용 층에서 유일하게 비싼 자원

NISQ 시대에는 위의 셋, 결함허용 시대에는 넷째가 지배한다. 이 전환이 회로 최적화 연구의 성격을 통째로 바꿨다. 오류 정정 없는 칩에서는 CNOT 하나 줄이는 게 이득이지만, 표면 부호 위에서는 클리퍼드가 사실상 공짜고 $T$ 하나에 마법 상태 증류 공장의 산출 하나가 소모된다. 같은 회로를 두고 두 척도가 정반대 최적화를 지시하는 경우가 흔하다.

5. 트랜스파일 — 컴파일러가 실제로 하는 일[편집]

사람이 쓴 논리 회로와 칩에 내려가는 펄스 열 사이에는 컴파일러가 있다. 단계는 대략 넷이다.

분해(decomposition). 추상 게이트를 백엔드의 네이티브 집합으로 다시 쓴다. ZYZ 분해, KAK 분해, 클리퍼드+T 합성 — 전부 양자 게이트 문서의 내용이다.
배치(placement). 논리 큐비트를 물리 큐비트에 할당한다. 물리 큐비트마다 오류율과 결맞음 시간이 다르므로 “아무 데나”가 아니다.
경로 배정(routing). 연결되지 않은 두 물리 큐비트 사이에 2큐비트 게이트가 필요하면 SWAP을 삽입해 데려온다. SWAP 하나가 CNOT 3개이므로 여기서 게이트 수가 폭증한다.
최적화. 이웃한 회전 합치기, $\mathrm{CNOT}^2=\mathbb{1}$ 지우기, 교환 관계로 게이트 재배열하기.

이 중 2·3번을 합친 큐비트 매핑 문제는 NP-난해다. 목적함수(삽입된 SWAP 수 또는 최종 깊이)를 최소화하는 배치와 라우팅을 동시에 찾는 문제이고, 실무 컴파일러는 휴리스틱을 쓴다. 대표적인 SABRE 계열은 회로를 앞뒤로 번갈아 훑으며 초기 배치를 개선하는 방식으로, 그래프 분할·배치 배선 문제에서 쓰이는 발상과 같은 계보다.² 작은 블록에 대해서만 정수계획법이나 SAT 풀이기로 최적해를 뽑는다.

라우팅 비용은 하드웨어 위상에 통째로 지배된다. 격자형 초전도 칩에서 임의의 두 큐비트를 붙이려면 평균 $O(\sqrt{n})$ 개의 SWAP이 필요하고, 전연결(all-to-all)인 이온 트랩에서는 0이다. 연결성이 곧 오류 예산이라는 문장이 여기서 나온다.

회로 항등식을 체계적으로 다루는 도구로 ZX-계산이 있다. 회로를 스파이더 그래프로 바꾸고 국소 재작성 규칙만으로 등가 변형을 하는 형식 체계인데, 회로 도식으로는 안 보이는 상쇄가 그래프에서는 보인다. T-count 최적화에서 특히 성과를 냈다.

6. 고전 시뮬레이션 — 이 위키가 관심 있는 부분[편집]

양자 회로를 고전 컴퓨터로 돌리는 일은 검증·디버깅·알고리즘 개발의 전부이고, 순수하게 수치해석 문제다.

6.1. 상태벡터[편집]

가장 정직한 방법. $n$ 큐비트 상태를 $2^n$ 개의 복소수 배열로 들고, 게이트마다 배열을 갱신한다. 배정밀도 복소수(16바이트) 기준 메모리는

M = 2^{n}\times 16\ \text{B}

이고, 이 지수는 봐줄 생각이 없다.

큐비트 수	메모리
30	16 GiB
35	512 GiB
40	16 TiB
45	512 TiB
50	16 PiB

노트북에서 30, 좋은 서버 한 대에서 35, 슈퍼컴퓨터 전체를 동원해 45~50이 한계다.³ 큐비트 하나 늘 때마다 메모리가 두 배라서, 예산을 두 배 태우면 딱 한 개 더 얻는다. 세상에서 가장 손해 보는 장사.

계산 구조는 의외로 단순하다. 큐비트 $q$ 에 단일 큐비트 게이트를 거는 것은, 인덱스의 $q$ 번째 비트만 다른 진폭 쌍 $2^{n-1}$ 개를 각각 $2\times2$ 행렬로 갱신하는 것이다.

\begin{pmatrix}\psi'_{\dots 0_q\dots}\\ \psi'_{\dots 1_q\dots}\end{pmatrix} = U\begin{pmatrix}\psi_{\dots 0_q\dots}\\ \psi_{\dots 1_q\dots}\end{pmatrix}

즉 스트라이드 $2^q$ 짜리 접근 패턴에 게이트당 산술 연산은 $O(2^n)$ — 완전히 메모리 대역폭 지배다. 낮은 인덱스 큐비트는 캐시 안에서 놀지만 높은 인덱스 큐비트는 스트라이드가 커져 캐시가 죽고, 분산 환경에서는 노드 경계를 넘는 큐비트가 통째로 all-to-all 통신이 된다. 그래서 실무 시뮬레이터는 게이트 순서를 바꿔 통신 큐비트를 몰아 처리하고, 여러 게이트를 하나의 블록 행렬로 융합(gate fusion)해 배열 순회 횟수를 줄인다. 최적화의 성격이 희소행렬 커널 튜닝과 놀랄 만큼 닮았다.

6.2. 밀도행렬[편집]

잡음을 넣으려면 상태벡터로는 부족하고 밀도행렬이 필요하다. 그러면 크기가 $4^n$ 이 된다 — 도달 가능한 큐비트 수가 정확히 절반이다. 20큐비트가 상태벡터 40큐비트와 같은 메모리를 먹는다. 이 벽 때문에 잡음 시뮬레이션은 대개 밀도행렬 대신 양자 궤적(quantum trajectory) 을 쓴다. 상태벡터 여러 개를 확률적으로 굴려 몬테카를로 방법으로 평균을 내는 것으로, $4^n$ 을 $2^n\times N_{\rm traj}$ 로 바꾸는 고전적인 시간–메모리 트레이드오프다.

6.3. 텐서망[편집]

회로를 텐서 네트워크로 보면 상태 전체를 만들 필요가 없다. 특정 진폭 하나 또는 특정 관측량 하나를 원한다면 그에 해당하는 망을 축약하면 되고, 비용은 큐비트 수가 아니라 축약 순서가 만드는 중간 텐서의 크기가 결정한다. 이 비용의 하한이 회로 그래프의 트리폭(treewidth)이라, 얕고 국소적인 회로는 싸고 깊고 얽힌 회로는 비싸다. 1차원 얕은 회로는 결합 차원이 제한된 행렬곱 상태로 사실상 공짜다.

축약 순서 찾기 자체가 NP-난해한 조합 최적화 문제이고, 여기에 좋은 휴리스틱을 붙이는 것이 지난 몇 년 이 분야에서 가장 실적이 좋았던 연구 방향이다. 초창기 “양자 우위” 주장들이 이후 고전 클러스터의 텐서망 축약에 따라잡힌 사건이 반복되면서, 양자 우위의 경계선은 하드웨어가 아니라 고전 시뮬레이션 알고리즘이 옮기고 있다는 인식이 자리 잡았다.

6.4. 안정자 시뮬레이터와 하이브리드[편집]

클리퍼드만 있는 회로는 안정자 부호 문서의 태블로 방법으로 다항 시간에 돈다. $T$ 게이트가 $t$ 개 섞이면 비용이 $t$ 에 대해 지수적으로 오르므로, $t$ 가 작은 회로는 안정자 분해로 뚫린다. 이 ” $T$ 개수를 눈금으로 삼는” 관점이 회로의 고전적 난이도를 재는 표준이 되었다.

슈뢰딩거–파인만 하이브리드도 있다. 회로를 두 덩어리로 자르고 자른 면을 지나는 게이트에 대해 경로 합을 하면, 메모리는 절반 크기 시뮬레이션 두 개면 되고 대신 시간이 자른 게이트 수에 지수적으로 든다. 메모리가 벽일 때 시간으로 갚는 전략이다.

7. 변분 회로 — 얕은 회로로 뭘 할 수 있나[편집]

오류 정정 없이 쓸 수 있는 깊이가 제한된 상황에서 나온 실무 패턴이 변분 양자 회로다. 매개변수 $\boldsymbol\theta$ 를 가진 얕은 회로 $U(\boldsymbol\theta)$ 를 양자 하드웨어에서 돌려 기댓값 $\langle\psi(\boldsymbol\theta)|H|\psi(\boldsymbol\theta)\rangle$ 만 측정하고, 최적화는 고전 컴퓨터가 맡는다. 분자 바닥상태를 찾는 VQE와 조합 최적화 문제를 푸는 QAOA가 두 대표 주자다.

기울기는 유한차분이 아니라 매개변수 이동 규칙으로 정확히 얻는다. 게이트가 $e^{-i\theta P/2}$ 꼴이면

\frac{\partial f}{\partial\theta}=\frac{f(\theta+\tfrac{\pi}{2})-f(\theta-\tfrac{\pi}{2})}{2}

가 근사가 아니라 등식이다. 유한차분과 달리 절단 오차가 없다는 점이 샷 잡음이 지배하는 환경에서 결정적이다.

다만 이 접근의 근본 문제도 잘 알려져 있다. 불모 고원(barren plateau) — 회로가 깊고 무작위에 가까울수록 기울기의 분산이 큐비트 수에 대해 지수적으로 0으로 죽어, 최적화가 시작조차 못 한다. 처방은 구조 있는 안사츠, 국소 관측량, 층별 학습 등인데 전부 부분적이다. 여기에 관측량 하나를 정밀도 $\epsilon$ 로 재려면 샷이 $O(1/\epsilon^2)$ 필요하다는 통계적 비용까지 겹친다. 양자 회로는 기울기를 공짜로 주지 않는다 — 역전파가 한 번의 순전파 비용으로 모든 매개변수 기울기를 주는 고전 딥러닝과 가장 크게 갈리는 지점이다.

8. 관련 문서[편집]

도식의 왼쪽이 곱의 오른쪽이라는 규약은 순전히 역사적 사고다. 함수 합성 $f(g(x))$ 는 오른쪽부터 적용되는데 회로도는 왼쪽부터 읽으니 어쩔 수 없다. 도식 순서대로 곱하는 표기를 쓰는 논문도 있어서, 남의 코드를 가져다 쓸 때는 전치를 먼저 의심하는 게 정신 건강에 좋다. ↩
배치와 라우팅을 동시에 최적화해야 한다는 점, 목적함수가 비볼록하고 해공간이 조합적이라는 점, 그래서 결국 좋은 초기해 + 국소 탐색으로 간다는 점까지 반도체 설계자동화(EDA)의 배치·배선과 판박이다. 실제로 EDA 하던 사람들이 이 바닥으로 넘어와 같은 트릭을 다시 쓰고 있다. ↩
“우리 슈퍼컴퓨터로 45큐비트 시뮬레이션 성공”이라는 기사 제목은 사실 “16 TiB짜리 배열을 노드 수천 개에 흩뿌리고 게이트마다 all-to-all 통신을 견뎠다”는 뜻이다. 물리학 성과라기보다 HPC 통신 최적화 성과에 가깝고, 논문의 절반이 MPI 이야기인 것도 그래서다. ↩