Controlled-U
control이 0이면 아무것도 하지 않고, 1이면 target에 U를 적용합니다.
$$
\mathrm{C}U
=
|0\rangle\langle0|\otimes I
+|1\rangle\langle1|\otimes U
$$입력 a\in\{0,1\}에 대해 아래처럼 읽으면 됩니다.
$$
\mathrm{C}U(|a\rangle|\psi\rangle)
=
|a\rangle U^a|\psi\rangle
$$CNOT / CX
CX는 target에 X를 조건부로 적용합니다.
$$
\mathrm{CX}|a,b\rangle=|a,b\oplus a\rangle
$$계산기저 순서를 |00\rangle,|01\rangle,|10\rangle,|11\rangle로 잡으면 행렬은 아래와 같습니다.
$$
\mathrm{CX}=
\begin{bmatrix}
1&0&0&0\\
0&1&0&0\\
0&0&0&1\\
0&0&1&0
\end{bmatrix}
$$CZ와 phase kick
CZ는 두 큐비트가 모두 1일 때만 부호를 뒤집습니다.
$$
\mathrm{CZ}|a,b\rangle=(-1)^{ab}|a,b\rangle
$$CZ는 대각행렬이라 target이 따로 없어 보이지만, H를 끼우면 CX와 서로 바뀝니다.
$$
\mathrm{CX}=(I\otimes H)\mathrm{CZ}(I\otimes H)
$$Toffoli / CCX
CCX는 두 control이 모두 1일 때 target을 뒤집습니다.
$$
\mathrm{CCX}|a,b,c\rangle=|a,b,c\oplus ab\rangle
$$ancilla가 0으로 준비되어 있으면 AND 값을 reversible하게 저장할 수 있습니다.
$$
|a,b,0\rangle \mapsto |a,b,ab\rangle
$$중요한 점은 계산 후 ancilla를 다시 0으로 돌려놓는 uncomputation입니다. 그렇지 않으면 ancilla가 본 계산과 얽혀 뒤의 간섭을 방해합니다.
제어게이트의 양자정보이론적 의미
제어게이트는 단순한 if문처럼 보이지만, control이 중첩상태일 때는 고전 조건문과 완전히 달라집니다. control이 (|0\rangle+|1\rangle)/\sqrt{2}이고 target이 |0\rangle이면 CX는 아래 상태를 만듭니다.
$$
\mathrm{CX}
\left(
{ |0\rangle+|1\rangle\over\sqrt{2}}\otimes|0\rangle
\right)
=
{ |00\rangle+|11\rangle\over\sqrt{2}}
$$이 결과는 두 큐비트를 따로따로의 상태로 분리해서 쓸 수 없는 Bell 상태입니다. 즉 제어게이트는 “조건부 실행”을 넘어서, 중첩된 조건과 target 사이에 상관관계를 만들고 얽힘을 생성하는 장치입니다.
또 제어게이트는 정보의 복사처럼 보일 수 있지만, 임의의 미지 양자상태를 복사하는 것은 아닙니다. CX가 복사처럼 작동하는 것은 계산기저 |0\rangle,|1\rangle에 대해서입니다.
$$
\mathrm{CX}|a,0\rangle=|a,a\rangle
\quad (a\in\{0,1\})
$$하지만 \alpha|0\rangle+\beta|1\rangle를 control로 넣으면 복사본 두 개가 아니라 얽힌 상태가 됩니다.
$$
\mathrm{CX}
(\alpha|0\rangle+\beta|1\rangle)|0\rangle
=
\alpha|00\rangle+\beta|11\rangle
$$이 차이가 양자정보이론에서 중요합니다. 제어게이트는 정보 복사가 아니라 basis-dependent correlation을 만들고, 그 correlation이 중첩과 결합하면 얽힘이 됩니다.
비용 관점
제어 게이트가 많아질수록 회로는 빠르게 비싸집니다. 하드웨어에서는 2큐비트 게이트가 오류율과 duration 측면에서 핵심 병목입니다.
- controlled-U는 U의 구조에 따라 분해 비용이 달라집니다.
- multi-controlled gate는 ancilla를 쓰면 깊이를 줄일 수 있습니다.
- CZ/CX 변환은 H 두 개만 추가하면 되므로 하드웨어 native gate에 맞춰 자주 바꿉니다.
NISQ 시대에 왜 분해가 중요한가
실제 장비는 “원하는 큰 게이트를 그대로 실행하는 기계”가 아닙니다. 하드웨어가 안정적으로 제공하는 기본 게이트 집합이 있고, 복잡한 다중 큐비트 연산은 그 기본 게이트들의 조합으로 바꿔 실행합니다.
비전공자식으로 말하면, 큰 기계 동작 하나를 한 번에 정확히 시키기 어렵기 때문에, 비교적 잘 되는 작은 동작 여러 개로 쪼개서 비슷하게 수행하는 것입니다. 다만 작은 동작마다 오차가 조금씩 있으므로, 너무 많이 쪼개면 오차가 누적됩니다.
NISQ 시대의 핵심 과제는 여기서 나옵니다. 많은 큐비트가 얽힌 큰 연산을 가능한 한 적은 수의 1큐비트/2큐비트 게이트 조합으로 바꾸고, 하드웨어 topology에 맞춰 SWAP을 줄이고, 전체 깊이를 낮춰서 오차가 커지기 전에 계산을 끝내야 합니다.
$$
\text{large controlled operation}
\quad\Rightarrow\quad
\text{1Q/2Q gate decomposition}
\quad\Rightarrow\quad
\text{depth, error, connectivity tradeoff}
$$그래서 제어게이트를 공부할 때는 수학적 정의뿐 아니라 “이걸 실제 장비의 작은 게이트들로 바꾸면 얼마나 비싼가”를 항상 같이 봐야 합니다.
control이 중첩일 때 생기는 일
control이 고전적으로 0 또는 1이면 제어게이트는 if문처럼 보입니다. 하지만 control이 중첩이면 제어게이트는 “두 경우를 동시에 실행”하는 것처럼 보이면서도, 실제로는 두 분기 사이의 위상 관계를 보존합니다.
일반적인 control 상태를 \alpha|0\rangle+\beta|1\rangle라 두면 controlled-U는 아래처럼 작용합니다.
$$
\mathrm{C}U
(\alpha|0\rangle+\beta|1\rangle)|\psi\rangle
=
\alpha|0\rangle|\psi\rangle
+\beta|1\rangle U|\psi\rangle
$$만약 |\psi\rangle와 U|\psi\rangle가 서로 다른 상태라면, control과 target은 일반적으로 얽힙니다. 이 구조가 phase estimation, controlled modular multiplication, quantum walk, amplitude amplification에서 계속 등장합니다.
Phase kickback
제어게이트의 가장 중요한 응용 중 하나는 phase kickback입니다. target이 U의 고유상태라면 controlled-U는 target을 바꾸지 않고 control에 위상을 되돌려줍니다.
$$
U|u\rangle=e^{2\pi i\phi}|u\rangle
$$$$
\mathrm{C}U
{ |0\rangle+|1\rangle \over \sqrt{2}}
|u\rangle
=
{ |0\rangle+e^{2\pi i\phi}|1\rangle \over \sqrt{2}}
|u\rangle
$$target의 고유위상이 control의 상대 위상으로 올라온 것입니다. 이 원리가 Bernstein-Vazirani의 phase oracle, Deutsch-Jozsa의 부호 반전, Shor의 phase estimation에서 모두 같은 형태로 쓰입니다.
Multi-control 설계 감각
여러 control이 모두 1일 때만 어떤 연산을 하고 싶다면 multi-controlled gate가 필요합니다. 예를 들어 n개 control의 AND 조건은 아래처럼 쓸 수 있습니다.
$$
|x_1,\dots,x_n,y\rangle
\mapsto
|x_1,\dots,x_n,y\oplus(x_1x_2\cdots x_n)\rangle
$$하지만 하드웨어가 이런 큰 게이트를 직접 제공하는 경우는 드뭅니다. 보통 Toffoli, CX, 단일 큐비트 회전으로 분해합니다. ancilla를 충분히 쓰면 AND 값을 단계적으로 저장할 수 있습니다.
$$
a_1=x_1x_2,\quad
a_2=a_1x_3,\quad
\dots,\quad
a_{n-1}=a_{n-2}x_n
$$계산 후에는 이 ancilla들을 역순으로 지워야 합니다. 이를 하지 않으면 “조건이 참이었는지”에 대한 정보가 ancilla에 남고, 본 계산과 얽혀서 간섭을 망칩니다.
분해의 직관: 정확한 큰 블록보다 작은 블록들의 조합
회로도에서 큰 controlled operation을 하나의 박스로 그리는 것은 개념적으로 편합니다. 하지만 실제 장비는 그 박스를 그대로 실행하지 않습니다. transpiler는 그것을 하드웨어가 아는 작은 instruction들로 바꿉니다.
이때 목표는 단순히 “수학적으로 같은 회로”를 만드는 것이 아닙니다. 실제 목표는 다음 세 가지의 균형입니다.
- 게이트 수를 줄여 오류 누적을 줄인다.
- 회로 깊이를 줄여 decoherence 전에 끝낸다.
- 장비 connectivity에 맞춰 불필요한 SWAP을 줄인다.
NISQ에서는 완벽한 논리 연산보다 “오류가 누적되기 전에 대충 충분히 좋은 근사 결과를 얻는 것”이 중요할 때가 많습니다. 그래서 큰 다중 큐비트 연산은 최대한 적은 2큐비트 게이트와 단일 큐비트 보정으로 분해하려고 합니다.