Circuits

컴퓨터 과학에서 Circuit은 선(wire)을 통해 정보가 운반되고, 그 정보에 대한 연산을 나타내는 Gate들의 네트워크를 거치는 계산 모델입니다. 양자 Circuit은 이러한 보다 일반적인 개념을 바탕으로 한 구체적인 계산 모델입니다.

"circuit"이라는 단어는 흔히 원형의 경로를 가리키지만, 가장 널리 연구되는 Circuit 계산 모델에서는 사실 원형 경로가 허용되지 않습니다. 다시 말해, Circuit을 계산 모델로 생각할 때 우리는 보통 비순환(acyclic) Circuit을 고려합니다. 양자 Circuit도 이러한 형태를 따르며, 양자 Circuit은 피드백 루프를 포함할 수 없는 유한한 연산 시퀀스를 나타냅니다.

불리언 Circuit

다음은 선이 이진 값을 운반하고 Gate가 불리언 논리 연산을 나타내는 (고전적인) 불리언 Circuit의 예입니다:

선을 따라 흐르는 정보의 방향은 왼쪽에서 오른쪽입니다. 그림 왼쪽에서 $\mathsf{X}$와 $\mathsf{Y}$로 표시된 선은 입력 비트로서, 각각 우리가 원하는 이진 값으로 설정할 수 있으며, 오른쪽에 있는 선은 출력입니다. 중간에 있는 선들은 Gate에 의해 결정되는 값을 가지며, Gate는 왼쪽에서 오른쪽 순으로 평가됩니다.

Gate는 AND Gate($\wedge$로 표시), OR Gate($\vee$로 표시), NOT Gate($\neg$로 표시)입니다. 이 Gate들이 계산하는 함수는 많은 독자에게 익숙할 것입니다만, 여기서는 값의 표로 표현하였습니다:

$$\begin{array}{c} \begin{array}{c|c} a & \neg a\\ \hline 0 & 1\\ 1 & 0\\ \end{array}\\ \\ \\ \end{array} \qquad\quad \begin{array}{c|c} ab & a \wedge b\\ \hline 00 & 0\\ 01 & 0\\ 10 & 0\\ 11 & 1 \end{array} \qquad\quad \begin{array}{c|c} ab & a \vee b\\ \hline 00 & 0\\ 01 & 1\\ 10 & 1\\ 11 & 1 \end{array}$$

$\mathsf{X}$와 $\mathsf{Y}$라는 이름 바로 오른쪽 선 위에 있는 두 개의 작은 검은 원은 팬아웃(fan-out) 연산을 나타냅니다. 이 연산은 단순히 해당 선이 운반하는 값의 복사본을 생성하여 그 값이 여러 Gate로 입력될 수 있도록 합니다. 팬아웃 연산은 고전 환경에서는 항상 Gate로 간주되지는 않으며, 때때로 어떤 의미에서 "공짜"인 것처럼 취급되기도 합니다. 그러나 불리언 Circuit이 등가의 양자 Circuit으로 변환될 때에는 팬아웃 연산을 올바르게 다루고 처리하기 위해 이를 Gate로 명시적으로 분류할 필요가 있습니다.

다음은 동일한 Circuit을 전기공학에서 더 흔히 사용되는 스타일, 즉 AND, OR, NOT Gate에 대한 기존 기호를 이용해 나타낸 것입니다:

앞으로 이 스타일이나 이러한 특정 Gate 기호를 더 사용하지는 않겠지만, 양자 Circuit에서 Gate를 나타내기 위해 다른 기호들을 사용할 것이며, 이는 등장할 때마다 설명할 것입니다.

이 예시에 나오는 특정 Circuit은 배타적 논리합(exclusive-OR), 즉 XOR를 계산하며, 이는 $\oplus$ 기호로 나타냅니다:

$$\begin{array}{c|c} ab & a \oplus b\\ \hline 00 & 0\\ 01 & 1\\ 10 & 1\\ 11 & 0 \end{array}$$

다음 다이어그램에서는 입력에 대해 단 하나의 선택인 $\mathsf{X}=0$과 $\mathsf{Y}=1$만을 고려합니다. 각 선에는 해당 선이 운반하는 값이 표시되어 있어 연산을 따라갈 수 있습니다. 이 경우 출력 값은 $1$이며, 이는 XOR의 올바른 값입니다: $0 \oplus 1 = 1.$

나머지 세 가지 가능한 입력 설정도 비슷한 방식으로 확인할 수 있습니다.

다른 유형의 Circuit

