큐비트가 늘어나면 게이트는 전체 상태공간 위의 큰 행렬로 lift됩니다. 이 문서는 그 확장 규칙을 작은 예제로 계산합니다.
## 차원 증가 {#dimension}
큐비트 하나는 2차원, 큐비트 n개는 $2^n$차원이다. 재귀적으로 1큐비트 늘어날 때마다 텐서곱을 통해 차원이 2배가 된다.
$$
|\psi\rangle = \sum_{x\in\{0,1\}^n} a_x |x\rangle,
\qquad
\sum_x |a_x|^2=1
$$
## Kronecker product {#kronecker}
행렬 $A$와 $B$의 텐서곱은 block matrix로 계산합니다.
$$
A\otimes B =
\begin{bmatrix}
a_{00}B & a_{01}B\\
a_{10}B & a_{11}B
\end{bmatrix}
$$
예를 들어 $X\otimes I$는 첫 번째 큐비트만 뒤집습니다.
$$
(X\otimes I)|00\rangle=|10\rangle,\qquad
(X\otimes I)|01\rangle=|11\rangle
$$
## 큐비트 순서 주의 {#ordering}
프레임워크마다 qubit ordering convention이 다를 수 있습니다. 수학 문서에서는 보통 $|q_0q_1\rangle$ 순서를 그대로 쓰지만, SDK에서는 little-endian 표시를 쓰는 경우가 있습니다.
필자도 Qiskit을 처음 사용할 때 큐비트 순서를 정방향으로 입력했다가 결과 bitstring이 반대로 나온 적이 있습니다. Qiskit 결과를 볼 때는 little-endian이 기본이라고 생각하고, 화면에 찍힌 문자열과 수학적으로 생각한 레지스터 순서가 같은지 먼저 확인하는 편이 안전합니다.
계산이 꼬이면 먼저 basis ordering을 명시합니다.
$$
|00\rangle, |01\rangle, |10\rangle, |11\rangle
$$
## 특정 큐비트에만 게이트 적용 {#local-gate}
3큐비트에서 가운데 큐비트에 H를 적용하려면 양쪽에 항등행렬을 붙입니다.
$$
I\otimes H\otimes I
$$
입력 $|010\rangle$에 적용하면 가운데 1이 $|-\rangle$로 바뀝니다.
$$
(I\otimes H\otimes I)|010\rangle
=
|0\rangle\otimes {|0\rangle-|1\rangle\over\sqrt{2}}\otimes |0\rangle
$$
## 왜 전체 행렬을 만들지 않는가 {#sparse}
10큐비트 유니터리는 $1024\times1024$ 행렬입니다. 30큐비트가 되면 상태벡터만으로도 이미 $2^{30}$개 진폭이 필요합니다.
그래서 실제 시뮬레이터는 회로를 게이트별로 적용하고, 실제 하드웨어는 큰 행렬을 만들지 않고 펄스와 게이트 sequence로 실행합니다.
## 회로설계 규칙 {#rule}
1. 작은 게이트의 수학적 의미를 먼저 확인합니다.
2. 어느 큐비트에 적용되는지 텐서 위치를 명시합니다.
3. basis ordering을 고정합니다.
4. 전체 행렬보다 게이트 sequence를 기준으로 생각합니다.
## basis index를 숫자로 읽는 법 {#indexing}
n큐비트 basis state는 비트열이면서 동시에 정수 인덱스입니다. 예를 들어 big-endian 관례를 쓰면 $|q_0q_1q_2\rangle$는 아래 정수에 대응합니다.
$$
q_0q_1q_2
\quad\mapsto\quad
4q_0+2q_1+q_2
$$
따라서 3큐비트 상태벡터의 진폭 배열은 보통 아래 순서입니다.
$$
(a_{000},a_{001},a_{010},a_{011},a_{100},a_{101},a_{110},a_{111})^T
$$
SDK가 little-endian 출력 convention을 쓰면 화면에 보이는 bitstring과 수학적으로 생각한 qubit 순서가 반대로 느껴질 수 있습니다. 실험 결과를 해석할 때 이 차이가 버그처럼 보이는 경우가 많습니다.
## 3큐비트에서 가운데 큐비트에 X 적용하기 {#operator-lift-example}
3큐비트 상태에서 가운데 큐비트에 X를 적용하는 연산은 $I\otimes X\otimes I$입니다. basis state에 직접 적용하면 가운데 비트만 뒤집힙니다.
$$
|000\rangle\mapsto|010\rangle,\quad
|001\rangle\mapsto|011\rangle,\quad
|100\rangle\mapsto|110\rangle
$$
일반 상태에 적용하면 각 진폭의 위치가 permutation됩니다.
$$
\sum_{a,b,c} \alpha_{abc}|abc\rangle
\mapsto
\sum_{a,b,c} \alpha_{abc}|a(1-b)c\rangle
$$
이 관점은 simulator를 구현할 때도 중요합니다. 큰 행렬을 만들지 않고, 진폭 배열에서 target bit가 다른 위치끼리 pair를 이루어 업데이트합니다.
## 제어게이트의 텐서 확장 {#controlled-lift}
두 큐비트 인접 게이트를 전체 n큐비트 공간에 올리는 것은 단순히 $I\otimes U\otimes I$처럼 깔끔하지 않을 때가 많습니다. 특히 control과 target이 떨어져 있으면 basis index에서 특정 두 비트를 골라 조건부 업데이트를 해야 합니다.
예를 들어 4큐비트에서 0번 큐비트가 control, 3번 큐비트가 target인 CX는 아래처럼 작동합니다.
$$
|q_0q_1q_2q_3\rangle
\mapsto
|q_0q_1q_2(q_3\oplus q_0)\rangle
$$
수학적으로는 permutation matrix이지만, 회로 컴파일러는 실제 하드웨어에서 두 큐비트가 연결되어 있는지 먼저 봅니다. 연결되어 있지 않으면 SWAP을 넣어 서로 가까이 가져옵니다.
## 상태벡터 업데이트 관점 {#state-vector-update}
단일 큐비트 게이트를 n큐비트 상태에 적용하는 것은 진폭 배열의 pair 업데이트입니다. target bit가 0인 인덱스 $i$와 target bit가 1인 인덱스 $j$를 묶습니다.
$$
\begin{bmatrix}
a_i'\\
a_j'
\end{bmatrix}
=
U
\begin{bmatrix}
a_i\\
a_j
\end{bmatrix}
$$
예를 들어 H를 target bit에 적용하면 각 pair는 아래처럼 바뀝니다.
$$
a_i'={a_i+a_j\over\sqrt{2}},\qquad
a_j'={a_i-a_j\over\sqrt{2}}
$$
이 pair 업데이트가 constructive/destructive amplitude의 가장 낮은 수준의 계산입니다. 두 진폭이 같은 부호면 한쪽은 커지고, 다른 쪽은 0이 될 수 있습니다.
## 큰 행렬을 만들지 않는 이유 {#why-not-matrix}
n큐비트 유니터리는 $2^n\times2^n$ 행렬입니다. 20큐비트만 되어도 행렬 원소 수는 $2^{40}$개입니다. 이는 단순 학습 예제가 아니라면 직접 만들 수 없는 크기입니다.
그래서 실제 회로설계와 시뮬레이션은 다음 관점을 씁니다.
- 회로는 큰 행렬 하나가 아니라 작은 로컬 게이트들의 sequence다.
- 각 게이트는 관련된 qubit subset의 진폭만 업데이트한다.
- 얽힘이 적거나 구조가 있으면 tensor network 등으로 압축할 수 있다.
- 하지만 일반적인 깊은 회로는 빠르게 고전 시뮬레이션이 어려워진다.