양자 연산

양자 컴퓨팅은 현재 활발히 연구되는 주제입니다. 만약 실제로 만들 수 있다면, 양자 컴퓨터는 특정 계산 작업을 오늘날 존재하는 그 어떤 컴퓨터보다도 훨씬 빠르게 수행할 수 있습니다. 다행히 이 문제를 풀기 위해 양자 컴퓨터가 필요하지는 않습니다.

양자 컴퓨팅의 핵심 개념 중 하나는 양자 연산(quantum operation) 입니다. 양자 연산은 본질적으로 하나의 행렬로 생각할 수 있습니다. 또한 서로 다른 양자 데이터에 대해 두 양자 연산을 병렬로 수행하면, 그 결과를 더 큰 하나의 양자 연산으로 볼 수 있습니다. 이를 행렬의 관점에서 보면, 두 행렬을 병렬로 결합하여 얻는 행렬을 두 행렬의 텐서 곱(tensor product) 이라 하며 기호 $\otimes$ 로 나타냅니다. 이는 여러분이 배웠을 법한 일반적인 행렬 곱과는 다릅니다.

두 행렬 $A$ 와 $B$(각각 본질적으로 2차원 배열)가 주어질 때, 각 원소를 다음과 같이 나타냅니다.

$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}, \quad B = \begin{bmatrix} b_{11} & b_{12} & \cdots & b_{1q} \\ b_{21} & b_{22} & \cdots & b_{2q} \\ \vdots & \vdots & \ddots & \vdots \\ b_{p1} & b_{p2} & \cdots & b_{pq} \end{bmatrix}.$

여기서 행렬 $A$ 의 크기는 $m \times n$($m$ 행, $n$ 열)이고, 행렬 $B$ 의 크기는 $p \times q$ 입니다.

두 행렬의 텐서 곱은 다음과 같은 $mp \times nq$ 행렬($mp$ 행, $nq$ 열)입니다.

$A \otimes B = \begin{bmatrix} a_{11}[B] & a_{12}[B] & \cdots & a_{1n}[B] \\ a_{21}[B] & a_{22}[B] & \cdots & a_{2n}[B] \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}[B] & a_{m2}[B] & \cdots & a_{mn}[B] \end{bmatrix},$

여기서 $a_{ij}[B]$ 는 $B$ 의 모든 원소에 $a_{ij}$ 를 곱하여 얻은 블록을 뜻합니다.

텐서 곱은 교환법칙이 성립하지 않습니다. 즉, 행렬의 순서를 바꾸면 결과가 달라질 수 있습니다($A \otimes B \ne B \otimes A$).

세 개 이상의 행렬에 대해서는 $A \otimes B \otimes C = (A \otimes B) \otimes C$ 로 정의합니다. 텐서 곱은 결합법칙이 성립하므로 어떻게 묶어 계산하든 결과는 같습니다.

주어진 두 개 이상의 행렬의 텐서 곱을 계산하고, 그에 대한 몇 가지 통계값을 출력하세요.

첫째 줄에는 행렬의 개수 $N$(양의 정수)이 주어집니다. 그다음에는 $N$ 개의 행렬을 순서대로 설명하는 블록이 이어집니다.

각 블록의 첫째 줄에는 두 양의 정수 $r$ 과 $c$ 가 공백으로 구분되어 주어지며, 각각 행의 수와 열의 수를 나타냅니다. 이어지는 $r$ 개의 줄은 각 행을 순서대로 나타내며, 각 줄에는 $c$ 개의 정수가 공백으로 구분되어 주어집니다.

다음 순서대로 여섯 개의 정수를 한 줄에 하나씩 출력합니다.

• 텐서 곱의 최대 원소
• 텐서 곱의 최소 원소
• 최대 행 합(한 행에 있는 원소들의 합)
• 최소 행 합
• 최대 열 합(한 열에 있는 원소들의 합)
• 최소 열 합

텐서 곱 행렬의 행 수와 열 수는 각각 $1024$ 를 넘지 않는다고 가정해도 좋습니다.