앞서 시사한 바와 같이, 컴퓨터 과학에서 Circuit의 개념은 매우 일반적입니다. 예를 들어, 선이 $0$과 $1$ 외의 값을 운반하는 Circuit이나 다른 연산을 나타내는 Gate를 갖는 Circuit도 때때로 분석됩니다.

예를 들어, 산술 Circuit에서는 선이 정수 값을 운반하고 Gate는 덧셈, 곱셈과 같은 산술 연산을 나타낼 수 있습니다. 다음 그림은 두 개의 변수 입력 값($x$와 $y$)과 함께 값이 $1$로 설정된 세 번째 입력을 받는 산술 Circuit을 나타냅니다. 선이 운반하는 값은 $x$와 $y$의 함수로서 그림에 표시되어 있습니다.

또한 Gate가 확률적 연산을 나타내는 경우처럼 무작위성을 포함하는 Circuit도 생각해 볼 수 있습니다.

양자 Circuit

양자 Circuit 모델에서 선은 Qubit을 나타내고, Gate는 이 Qubit에 대한 연산을 나타냅니다. 지금은 지금까지 살펴본 연산들, 즉 유니타리 연산과 표준 기저 측정에 초점을 맞추겠습니다. 다른 종류의 양자 연산과 측정에 대해 배우면서 그에 따라 모델을 확장할 수 있습니다.

다음은 양자 Circuit의 간단한 예입니다:

이 Circuit에는 수평선으로 나타내어진 $\mathsf{X}$라는 이름의 Qubit이 하나 있으며, 이 Qubit에 대한 유니타리 연산을 나타내는 Gate들의 시퀀스가 있습니다. 앞선 예시들에서와 마찬가지로, 정보의 흐름은 왼쪽에서 오른쪽으로 진행되므로 가장 먼저 수행되는 연산은 Hadamard 연산이고, 두 번째는 $S$ 연산, 세 번째는 또 다른 Hadamard 연산, 마지막 연산은 $T$ 연산입니다. 따라서 전체 Circuit을 적용하면 Qubit $\mathsf{X}$에 이 연산들의 합성인 $T H S H$가 적용됩니다.

때로는 Circuit의 입력 또는 출력 상태를 명시적으로 나타내고 싶을 수 있습니다. 예를 들어, 상태 $\vert 0\rangle$에 연산 $T H S H$를 적용하면 상태 $\frac{1+i}{2}\vert 0\rangle + \frac{1}{\sqrt{2}} \vert 1 \rangle$를 얻습니다. 이는 다음과 같이 나타낼 수 있습니다:

양자 Circuit은 이 경우처럼 모든 Qubit이 $\vert 0\rangle$로 초기화되어 시작하는 경우가 많지만, 입력 Qubit이 처음부터 다른 상태로 설정되는 상황도 있습니다. 다음은 이번에는 두 개의 Qubit이 있는 양자 Circuit의 또 다른 예입니다:

언제나 그렇듯이 $H$로 표시된 Gate는 Hadamard 연산을 가리키며, 두 번째 Gate는 제어-NOT(controlled-NOT) 연산입니다. 검은 원은 *제어 Qubit(control qubit)*을 나타내고, $\oplus$ 기호와 비슷한 원은 *대상 Qubit(target qubit)*을 나타냅니다.

이 Circuit을 더 자세히 살펴보고 무엇을 하는지 설명하기 전에, 양자 Circuit에서 Qubit의 순서가 어떻게 매겨지는지 먼저 명확히 해 둘 필요가 있습니다. 이는 이전 수업에서 잠시 언급했던, Qiskit이 시스템의 이름을 지정하고 순서를 매기는 데 사용하는 관례와 연결됩니다.

Qiskit의 Circuit용 Qubit 순서 관례

Qiskit에서 Circuit 다이어그램의 가장 위쪽 Qubit은 인덱스 $0$을 가지며, Qubit 튜플(또는 이 튜플에 대응하는 문자열, 데카르트 곱, 텐서 곱)에서 가장 오른쪽 위치에 해당합니다. 위에서 두 번째 Qubit은 인덱스 $1$을 가지며 튜플의 오른쪽에서 두 번째 위치에 해당하고, 이하 마찬가지입니다. 따라서 가장 높은 인덱스를 가지는 가장 아래쪽 Qubit은 튜플의 가장 왼쪽 위치에 해당합니다. 특히 $n$-Qubit Circuit의 Qubit에 대한 Qiskit의 기본 이름은 $n$-튜플 $(\mathsf{q_{n-1}},\ldots,\mathsf{q_{0}})$로 표현되며, 양자 Circuit 다이어그램에서 $\mathsf{q_{0}}$는 맨 위에 있는 Qubit이고 $\mathsf{q_{n-1}}$는 맨 아래에 있는 Qubit입니다.

