고전 정보

양자 정보와 그 작동 방식을 설명하기 위해, 먼저 고전 정보에 대한 개요부터 시작하겠습니다. 양자 정보를 다루는 강좌에서 고전 정보에 왜 이렇게 많은 관심을 기울이는지 의아할 수 있지만, 그에는 충분한 이유가 있습니다.

우선, 양자 정보와 고전 정보는 몇 가지 놀라운 면에서 서로 다르지만, 수학적 서술 방식은 실제로 상당히 유사합니다. 또한 고전 정보는 양자 정보를 공부할 때 친숙한 참조점이 되며, 놀랍도록 광범위하게 활용될 수 있는 유추의 원천이 되기도 합니다. 양자 정보에 대해 제기되는 질문들은 자연스러운 고전적 유사체를 가지는 경우가 많으며, 그 질문들은 종종 간단한 답을 통해 양자 정보에 대한 원래 질문에 명확성과 통찰을 제공합니다. 실제로, 고전 정보를 이해하지 않고서는 양자 정보를 진정으로 이해할 수 없다고 해도 과언이 아닙니다.

이 절에서 다루는 내용이 이미 익숙한 독자도 있고, 그렇지 않은 독자도 있을 것입니다. 이 설명은 두 부류의 독자 모두를 위한 것입니다. 양자 정보 입문에 가장 관련성이 높은 고전 정보의 측면을 강조하는 것 외에도, 이 절에서는 *디랙 표기법(Dirac notation)*을 소개합니다. 이 표기법은 양자 정보와 계산에서 벡터와 행렬을 나타낼 때 자주 사용됩니다. 사실 디랙 표기법은 양자 정보에만 국한된 것이 아니며, 고전 정보의 맥락에서도, 그리고 벡터와 행렬이 등장하는 다른 여러 상황에서도 동일하게 활용할 수 있습니다.

고전 상태와 확률 벡터

정보를 저장하는 시스템이 있다고 가정해 봅시다. 더 구체적으로는, 이 시스템이 매 순간 유한한 수의 고전 상태(classical states) 중 하나에 있을 수 있다고 가정합니다. 여기서 고전 상태라는 용어는 직관적인 의미로, 즉 모호함 없이 인식하고 설명할 수 있는 구성(configuration)으로 이해해야 합니다.

대표적인 예시는 *비트(bit)*로, 이는 고전 상태가 $0$과 $1$인 시스템입니다. 이 예시는 이후에도 반복적으로 등장할 것입니다. 다른 예시로는 표준 육면체 주사위(고전 상태는 $1,$ $2,$ $3,$ $4,$ $5,$ $6$으로, 위를 향하는 면의 점의 수로 표현됨), DNA 가닥의 핵염기(고전 상태는 A, C, G, T), 전기 선풍기의 스위치(고전 상태는 일반적으로 고속(high), 중속(medium), 저속(low), 꺼짐(off)) 등이 있습니다. 수학적으로 보면, 시스템의 고전 상태 명세는 사실상 출발점입니다. 즉, 고전 상태가 $0$과 $1$인 시스템을 비트로 정의하며, 서로 다른 고전 상태 집합을 가지는 시스템도 마찬가지입니다.

설명의 편의를 위해, 고려하는 시스템에 $\mathsf{X}$라는 이름을 부여하고, $\mathsf{X}$의 고전 상태 집합을 나타내는 기호로 $\Sigma$를 사용하겠습니다. 이미 언급한 $\Sigma$가 유한하다는 가정 외에도, 물리 시스템이 아무런 상태도 없다는 것은 말이 되지 않으므로 $\Sigma$가 *비어 있지 않다(nonempty)*는 것도 자연스럽게 가정합니다. 물론 무한히 많은 고전 상태를 가지는 물리 시스템을 고려하는 것도 의미가 있으나, 이는 흥미롭기는 하지만 이 강좌와는 관련이 없으므로 다루지 않겠습니다. 이러한 이유로, 편의와 간결함을 위해 이후에는 고전 상태 집합이라는 용어를 유한하고 비어 있지 않은 임의의 집합을 가리키는 데 사용하겠습니다.

몇 가지 예시를 들면 다음과 같습니다:

1. $\mathsf{X}$가 비트이면 $\Sigma = \{0,1\}$입니다. 이 집합을 *이진 알파벳(binary alphabet)*이라고 부릅니다.
2. $\mathsf{X}$가 육면체 주사위이면 $\Sigma = \{1,2,3,4,5,6\}$입니다.
3. $\mathsf{X}$가 전기 선풍기 스위치이면 $\Sigma = \{\mathrm{high}, \mathrm{medium}, \mathrm{low}, \mathrm{off}\}$입니다.

$\mathsf{X}$를 정보의 운반체로 생각할 때, $\mathsf{X}$의 서로 다른 고전 상태에 특정 의미를 부여하여 서로 다른 결과나 결론으로 이어지게 할 수 있습니다. 이러한 경우, $\mathsf{X}$가 가능한 고전 상태 중 하나에 있다고 단순하게 서술하는 것으로 충분할 수 있습니다. 예를 들어, $\mathsf{X}$가 선풍기 스위치라면, 우리는 스위치가 고속으로 설정되어 있다는 것을 확실히 알고 있고, 이를 바탕으로 중속으로 바꿀 수 있습니다.

그러나 정보 처리에서는 우리의 지식이 불확실한 경우가 많습니다. 시스템 $\mathsf{X}$의 고전 상태에 대한 우리의 지식을 표현하는 한 가지 방법은, 가능한 각 고전 상태에 확률을 연결하는 것입니다. 이를 *확률적 상태(probabilistic state)*라고 부르겠습니다.

예를 들어, $\mathsf{X}$가 비트라고 가정해 봅시다. $\mathsf{X}$에 과거에 일어난 일에 대한 우리의 지식이나 예상에 따라, $\mathsf{X}$가 고전 상태 $0$에 있을 확률을 $3/4$, 상태 $1$에 있을 확률을 $1/4$로 믿을 수 있습니다. 이러한 믿음은 다음과 같이 나타낼 수 있습니다:

$$\operatorname{Pr}(\mathsf{X}=0) = \frac{3}{4} \quad\text{and}\quad \operatorname{Pr}(\mathsf{X}=1) = \frac{1}{4}.$$

이 확률적 상태를 더 간결하게 나타내는 방법은 열벡터(column vector)를 사용하는 것입니다.

$$\begin{pmatrix} \frac{3}{4}\\[2mm] \frac{1}{4} \end{pmatrix}$$

비트가 $0$일 확률은 벡터의 위에, 비트가 $1$일 확률은 아래에 배치하는데, 이는 집합 $\{0,1\}$을 정렬하는 관례적인 방식이기 때문입니다.

일반적으로, 임의의 고전 상태 집합을 가지는 시스템의 확률적 상태도 마찬가지 방식으로, 확률로 이루어진 벡터로 나타낼 수 있습니다. 확률의 순서는 임의로 정할 수 있지만, 자연스럽거나 기본적인 순서가 있는 경우가 일반적입니다. 정확히 말하면, 다음 두 가지 성질을 만족하는 열벡터로 임의의 확률적 상태를 표현할 수 있습니다:

1. 벡터의 모든 원소는 *음이 아닌 실수(nonnegative real numbers)*입니다.
2. 원소들의 합이 $1$과 같습니다.

역으로, 이 두 성질을 만족하는 임의의 열벡터는 확률적 상태의 표현으로 취할 수 있습니다. 이후에는 이러한 형태의 벡터를 *확률 벡터(probability vectors)*라고 부르겠습니다.

이 표기법의 간결함 외에도, 확률적 상태를 열벡터로 나타내면 확률적 상태에 대한 연산이 행렬-벡터 곱셈으로 표현된다는 장점이 있으며, 이에 대해서는 곧 논의할 것입니다.

확률적 상태의 측정

다음으로, 시스템이 확률적 상태에 있을 때 *측정(measure)*하면 어떤 일이 일어나는지 살펴봅시다. 여기서 시스템을 측정한다는 것은 단순히 시스템을 바라보고 어떤 고전 상태에 있는지를 모호함 없이 인식하는 것을 의미합니다. 직관적으로 말하면, 시스템의 확률적 상태를 "볼" 수는 없습니다. 시스템을 보면 가능한 고전 상태 중 하나만 보일 뿐입니다.

시스템을 측정함으로써 시스템에 대한 우리의 지식이 바뀔 수 있으며, 따라서 시스템과 연결된 확률적 상태도 변할 수 있습니다. 즉, $\mathsf{X}$가 고전 상태 $a\in\Sigma$에 있다고 인식한다면, $\mathsf{X}$의 상태에 대한 지식을 나타내는 새로운 확률 벡터는 $a$에 해당하는 원소가 $1$이고 나머지는 모두 $0$인 벡터가 됩니다. 이 벡터는 $\mathsf{X}$가 고전 상태 $a$에 확실히 있음을 나타내며(방금 인식했으므로), 이 벡터를 $\vert a\rangle$으로 표기하고 "ket $a$"라고 읽습니다. 그 이유는 곧 설명하겠습니다. 이런 종류의 벡터를 표준 기저(standard basis) 벡터라고도 부릅니다.

예를 들어, 고려하는 시스템이 비트라고 가정하면, 표준 기저 벡터는 다음과 같습니다:

$$\vert 0\rangle = \begin{pmatrix}1\\[1mm] 0\end{pmatrix} \quad\text{and}\quad \vert 1\rangle = \begin{pmatrix}0\\[1mm] 1\end{pmatrix}.$$

임의의 2차원 열벡터는 이 두 벡터의 선형 결합으로 표현할 수 있다는 점에 주목하세요. 예를 들어,

$$\begin{pmatrix} \frac{3}{4}\\[2mm] \frac{1}{4} \end{pmatrix} = \frac{3}{4}\,\vert 0\rangle + \frac{1}{4}\,\vert 1\rangle.$$

이 사실은 임의의 고전 상태 집합으로 자연스럽게 일반화됩니다. 즉, 임의의 열벡터는 표준 기저 상태의 선형 결합으로 표현할 수 있습니다. 벡터를 정확히 이러한 방식으로 표현하는 경우가 매우 많습니다.

측정 시 확률적 상태가 변하는 것으로 돌아가서, 우리의 일상적인 경험과의 연결성을 살펴볼 수 있습니다. 공정한 동전을 던지되, 보기 전에 동전을 가린다고 가정합시다. 그러면 동전의 확률적 상태는 다음과 같습니다:

$$\begin{pmatrix} \frac{1}{2}\\[2mm] \frac{1}{2} \end{pmatrix} = \frac{1}{2}\,\vert\text{heads}\rangle + \frac{1}{2}\,\vert\text{tails}\rangle.$$

여기서 동전의 고전 상태 집합은 $\{\text{heads},\text{tails}\}$입니다. 앞면(heads)을 먼저, 뒷면(tails)을 나중으로 순서를 정하겠습니다.

$$\vert\text{heads}\rangle = \begin{pmatrix}1\\[1mm] 0\end{pmatrix} \quad\text{and}\quad \vert\text{tails}\rangle = \begin{pmatrix}0\\[1mm] 1\end{pmatrix}$$

동전의 덮개를 걷어내고 보면, 두 고전 상태 중 하나(앞면 또는 뒷면)를 보게 됩니다. 결과가 뒷면이라면, 동전의 확률적 상태를 $|\text{tails}\rangle$로 자연스럽게 업데이트할 것입니다. 물론, 다시 동전을 가리고 다시 들여다보면 고전 상태는 여전히 뒷면일 것이며, 이는 확률적 상태가 벡터 $|\text{tails}\rangle$로 서술되는 것과 일치합니다.

이것이 사소하게 보일 수 있으며, 어떤 의미에서는 그렇습니다. 그러나 양자 시스템도 완전히 유사한 방식으로 동작하지만, 그 측정 특성은 종종 이상하거나 특이하게 여겨집니다. 고전 시스템의 유사한 성질을 확립함으로써, 양자 정보가 작동하는 방식이 덜 특이하게 느껴질 수 있습니다.

확률적 상태의 측정에 관한 마지막 언급은 다음과 같습니다: 확률적 상태는 실제 현실이 아니라 지식이나 믿음을 서술하며, 측정은 단지 우리의 지식을 변화시킬 뿐 시스템 자체를 바꾸지 않습니다. 예를 들어, 동전을 던진 후 보기 전의 동전 상태는 앞면이거나 뒷면입니다. 우리가 볼 때까지 어느 쪽인지 모를 뿐입니다. 고전 상태가 뒷면임을 확인했다면, 우리의 지식을 나타내는 벡터를 $|\text{tails}\rangle$로 자연스럽게 업데이트하겠지만, 동전이 공개될 때 보지 못한 다른 사람에게는 확률적 상태가 변하지 않은 채로 남아 있습니다. 이것은 걱정할 일이 아닙니다. 서로 다른 사람들이 특정 시스템에 대해 서로 다른 지식이나 믿음을 가질 수 있으며, 따라서 서로 다른 확률 벡터로 그 시스템을 서술할 수 있습니다.

고전적 연산

이 간략한 고전 정보 요약의 마지막 부분에서는 고전 시스템에 수행할 수 있는 연산의 종류를 살펴보겠습니다.

결정론적 연산

먼저, 결정론적 연산이 있습니다. 이 연산에서는 각 고전 상태 $a\in\Sigma$가 $f:\Sigma\rightarrow\Sigma$ 형태의 어떤 함수 $f$에 의해 $f(a)$로 변환됩니다.

예를 들어, $\Sigma = \{0,1\}$이면 이 형태의 함수는 네 가지 $f_1,$ $f_2,$ $f_3,$ $f_4$가 있으며, 다음과 같이 값 표로 나타낼 수 있습니다:

$$\begin{array}{c|c} a & f_1(a)\\ \hline 0 & 0\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_2(a)\\ \hline 0 & 0\\ 1 & 1 \end{array} \qquad \begin{array}{c|c} a & f_3(a)\\ \hline 0 & 1\\ 1 & 0 \end{array} \qquad \begin{array}{c|c} a & f_4(a)\\ \hline 0 & 1\\ 1 & 1 \end{array}$$

이 중 첫 번째와 마지막 함수는 상수 함수입니다: 각 $a\in\Sigma$에 대해 $f_1(a) = 0$이고 $f_4(a) = 1$입니다. 가운데 두 함수는 상수가 아니라 균형 함수입니다: 가능한 입력 전체를 범위로 할 때 두 출력값이 같은 횟수(이 경우 각각 한 번)씩 나타납니다. $f_2$는 항등 함수입니다: 각 $a\in\Sigma$에 대해 $f_2(a) = a$입니다. 그리고 $f_3$는 $f_3(0) = 1$이고 $f_3(1) = 0$인 함수로, NOT 함수로 더 잘 알려져 있습니다.

결정론적 연산이 확률적 상태에 작용하는 방식은 행렬-벡터 곱으로 나타낼 수 있습니다. 구체적으로, 주어진 함수 $f:\Sigma\rightarrow\Sigma$를 나타내는 행렬 $M$은 다음 조건을 만족하는 행렬입니다:

$$M \vert a \rangle = \vert f(a)\rangle$$

이 조건은 모든 $a\in\Sigma$에 대해 성립합니다. 이러한 행렬은 항상 존재하며 이 조건에 의해 유일하게 결정됩니다. 결정론적 연산을 나타내는 행렬은 각 열에 정확히 하나의 $1$을 가지고, 나머지 항목은 모두 $0$입니다.

예를 들어, 위의 함수 $f_1,\ldots,f_4$에 대응하는 행렬 $M_1,\ldots,M_4$는 다음과 같습니다:

$$M_1 = \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix}, \hspace{4mm} M_2 = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}, \hspace{4mm} M_3 = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}, \hspace{4mm} M_4 = \begin{pmatrix} 0 & 0\\ 1 & 1 \end{pmatrix}.$$

다음은 첫 번째 행렬이 올바름을 빠르게 검증한 것입니다. 나머지 세 행렬도 같은 방식으로 확인할 수 있습니다.

$$\begin{aligned} M_1 \vert 0\rangle & = \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 1\\ 0 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix} = \vert 0\rangle = \vert f_1(0)\rangle \\[4mm] M_1 \vert 1\rangle & = \begin{pmatrix} 1 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0\\ 1 \end{pmatrix} = \begin{pmatrix} 1\\ 0 \end{pmatrix} = \vert 0\rangle = \vert f_1(1)\rangle \end{aligned}$$

이러한 형태와 다른 형태의 행렬을 편리하게 나타내는 방법으로, 앞서 열벡터에 사용한 표기법과 유사한 행벡터 표기법을 활용합니다: 각 $a\in\Sigma$에 대해, $a$에 해당하는 항목이 $1$이고 나머지 항목은 모두 $0$인 행 벡터를 $\langle a \vert$로 표기합니다. 이 벡터는 "bra $a$"라고 읽습니다.

예를 들어, $\Sigma = \{0,1\}$이면

$$\langle 0 \vert = \begin{pmatrix} 1 & 0 \end{pmatrix} \quad\text{and}\quad \langle 1 \vert = \begin{pmatrix} 0 & 1 \end{pmatrix}.$$

임의의 고전 상태 집합 $\Sigma$에 대해, 행벡터와 열벡터를 행렬로 간주하면 행렬 곱 $\vert b\rangle \langle a\vert$를 수행할 수 있습니다. 그 결과는 쌍 $(b,a)$에 해당하는 항목(행은 고전 상태 $b$, 열은 고전 상태 $a$에 대응)이 $1$이고 나머지는 모두 $0$인 정방행렬이 됩니다. 예를 들어,

$$\vert 0 \rangle \langle 1 \vert = \begin{pmatrix} 1\\ 0 \end{pmatrix} \begin{pmatrix} 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}.$$

이 표기법을 사용하면, 임의의 함수 $f:\Sigma\rightarrow\Sigma$에 대응하는 행렬 $M$을 다음과 같이 표현할 수 있습니다:

$$M = \sum_{a\in\Sigma} \vert f(a) \rangle \langle a \vert.$$

예를 들어, $\Sigma = \{0,1\}$인 위의 함수 $f_4$를 생각해 봅시다. 행렬은 다음과 같이 구해집니다:

$$M_4 = \vert f_4(0) \rangle \langle 0 \vert + \vert f_4(1) \rangle \langle 1 \vert = \vert 1\rangle \langle 0\vert + \vert 1\rangle \langle 1\vert = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} + \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 1 \end{pmatrix}.$$

이것이 성립하는 이유는 다음과 같습니다. 벡터를 다시 행렬로 생각하고, 이번에는 곱 $\langle a \vert \vert b \rangle$를 고려하면, $1\times 1$ 행렬, 즉 스칼라(수)가 됩니다. 표기의 간결함을 위해 이 곱을 $\langle a \vert \vert b \rangle$가 아닌 $\langle a \vert b\rangle$로 씁니다. 이 곱은 다음의 간단한 공식을 만족합니다:

$$\langle a \vert b \rangle = \begin{cases} 1 & a = b\\[1mm] 0 & a \neq b. \end{cases}$$

이 관찰과 행렬 곱이 결합 법칙과 선형성을 만족한다는 사실을 함께 이용하면, 모든 $b\in\Sigma$에 대해

$$M \vert b \rangle = \Biggl( \sum_{a\in\Sigma} \vert f(a) \rangle \langle a \vert \Biggr) \vert b\rangle = \sum_{a\in\Sigma} \vert f(a) \rangle \langle a \vert b \rangle = \vert f(b)\rangle,$$

을 얻을 수 있으며, 이것이 바로 행렬 $M$에 요구하는 조건입니다.

나중에 다른 강의에서 더 자세히 다루겠지만, $\langle a \vert b \rangle$는 벡터 $\vert a\rangle$와 $\vert b\rangle$ 사이의 내적으로 볼 수도 있습니다. 내적은 양자 정보에서 매우 중요하지만, 필요한 시점이 될 때까지 논의를 미루겠습니다.

이 시점에서 "bra"와 "ket"라는 이름의 유래가 분명해졌을 것입니다: "bra" $\langle a\vert$와 "ket" $\vert b\rangle$를 합치면 "bracket" $\langle a \vert b\rangle$가 됩니다. 이 표기법과 용어는 폴 디랙이 도입한 것으로, 그 이름을 따서 디랙 표기법이라고 합니다.

확률적 연산과 확률 행렬

결정론적 연산 외에도 확률적 연산이 존재합니다.

예를 들어, 비트에 대한 다음 연산을 생각해 보겠습니다. 비트의 고전 상태가 $0$이면 그대로 두고, 고전 상태가 $1$이면 뒤집어서 확률 $1/2$로 $0$이 되거나 확률 $1/2$로 $1$이 됩니다. 이 연산은 다음 행렬로 표현됩니다.

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

두 표준 기저 벡터를 이 행렬에 곱해 보면 올바른 결과가 나오는지 확인할 수 있습니다.

임의의 고전 상태 집합에 대해, 모든 확률적 연산의 집합을 수학적으로 기술하면 확률(stochastic) 행렬로 표현되는 연산들이며, 이 행렬은 다음 두 가지 성질을 만족합니다.

1. 모든 원소가 음이 아닌 실수입니다.
2. 각 열의 원소의 합이 $1$입니다.

다시 말해, 확률 행렬은 모든 열이 확률 벡터를 이루는 행렬입니다.

확률적 연산을 직관적으로 생각하면, 위의 예시처럼 연산 과정에서 어떤 식으로든 무작위성이 사용되거나 도입되는 연산입니다. 확률적 연산의 확률 행렬 표현에서, 각 열은 해당 열에 대응하는 고전 상태를 입력으로 받았을 때 생성되는 확률 상태의 벡터 표현으로 볼 수 있습니다.

또한 확률 행렬은 확률 벡터를 항상 확률 벡터로 대응시키는 정확히 그 행렬들로 생각할 수도 있습니다. 즉, 확률 행렬은 항상 확률 벡터를 확률 벡터로 대응시키며, 확률 벡터를 항상 확률 벡터로 대응시키는 행렬은 반드시 확률 행렬입니다.

마지막으로, 확률적 연산을 바라보는 또 다른 방식은 결정론적 연산들 중 하나를 무작위로 선택하는 것으로 보는 것입니다. 예를 들어, 위 예시의 연산은 항등 함수와 상수 0 함수 중 하나를 각각 확률 $1/2$로 적용하는 것으로 생각할 수 있습니다. 이는 다음 등식과 일치합니다.

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

이러한 표현은 임의의 고전 상태 집합과, 해당 집합으로 행과 열이 인덱싱된 임의의 확률 행렬에 대해 항상 가능합니다.

확률적 연산의 합성

$\mathsf{X}$가 고전 상태 집합 $\Sigma$를 가진 시스템이고, $M_1,\ldots,M_n$이 시스템 $\mathsf{X}$에 대한 확률적 연산을 나타내는 확률 행렬이라고 가정합니다.

확률 벡터 $u$로 표현되는 확률 상태에 첫 번째 연산 $M_1$을 적용하면, 결과 확률 상태는 벡터 $M_1 u$로 표현됩니다. 이 새로운 확률 벡터에 두 번째 확률적 연산 $M_2$를 적용하면 다음 확률 벡터를 얻습니다.

$$M_2 (M_1 u) = (M_2 M_1) u.$$

이 등식은 행렬 곱셈(행렬-벡터 곱셈을 특수한 경우로 포함)이 결합 연산이라는 사실에서 성립합니다. 따라서, 먼저 $M_1$을 적용한 뒤 $M_2$를 적용하는 방식으로 첫 번째와 두 번째 확률적 연산을 합성하여 얻는 확률적 연산은 행렬 $M_2 M_1$로 표현되며, 이 행렬은 반드시 확률 행렬입니다.

더 일반적으로, 행렬 $M_1,\ldots,M_n$으로 표현되는 확률적 연산들을 이 순서대로, 즉 $M_1$을 먼저 적용하고, $M_2$를 두 번째로 적용하며, 마지막으로 $M_n$을 적용하도록 합성하면 다음 행렬 곱으로 표현됩니다.

$$M_n \,\cdots\, M_1.$$

여기서 순서가 중요합니다. 행렬 곱셈은 결합 법칙이 성립하지만 교환 연산은 아닙니다. 예를 들어,

$$M_1 = \begin{pmatrix} 1 & 1\\[1mm] 0 & 0 \end{pmatrix} \quad\text{and}\quad M_2 = \begin{pmatrix} 0 & 1\\[1mm] 1 & 0 \end{pmatrix},$$

이면

$$M_2 M_1 = \begin{pmatrix} 0 & 0 \\[1mm] 1 & 1 \end{pmatrix} \quad\text{and}\quad M_1 M_2 = \begin{pmatrix} 1 & 1\\[1mm] 0 & 0 \end{pmatrix}.$$

즉, 확률적 연산을 합성하는 순서가 중요합니다. 합성에서 연산을 적용하는 순서를 바꾸면 결과 연산이 달라질 수 있습니다.