이는 Circuit에서 Qubit 순서를 매기는 더 일반적인 관례와는 반대이며, 자주 혼란의 원인이 된다는 점에 유의해 주세요. 이 순서 관례에 대한 추가 정보는 Bit-ordering in Qiskit 문서 페이지에서 확인할 수 있습니다.

Qiskit에서 Qubit의 기본 이름인 $\mathsf{q_{0}},\ldots,\mathsf{q_{n-1}}$에서 벗어나는 경우도 있지만, 이 과정 전체에 걸쳐 Circuit 다이어그램을 해석할 때에는 항상 위에서 설명한 순서 관례를 따를 것입니다. 따라서 위의 Circuit에 대한 우리의 해석은, 이것이 한 쌍의 Qubit $(\mathsf{X},\mathsf{Y})$에 대한 연산을 기술한다는 것입니다. 예를 들어 Circuit의 입력이 양자 상태 $\vert\psi\rangle \otimes \vert\phi\rangle$라면, 이는 아래쪽 Qubit $\mathsf{X}$가 상태 $\vert\psi\rangle$에서 시작하고 위쪽 Qubit $\mathsf{Y}$가 상태 $\vert\phi\rangle$에서 시작한다는 의미입니다.

이 Circuit이 무엇을 하는지 이해하기 위해 연산을 왼쪽에서 오른쪽으로 따라가 볼 수 있습니다.

1. 첫 번째 연산은 $\mathsf{Y}$에 대한 Hadamard 연산입니다:

   

   이처럼 단일 Qubit에 Gate를 적용할 때는 다른 Qubit(이 경우에는 단 하나의 다른 Qubit)에는 아무 일도 일어나지 않습니다. 아무 일도 일어나지 않는다는 것은 항등 연산이 수행되는 것과 동치입니다. 따라서 위 그림의 점선 사각형은 다음 연산을 나타냅니다:

   $$\mathbb{I}\otimes H = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix}.$$

   항등 행렬이 텐서 곱의 왼쪽에 있고 $H$가 오른쪽에 있다는 점에 유의해 주세요. 이는 Qiskit의 순서 관례와 일치합니다.

2. 두 번째 연산은 제어-NOT 연산으로, $\mathsf{Y}$가 제어이고 $\mathsf{X}$가 대상입니다:

   

   제어-NOT Gate의 표준 기저 상태에 대한 동작은 다음과 같습니다:

   

   Qubit의 순서를 $(\mathsf{X}, \mathsf{Y})$로 매기고 $\mathsf{X}$가 Circuit의 아래쪽, $\mathsf{Y}$가 위쪽에 있다고 하면, 제어-NOT Gate의 행렬 표현은 다음과 같습니다:

   $$\begin{pmatrix} 1 & 0 & 0 & 0\\[2mm] 0 & 0 & 0 & 1\\[2mm] 0 & 0 & 1 & 0\\[2mm] 0 & 1 & 0 & 0 \end{pmatrix}.$$

$U$라는 이름을 붙일, Circuit 전체가 구현하는 유니타리 연산은 위 연산들의 합성입니다:

$$U = \begin{pmatrix} 1 & 0 & 0 & 0\\[2mm] 0 & 0 & 0 & 1\\[2mm] 0 & 0 & 1 & 0\\[2mm] 0 & 1 & 0 & 0 \end{pmatrix} \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 & 0\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}}\\[2mm] 0 & 0 & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\[2mm] \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & 0 \end{pmatrix}.$$

특히, 벨(Bell) 상태에 대한 표기를 떠올리면,

$$\begin{aligned} \vert \phi^+ \rangle & = \frac{1}{\sqrt{2}} \vert 0 0 \rangle + \frac{1}{\sqrt{2}} \vert 1 1 \rangle \\[2mm] \vert \phi^- \rangle & = \frac{1}{\sqrt{2}} \vert 0 0 \rangle - \frac{1}{\sqrt{2}} \vert 1 1 \rangle \\[2mm] \vert \psi^+ \rangle & = \frac{1}{\sqrt{2}} \vert 0 1 \rangle + \frac{1}{\sqrt{2}} \vert 1 0 \rangle \\[2mm] \vert \psi^- \rangle & = \frac{1}{\sqrt{2}} \vert 0 1 \rangle - \frac{1}{\sqrt{2}} \vert 1 0 \rangle, \end{aligned}$$

다음을 얻을 수 있습니다.

$$\begin{aligned} U \vert 00\rangle & = \vert \phi^+\rangle\\ U \vert 01\rangle & = \vert \phi^-\rangle\\ U \vert 10\rangle & = \vert \psi^+\rangle\\ U \vert 11\rangle & = -\vert \psi^-\rangle. \end{aligned}$$

따라서 이 Circuit은 $\vert 00\rangle$로 초기화된 두 개의 Qubit 위에서 실행하면 상태 $\vert\phi^+\rangle$를 생성할 수 있는 방법을 제공합니다. 보다 일반적으로는, 이는 표준 기저를 벨 기저(Bell basis)로 변환하는 방법을 제공합니다. (이 예시에서는 중요하지 않지만, 마지막 상태에 붙어 있는 $-1$ 위상 인자 $-\vert \psi^-\rangle$는 원한다면 Circuit에 작은 수정을 가해 제거할 수 있다는 점에 유의해 주세요. 예를 들어 처음에 제어-$Z$ Gate를 추가할 수 있는데, 이는 제어가 $1$로 설정되었을 때 대상 Qubit에 NOT 연산 대신 $Z$ 연산이 적용된다는 점을 제외하면 제어-NOT Gate와 유사합니다. 또는 끝부분에 스왑(swap) Gate를 추가할 수도 있습니다. 어느 쪽을 선택하든 다른 세 개의 표준 기저 상태에 대한 Circuit의 작용에 영향을 주지 않고 마이너스 부호를 제거할 수 있습니다.)

일반적으로 양자 Circuit은 임의 개수의 Qubit 선을 포함할 수 있습니다. 또한 이 예시에서처럼 이중 선으로 표시되는 고전 비트(classical bit) 선도 포함할 수 있습니다:

여기에는 이전 예시에서와 마찬가지로 두 Qubit $\mathsf{X}$와 $\mathsf{Y}$에 대한 Hadamard Gate와 제어-NOT Gate가 있습니다. 또한 두 개의 고전 비트 $\mathsf{A}$와 $\mathsf{B}$, 그리고 두 개의 측정 Gate가 있습니다. 측정 Gate는 표준 기저 측정을 나타냅니다: Qubit은 측정 후 상태로 변경되고, 측정 결과는 화살표가 가리키는 고전 비트에 덮어쓰여집니다.

측정을 Qubit을 입력으로 받아 고전 비트를 출력하는 Gate로 묘사하는 것이 편리할 때가 많습니다 (Qubit을 측정 후 상태로 출력하고 그 결과를 별도의 고전 비트에 기록하는 방식 대신). 이는 측정된 Qubit이 폐기되어 이후로는 안전하게 무시할 수 있으며, 측정 결과에 따라 그 상태가 $\vert 0\rangle$ 또는 $\vert 1\rangle$로 변경되었음을 의미합니다.

예를 들어, 다음 Circuit 다이어그램은 이전 다이어그램과 동일한 과정을 나타내지만, $\mathsf{X}$와 $\mathsf{Y}$를 측정한 후에는 이를 무시하는 경우입니다:

수업이 계속됨에 따라 위의 간단한 예시들보다 대체로 더 복잡한 양자 Circuit의 예시들을 더 많이 보게 될 것입니다. 다음은 Circuit 다이어그램에 흔히 등장하는 Gate를 나타내기 위해 사용되는 기호의 몇 가지 예입니다:

• 단일 Qubit Gate는 일반적으로 어떤 연산인지를 나타내는 글자가 있는 사각형으로 다음과 같이 표시됩니다:

  

  NOT Gate(동등하게는 $X$ Gate)는 때로는 더하기 기호를 둘러싼 원으로 표시되기도 합니다:

  

• 스왑(Swap) Gate는 다음과 같이 표시됩니다:

  

• 제어-Gate, 즉 제어-유니타리 연산을 기술하는 Gate는 제어를 나타내는 채워진 원을 수직선으로 제어되는 연산과 연결한 형태로 표시됩니다. 예를 들어, 제어-NOT Gate, 제어-제어-NOT(또는 Toffoli) Gate, 제어-스왑(Fredkin) Gate는 다음과 같이 표시됩니다:

  

• 여러 Qubit에 대한 임의의 유니타리 연산도 Gate로 볼 수 있습니다. 이들은 해당 유니타리 연산의 이름이 표시된 사각형으로 묘사됩니다. 예를 들어, 다음은 (특정되지 않은) 유니타리 연산 $U$를 Gate로 나타낸 것과 이 Gate의 제어 버전을 나타낸 것입니다: